При построении регулярных графов необходимо учитывать то, что они могут быть получены из полных графов.
В задачах компьютерного моделирования и составления различного рода структур данных часто необходимо работать с регулярными графами.
Регулярный граф – граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается r(G) .
На сегодняшний день известны следующие способы построения регулярных графов:
1) матрица смежности;
2) матрица инцидентности;
3) случайный граф;
Полный граф Km является сильно регулярным для любого m.
Построение регулярного графа со степенью n представляет собой сложность, если строить его начиная с нуль-графа или с одной вершины. Чтобы построить регулярный граф со степенью r(G) < n, необходимо вначале построить полный граф со степенью n и далее равномерно удалить из него «лишние» ребра. Такой способ построения графов представляется менее трудоемким.