Снарк «Цветок»
| Снарки «Цветок» J3, J5 и J7. | |
 | |
| Вершин |
4n |
|---|---|
| Рёбер |
6n |
| Обхват |
3 для n=3 |
| Хроматическое число |
3 |
| Хроматический индекс |
4 |
| Свойства |
снарк для n≥5 |
| Снарк «Цветок» J5 | |
 | |
| Вершин |
20 |
|---|---|
| Рёбер |
30 |
| Обхват |
5 |
| Хроматическое число |
3 |
| Хроматический индекс |
4 |
| Свойства | |
В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 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 вершинами (последовательность A130315 в OEIS). Цветок J5 является гипогамильтоновым[en][3].
J3 является тривиальным вариантом графа Петерсена, полученный путём применения преобразования треугольник-звезда к графу Петерсена, а затем заменой одной из вершин треугольником. Этот граф известен также как граф Титце[4]. Чтобы избежать тривиальных случаев, обычно графы с обхватом меньше 5 не рассматриваются как снарки. Если следовать этим ограничениям, J3 снарком не является.
Галерея
- Flower snark 3COL.svg
хроматическое число цветка J5 равно 3
- Flower snark 4color edge.svg
хроматический индекс цветка J5 равен 4.
- Flower snark original.svg
Первоначальное представление цветка J5.
Напишите отзыв о статье "Снарк «Цветок»"
Примечания
- ↑ Isaacs R. Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable // Amer. Math : Monthly. — 1975. — Т. 82. — С. 221–239.
- ↑ Weisstein, Eric W. [mathworld.wolfram.com/FlowerSnark.html Flower Snark] (англ.) на сайте Wolfram MathWorld.
- ↑ Weisstein, Eric W. [mathworld.wolfram.com/HypohamiltonianGraph.html Hypohamiltonian Graph] (англ.) на сайте Wolfram MathWorld.
- ↑ L. Clark, R. Entringer Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14, вып. 1. — С. 57—68. — DOI:10.1007/BF02023582.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Снарк «Цветок»
Долохов серьезно стал метать. О, как ненавидел Ростов в эту минуту эти руки, красноватые с короткими пальцами и с волосами, видневшимися из под рубашки, имевшие его в своей власти… Десятка была дана.– За вами 43 тысячи, граф, – сказал Долохов и потягиваясь встал из за стола. – А устаешь однако так долго сидеть, – сказал он.
– Да, и я тоже устал, – сказал Ростов.
Долохов, как будто напоминая ему, что ему неприлично было шутить, перебил его: Когда прикажете получить деньги, граф?
Ростов вспыхнув, вызвал Долохова в другую комнату.
– Я не могу вдруг заплатить всё, ты возьмешь вексель, – сказал он.
– Послушай, Ростов, – сказал Долохов, ясно улыбаясь и глядя в глаза Николаю, – ты знаешь поговорку: «Счастлив в любви, несчастлив в картах». Кузина твоя влюблена в тебя. Я знаю.
«О! это ужасно чувствовать себя так во власти этого человека», – думал Ростов. Ростов понимал, какой удар он нанесет отцу, матери объявлением этого проигрыша; он понимал, какое бы было счастье избавиться от всего этого, и понимал, что Долохов знает, что может избавить его от этого стыда и горя, и теперь хочет еще играть с ним, как кошка с мышью.
– Твоя кузина… – хотел сказать Долохов; но Николай перебил его.
– Моя кузина тут ни при чем, и о ней говорить нечего! – крикнул он с бешенством.
– Так когда получить? – спросил Долохов.
– Завтра, – сказал Ростов, и вышел из комнаты.
Сказать «завтра» и выдержать тон приличия было не трудно; но приехать одному домой, увидать сестер, брата, мать, отца, признаваться и просить денег, на которые не имеешь права после данного честного слова, было ужасно.
Дома еще не спали. Молодежь дома Ростовых, воротившись из театра, поужинав, сидела у клавикорд. Как только Николай вошел в залу, его охватила та любовная, поэтическая атмосфера, которая царствовала в эту зиму в их доме и которая теперь, после предложения Долохова и бала Иогеля, казалось, еще более сгустилась, как воздух перед грозой, над Соней и Наташей. Соня и Наташа в голубых платьях, в которых они были в театре, хорошенькие и знающие это, счастливые, улыбаясь, стояли у клавикорд. Вера с Шиншиным играла в шахматы в гостиной. Старая графиня, ожидая сына и мужа, раскладывала пасьянс с старушкой дворянкой, жившей у них в доме. Денисов с блестящими глазами и взъерошенными волосами сидел, откинув ножку назад, у клавикорд, и хлопая по ним своими коротенькими пальцами, брал аккорды, и закатывая глаза, своим маленьким, хриплым, но верным голосом, пел сочиненное им стихотворение «Волшебница», к которому он пытался найти музыку.
Волшебница, скажи, какая сила
Влечет меня к покинутым струнам;
Какой огонь ты в сердце заронила,
Какой восторг разлился по перстам!
Пел он страстным голосом, блестя на испуганную и счастливую Наташу своими агатовыми, черными глазами.
– Прекрасно! отлично! – кричала Наташа. – Еще другой куплет, – говорила она, не замечая Николая.
