Снарк «Цветок»

Перейти к навигации Перейти к поиску

Снарки «Цветок» J₃, J₅ и J₇.

Вершин	4n
Рёбер	6n
Обхват	3 для n=3 5 для n=5 6 для n≥7
Хроматическое число	3
Хроматический индекс	4
Свойства	снарк для n≥5
Медиафайлы на Викискладе

Снарк «Цветок» J₅

Вершин	20
Рёбер	30
Обхват	5
Хроматическое число	3
Хроматический индекс	4
Свойства	снарк гипогамильтонов
Медиафайлы на Викискладе

В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году^[1].

Как и все снарки, цветы являются связными кубическими графами без мостов с хроматическим индексом 4. Они не планарны и не гамильтоновы.

Построение

Цветок J_n можно построить следующим процессом:

Образуем n копий звезды с 4 вершинами. Обозначим центр каждой звезды через A_i, а внешние вершины — через B_i, C_i и D_i. Результатом будет несвязный граф с 4n вершинами и 3n рёбрами (A_i-B_i, A_i-C_i и A_i-D_i для 1≤i≤n).
Образуем цикл длины n (B₁... B_n). Это добавит n рёбер.
Образуем цикл длины 2n (C₁... C_nD₁... D_n). Это добавит ещё 2n рёбер.

По построению цветок J_n является кубическим графом с 4n вершинами и 6n рёбрами. Чтобы получить необходимые свойства, n должен быть нечётным.

Специальные случаи

Название «цветок» иногда используется для J₅, снарка с 20 вершинами и 30 рёбрами^[2]. Это один из 6 снарков с 20 вершинами (последовательность A130315 в OEIS). Цветок J₅ является гипогамильтоновым^[3].

J₃ является тривиальным вариантом графа Петерсена, полученный путём применения преобразования треугольник-звезда к графу Петерсена, а затем заменой одной из вершин треугольником. Этот граф известен также как граф Титце^[4]. Чтобы избежать тривиальных случаев, обычно графы с обхватом меньше 5 не рассматриваются как снарки. Если следовать этим ограничениям, J₃ снарком не является.

Галерея

хроматическое число цветка J₅ равно 3
хроматический индекс цветка J₅ равен 4.
Первоначальное представление цветка J₅.

Примечания

↑ Isaacs R. Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable // Amer. Math : Monthly. — 1975. — Т. 82. — С. 221–239.
↑ Weisstein, Eric W. Flower Snark (англ.) на сайте Wolfram MathWorld.
↑ Weisstein, Eric W. Hypohamiltonian Graph (англ.) на сайте Wolfram MathWorld.
↑ L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14, вып. 1. — С. 57—68. — doi:10.1007/BF02023582.

Похожие исследовательские статьи

Граф Петерсена — неориентированный граф с 10 вершинами и 15 рёбрами; достаточно простой граф, используемый в качестве примера и контрпримера для многих задач в теории графов.

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

В теории графов нечётные графы O_n — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.

В теории графов графом МакГи, или (3-7)-клеткой, называется 3-регулярный граф с 24 вершинами и 36 рёбрами.

<span class="mw-page-title-main">Граф Дезарга</span> дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами

Граф Дезарга — дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами. Назван в честь Жерара Дезарга. Возникает в некоторых комбинаторных построениях, имеет высокую степень симметрии, это единственный известный непланарный кубический частичный куб и применяется в химических базах данных.

Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.

Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.

В теории графов снарк Уоткинса — снарк с 50 вершинами и 75 рёбрами. Открыт Джоном Д. Уоткинсом в 1989 году.

Снарк Блануши — 3-регулярный граф с 18 вершинами и 27 рёбрами. Существуют два таких графа. Носят имя нашедшего оба этих графа в 1946 году югославского математика Данило Блануши.

Граф Турана T(n,r) — это граф, образованный разложением n вершин на r подмножеств, с как можно близким размером, и вершины в этом графе соединены ребром, если они принадлежат разным подмножествам. Граф будет иметь $\text{[math]}$ подмножеств размером $\text{[math]}$ и $\text{[math]}$ подмножеств размером $\text{[math]}$ . Таким образом, это полный r-дольный граф

\text{[math]}

Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк. Открыт Дьёрдьем Секерешем в 1973 году.

Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.

Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.

<span class="mw-page-title-main">Граф Титце</span> неориентированный кубический граф с 12 вершинами и 18 рёбрами

В теории графов граф Титце — это неориентированный кубический граф с 12 вершинами и 18 рёбрами. Граф назван именем Генриха Титце, показавшего в 1910 году, что ленту Мёбиуса можно разделить на шесть областей, касающихся друг друга — три вдоль границы ленты и три вдоль центральной линии — а потому для графов, допускающих вложение в ленту Мёбиуса, может потребоваться шесть цветов. Граничные сегменты областей Титца разделения ленты Мёбиуса образуют вложение графа Титце.

Двойное покрытие циклами в теории графов — множество циклов в неориентированном графе, которое включает в себя каждое ребро ровно два раза. Например, любой полиэдральный граф образован из вершин и рёбер выпуклого многогранника, грани же при этом образуют двойное покрытие циклами: каждое ребро принадлежит ровно двум граням.

В теории графов лестница L_n — планарный неориентированный граф с 2n вершинами и n+2(n-1) рёбрами.

Граф призмы — рёберный граф одной из призм.

Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.

Снарк «двойная звезда» — снарк с 30 вершинами и 45 рёбрами.

<span class="mw-page-title-main">Снарк Лупикайна</span>

Снарки Лупикайна — это два снарка, оба с 22 вершинами и 33 рёбрами. Для этих снарков встречается также название Снарки Голдберга — Лупикайна. Название «снарки Лупикайна» ввёл Айзекс в статье 1978 года, в которой он описал их построение.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.