При построении регулярных графов необходимо учитывать то, что они могут быть получены из полных графов.

В задачах компьютерного моделирования и составления различного рода структур данных часто необходимо работать с регулярными графами.

Регулярный граф – граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается r(G) .

На сегодняшний день известны следующие способы построения регулярных графов:

1) матрица смежности;

2) матрица инцидентности;

3) случайный граф;

Полный граф Km является сильно регулярным для любого m.

Построение регулярного графа со степенью n представляет собой сложность, если строить его начиная с нуль-графа или с одной вершины. Чтобы построить регулярный граф со степенью r(G) < n, необходимо вначале построить полный граф со степенью n и далее равномерно удалить из него «лишние» ребра. Такой способ построения графов представляется менее трудоемким.