Русская Википедия:Снарк «Цветок»
В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году[1].
Как и все снарки, цветы являются связными кубическими графами без мостов с хроматическим индексом 4. Они не планарны и не гамильтоновы.
Построение
Цветок Jn можно построить следующим процессом:
- Образуем n копий звезды с 4 вершинами. Обозначим центр каждой звезды через Ai, а внешние вершины — через Bi, Ci и Di. Результатом будет несвязный граф с 4n вершинами и 3n рёбрами (Ai-Bi, Ai-Ci и Ai-Di для 1≤i≤n).
- Образуем цикл длины n (B1... Bn). Это добавит n рёбер.
- Образуем цикл длины 2n (C1... CnD1... Dn). Это добавит ещё 2n рёбер.
По построению цветок Jn является кубическим графом с 4n вершинами и 6n рёбрами. Чтобы получить необходимые свойства, n должен быть нечётным.
Специальные случаи
Название «цветок» иногда используется для J5, снарка с 20 вершинами и 30 рёбрами[2]. Это один из 6 снарков с 20 вершинами (Шаблон:OEIS). Цветок J5 является гипогамильтоновым[3].
J3 является тривиальным вариантом графа Петерсена, полученный путём применения преобразования треугольник-звезда к графу Петерсена, а затем заменой одной из вершин треугольником. Этот граф известен также как граф Титце[4]. Чтобы избежать тривиальных случаев, обычно графы с обхватом меньше 5 не рассматриваются как снарки. Если следовать этим ограничениям, J3 снарком не является.
Галерея
-
хроматическое число цветка J5 равно 3
-
хроматический индекс цветка J5 равен 4.
-
Первоначальное представление цветка J5.
Примечания
