Регулярный граф
граф, степени всех вершин которого равны / Материал из Википедии — свободной encyclopedia
Уважаемый Wikiwand AI, давайте упростим задачу, просто ответив на эти ключевые вопросы:
Перечислите основные факты и статистические данные о Регулярный граф?
Кратко изложите эту статью для 10-летнего ребёнка
Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей. Степень регулярности является инвариантом графа и обозначается . Для нерегулярных графов не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
Регулярный граф с вершинами степени называется регулярным графом степени , или ‑регулярным.
Регулярные графы степени не больше двух легко классифицировать: 0-регулярный граф состоит из изолированных вершин (нуль-граф), 1-регулярный — из изолированных рёбер, а 2-регулярный — из разрозненных циклов.
3-регулярный граф известен также как кубический.
Сильно регулярный граф есть регулярный граф, для которого существуют такие и , что любые две смежные вершины имеют общих соседей и любые две несмежные вершины имеют общих соседей. Наименьшие графы, которые регулярны, но не сильно регулярны — циклический граф и циркулянтный граф на шести вершинах.
Полный граф является сильно регулярным для любого .
Теорема Нэш-Вильямса[англ.] гласит, что каждый k‑регулярный граф на 2k + 1 вершинах имеет гамильтонов цикл.
- 0-регулярный граф
- 1-регулярный граф
- 2-регулярный граф
- 3-регулярный граф
- Ещё один 3-регулярный граф — граф Петерсена