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