При построении регулярных графов необходимо учитывать то, что они могут быть получены из полных графов.
В задачах компьютерного моделирования и составления различного рода структур данных часто необходимо работать с регулярными графами.
Регулярный граф – граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается r(G) .
На сегодняшний день известны следующие способы построения регулярных графов:
1) матрица смежности;
2) матрица инцидентности;
3) случайный граф;
Полный граф Km является сильно регулярным для любого m.
Построение регулярного графа со степенью n представляет собой сложность, если строить его начиная с нуль-графа или с одной вершины. Чтобы построить регулярный граф со степенью r(G) < n, необходимо вначале построить полный граф со степенью n и далее равномерно удалить из него «лишние» ребра. Такой способ построения графов представляется менее трудоемким.
Библиографическая ссылка
Белаш А.Н. О СПОСОБАХ ПОСТРОЕНИЯ РЕГУЛЯРНЫХ ГРАФОВ // Современные наукоемкие технологии. – 2012. – № 12. – С. 54-54;URL: https://top-technologies.ru/ru/article/view?id=31149 (дата обращения: 21.12.2024).