У теорії графів, снарк «Квітка» утворює нескінченне сімейство снарків, відкрите [en] у 1975 році.
Снарк «Квітка» | |
---|---|
Снарк «Квітка» J3, J5 та J7. | |
(Вершин) | 4n |
(Ребер) | 6n |
(Обхват) | 3 для n=3 5 для n=5 6 для n≥7 |
Хроматичне число | 3 |
Хроматичний індекс | 4 |
Число черг | 2 для n=5 2 для n=7 |
Властивості | Снарк для n≥5 |
Позначення | Jn з непарним n |
Снарк «Квітка» J5 | |
---|---|
Снарк «Квітка» J5. | |
(Вершин) | 20 |
(Ребер) | 30 |
(Обхват) | 5 |
Хроматичне число | 3 |
Хроматичний індекс | 4 |
Властивості | Снарк [en] |
Як і інші снарки, снарк «Квітка» зв'язний кубічний граф без мостів з хроматичним індексом рівним 4. Снарк «Квітка» є негамільтонованим і непланарним. Снарки «Квітка» J5 and J7 мають книжкове вкладення 3 та число черг 2.
Побудова
Снарк «Квітка» 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 вершинами (послідовність A130315 в OEIS). Снарк «Квітка» J5 є [en].
J3 є тривіальною варіацією графу Петерсена, створеного шляхом заміни однієї з його вершин трикутником. Цей граф також відомий як граф Тітце. Для того, щоб уникнути тривіальних випадків, снарки, як правило, обмежені, щоб мати обхват не менше 5. За такого обмеження, J3 не є снарком.
Галерея
- Хроматичне число снарка «Квітка»J5 3.
- Хроматичний індекс снарка «Квітка» J5 4.
- Оригінальне представлення снарка «Квітка» J5.
Примітки
- Isaacs, R. «Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable.» Amer. Math. Monthly 82, 221–239, 1975.
- Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
- Weisstein, Eric W. Flower Snark(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Hypohamiltonian Graph(англ.) на сайті Wolfram MathWorld.
- Clark, L.; Entringer, R. (1983), Smallest maximally nonhamiltonian graphs, Periodica Mathematica Hungarica, 14 (1): 57—68, doi:10.1007/BF02023582.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi grafiv snark Kvitka utvoryuye neskinchenne simejstvo snarkiv vidkrite en u 1975 roci Snark Kvitka Snark Kvitka J3 J5 ta J7 Vershin4nReber6nObhvat3 dlya n 3 5 dlya n 5 6 dlya n 7Hromatichne chislo3Hromatichnij indeks4Chislo cherg2 dlya n 5 2 dlya n 7VlastivostiSnark dlya n 5PoznachennyaJn z neparnim n Snark Kvitka J5Snark Kvitka J5 Vershin20Reber30Obhvat5Hromatichne chislo3Hromatichnij indeks4VlastivostiSnark en Yak i inshi snarki snark Kvitka zv yaznij kubichnij graf bez mostiv z hromatichnim indeksom rivnim 4 Snark Kvitka ye negamiltonovanim i neplanarnim Snarki Kvitka J5 and J7 mayut knizhkove vkladennya 3 ta chislo cherg 2 PobudovaSnark Kvitka Jn mozhna pobuduvati za dopomogoyu nastupnogo procesu Pobuduyemo n kopij zirki z 4 vershinami Poznachimo centralni vershini kozhnoyi zirki Ai a zovnishni vershini Bi Ci ta Di Mi otrimali nezv yazni grafi z 4n vershinami ta 3n rebrami Ai Bi Ai Ci ta Ai Di dlya 1 i n Pobuduyemo n cikl B1 Bn Ce dodaye n reber Nareshti pobuduyemo 2n cikl C1 CnD1 Dn Ce dodaye 2n reber Za pobudovoyu snark Kvitka Jn ye kubichnim grafom z 4n vershinami ta 6n rebrami Dlya togo shob mati neobhidni vlastivosti znachennya n maye buti neparnim Osoblivi vipadkiNazva snark Kvitka inodi vikoristovuyetsya dlya J5 yakij ye snarkom z 20 vershinami i 30 rebrami Ce odin z 6 snarkiv z 20 vershinami poslidovnist A130315 v OEIS Snark Kvitka J5 ye en J3 ye trivialnoyu variaciyeyu grafu Petersena stvorenogo shlyahom zamini odniyeyi z jogo vershin trikutnikom Cej graf takozh vidomij yak graf Titce Dlya togo shob uniknuti trivialnih vipadkiv snarki yak pravilo obmezheni shob mati obhvat ne menshe 5 Za takogo obmezhennya J3 ne ye snarkom GalereyaHromatichne chislo snarka Kvitka J5 3 Hromatichnij indeks snarka Kvitka J5 4 Originalne predstavlennya snarka Kvitka J5 PrimitkiIsaacs R Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable Amer Math Monthly 82 221 239 1975 Wolz Jessica Engineering Linear Layouts with SAT Master Thesis University of Tubingen 2018 Weisstein Eric W Flower Snark angl na sajti Wolfram MathWorld Weisstein Eric W Hypohamiltonian Graph angl na sajti Wolfram MathWorld Clark L Entringer R 1983 Smallest maximally nonhamiltonian graphs Periodica Mathematica Hungarica 14 1 57 68 doi 10 1007 BF02023582