Клітка (теорія графів)

Матеріал з testwiki
Перейти до навігації Перейти до пошуку

Шаблон:Значення

Граф Петерсена
Граф Хівуда
Граф Маꥳ
Граф Татта — Коксетера
Граф Гофмана — Синглтона

n-клітка — кубічний граф обхвату n з найменшим можливим числом вершин. Граф називається кубічним, якщо з кожної його вершини виходять 3 ребра. Обхват графа — це довжина найменшого циклу в ньому.

  • 3-клітка — К4, остов тетраедра, 4 вершини.
  • 4-клітка — К3,3, один з двох мінімальних не планарних графів, 6 вершин.
  • 5-клітка — граф Петерсена, 10 вершин. Мінімальний кубічний граф з індексом самоперетину 2.
  • 6-клітка — граф Хівуда, 14 вершин. Розбивається на 1-фактори (тобто, реберно розфарбовуємий), будь-яка сума двох чинників утворює гамільтонів цикл. Мінімальний кубічний граф з індексом самоперетину 3.
  • 7-клітка — граф Маꥳ, 24 вершини. Мінімальний кубічний граф з індексом самоперетину 8.
  • 8-клітка — граф Татта — Коксетера, 30 вершин.

Узагальнене визначення

(r,n)-клітка — регулярний граф ступеня r (тобто з кожної вершини якого виходить рівно r ребер) та обхвату n з найменшим можливим числом вершин.

Тривіальні сімейства

  • (2,n)-клітками є, очевидно, циклічні графи Cn
  • (r-1,3)-клітки — повні графи Кr з r вершин
  • (r,4)-клітки — повні двочасткові графи Кr,r, у яких в кожній долі знаходиться по r вершин

Нетривіальні представники

  • (7,5)-клітка — граф Гофмана — Синглтона, 50 вершин.

Відомі ще деякі клітки. У таблиці нижче показано кількість вершин в (r,n)-клітинах ступеня 3≤r≤7 та обхвату 3≤n≤12. Клітки для цих та великих r и n описані тут: [1] (англійською мовою).

n: 3 4 5 6 7 8 9 10 11 12
r = 3: 4 6 10 14 24 30 58 70 112 126
r = 4: 5 8 19 26 67 80 275 384 728
r = 5: 6 10 30 42 152 170 2730
r = 6: 7 12 40 62 294 312 7812
r = 7: 8 14 50 90

Графи Мура

Шаблон:Докладніше Кількість вершин в (r,n)-клітці більше або дорівнює

1+r∑i=0(n−3)/2(r−1)i для непарних n та
2∑i=0(n−2)/2(r−1)i для парних.

Якщо має місце рівність, то відповідний граф називається графом Мура. У той час як клітка існує для будь-яких r > 2 і n > 2, нетривіальних графів Мура набагато менше. З вищезгаданих клітин, графами Мура є граф Петерсена, граф Хівуда, граф Татта — Коксетера і граф Гофмана — Синглтона. Доведено,[1][2][3] що всі непарні випадки вичерпуються n = 5, r = 2, 3, 7 та, можливо, 57, а парні n = 6, 8, 12.

Примітки

Шаблон:Reflist

Література

  • Ф. Харари Теория графов. — М.: УРСС, — 2003. — 300 с — ISBN 5-354-00301-6.

Посилання

Посилання

  1. ↑ Bannai, E. and Ito, T. «On Moore Graphs.» J. Fac. Sci. Univ. Tokyo Ser. A 20, 191—208, 1973
  2. ↑ Damerell, R. M. «On Moore Graphs.» Proc. Cambridge Philos. Soc. 74, 227—236, 1973
  3. ↑ Hoffman, A. J. and Singleton, R. R. «On Moore Graphs of Diameter 2 and 3.» IBM J. Res. Develop. 4, 497—504, 1960
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Клітка_(теорія_графів)&oldid=6540