WikiSort.ru - Не сортированное

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

Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее индекс самопересечения (англ.).

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

Обобщённое определение

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

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

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

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

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

Известны ещё некоторые клетки. В таблице ниже показано количество вершин в (r,n)-клетках степени 3≤r≤7 и обхвата 3≤n≤12. Клетки для этих и бо́льших r и n описаны здесь: (на английском языке).

Графы Мура

Количество вершин в (r,n)-клетке больше или равно

${\displaystyle 1+r\sum _{i=0}^{(n-3)/2}(r-1)^{i}}$ для нечётных n и

${\displaystyle 2\sum _{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.

Примечания

Литература

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

Ссылки

• Weisstein, Eric W. Клеточный граф (англ.) на сайте Wolfram MathWorld.
• https://web.archive.org/web/20090224031515/http://people.csse.uwa.edu.au/gordon/cages/  (англ.)

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.