В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.
Как и все снарки, цветы являются связными кубическими графами без мостов с хроматическим индексом 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 рёбрами. Это один из 6 снарков с 20 вершинами (). Цветок J5 является гипогамильтоновым.
J3 является тривиальным вариантом графа Петерсена, полученный путём применения преобразования треугольник-звезда к графу Петерсена, а затем заменой одной из вершин треугольником. Этот граф известен также как граф Титце. Чтобы избежать тривиальных случаев, обычно графы с обхватом меньше 5 не рассматриваются как снарки. Если следовать этим ограничениям, J3 снарком не является.
Галерея
Примечания
Категория:Теория графов Категория:Регулярные графы Категория:Параметрические семейства графов