Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Снарк в теорії графів це зв язний кубічний граф без мостів з хроматичним індексом 4 Іншими словами це граф з надмірною з

Снарк (теорія графів)

Снарк (теорія графів)

Снарк в теорії графів — це зв'язний кубічний граф без мостів з хроматичним індексом 4. Іншими словами, це граф з надмірною зв'язністю — усунення будь-якого ребра не призведе до розбиття графу, також кожна вершина має три сусідні вершини і ребра не можна розфарбувати тільки в три кольори, так щоб два ребра одного кольору не сходилися в одній вершині. (З теореми Візінга хроматичний індекс кубічного графу дорівнює 3 або 4.) Щоб уникнути тривіальних випадків, до снарків не відносять графи, які мають обхват менше 5.

image
Граф Петерсена є найменшим снарком — всього 10 вершин.
image
Снарк «Квітка» J5 — один з шести снарків з 20 вершинами.

Вважається, що незважаючи на просте визначення і тривалу історію вивчення, властивості і структура снарка маловідомі.

image

При вивченні різних важливих і складних проблем теорії графів (таких, як [en] і гіпотеза про 5-потік) трапляються цікаві, але в чомусь дивні графи, які називаються снарками. Всупереч своїй простому визначенню … і більш ніж віковому вивченню, їх властивості та структура здебільшого залишаються невідомими.

Оригінальний текст (англ.)
In the study of various important and difficult problems in graph theory (such as the Cycle double cover conjecture and the 5-Flow Conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown.
 image

Історія

image
Снарк Секереша

Пітер Тет вперше зацікавився снарками в 1880 році, коли він довів, що теорема про чотири фарби еквівалентна твердженням, що ніякий снарк не є планарним. Першим відомим снарком став граф Петерсена, знайдений в 1898 році. У 1946 році югославський математик [en] знайшов ще два снарки, обидва з 18 вершинами, що отримали назву Снарк Блануші. Четвертого снарка знайшов двома роками пізніше Татт, який працював під псевдонімом Бланш Декарт (Blanche Descartes), і це був граф порядку 210 У 1973 році Дьйордь Секереш знайшов п'ятий снарк — Снарк Секереша. У 1975 році [en] узагальнив метод Блануші для побудови двох нескінченних родин снарків — квіти і BDS (снарк Блануші — Декарта — Секереша), сімейство, що включає два снарки Блануші, снарк Декарта і снарк Секереша. Айзекс виявив також снарк з 30 вершинами, що не належить сімейству BDS і не є квіткою — подвійну зірку.

Термін «снарк» увів Мартін Гарднер 1976 року за назвою невловимої істоти «Снарк» з поеми «Полювання на Снарка» Льюїса Керролла.

Властивості

Всі снарки є негамільтоновими і більшість з відомих снарків є [en] — видалення будь-якої окремої вершини дає гамильтонов підграф. Гіпогамільтонові снарки повинні бути бікритичними — видалення будь-яких двох вершин дає підграф, розфарбовуваний реберно в 3 кольори.

Було показано, що число снарків для заданого числа вершин обмежена експоненційної функцією. (Будучи кубічними графами, всі снарки повинні мати парне число вершин.) OEIS послідовність A130315 містить число нетривіальних снарків з 2n вершинами для малих значень n.

[en] стверджує, що в будь-якому графі без мостів можна знайти набір циклів, що покривають кожне ребро двічі, або, що еквівалентно, що граф можна вкласти в поверхню таким чином, що всі грані будуть простими циклами. Снарки утворюють важкий випадок для цієї гіпотези — якщо вона правильна для снарків, вона правильна для всіх графів. У зв'язку з цим Бранко Ґрюнбаум висловив гіпотезу, що не можна вкласти будь-який снарк в поверхню таким способом, що всі грані є простими циклами і при цьому дві будь-яких межі або не мають спільних ребер, або мають одне спільне ребро. Однак Мартін Кохол знайшов контрприклад до цієї гіпотези Ґрюнбаум.

Теорема про снарки

Татт висловив гіпотезу, що будь-який снарк має граф Петерсена як мінор. Таким чином, він припустив, що найменший снарк, граф Петерсена, можна отримати з будь-якого іншого снарка шляхом стягування деяких ребер і видалення інших. Що еквівалентно (оскільки граф Петерсена має максимальний степінь три) твердженню, що будь-який снарк містить підграф, який можна отримати з графу Петерсена шляхом ділення деяких ребер. Ця гіпотеза є посиленням теореми про чотири фарби, оскільки будь-який граф, що містить граф Петерсена як мінору, не може бути планарним. У 1999 році [en], [en], [en] і [en] оголосили про доведення гіпотези, однак за станом на 2012 рік доведення так і не опубліковано.

Татт також запропонував як гіпотезу узагальнену теорему про снарки для довільних графів — будь-який граф без мостів, що не має графу Петерсена як мінору, має ніде не нульовий 4-потік. Що означає, що ребрам графу можна задати напрямки і позначити числами з множини {1, 2, 3} так, що сума вхідних чисел мінус сума вихідних в кожній вершині ділиться на чотири. Як показав Татт, таке призначення для кубічних графів існує в тому і тільки в тому випадку, коли ребра можна розфарбувати в три кольори, так що в цьому випадку гіпотеза випливає з теореми про снарки. Однак гіпотеза залишається відкритою для інших графів (НЕ кубічних).

Список снарків

Список всіх снарків з 36 вершинами, за винятком снарка з 36 вершинами і обхватом 4, був створений Гуннаром Брінкманном, Яном Гедгебером, Джонасом Хегглундом і Класом Маркстремом в 2012 році.

Примітки

  1. Chladný, Miroslav; Škoviera, Martin (2010), Factorisation of snarks, , 17: R32.
  2. P. G. Tait. Remarks on the colourings of maps // Proc. R. Soc. Edinburgh. — 1880. — Т. 10. — С. 729.
  3. Danilo Blanuša. Problem četiriju boja // Glasnik Mat. Fiz. Astr. Ser II. — 1946. — Т. 1. — С. 31–42.
  4. Blanche Descartes, Network-colourings, The Mathematical Gazette (London) 32, 67-69, 1948.
  5. Martin Gardner, The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications, Springer, 2007, ,
  6. G. Szekeres. Polyhedral decompositions of cubic graphs // Bull. Austral. Math. Soc.. — 1973. — Т. 8, вип. 3. — С. 367–387. — DOI:10.1017/S0004972700042660.
  7. R. Isaacs. Infinite families of non-trivial trivalent graphs which are not Tait-colorable // American Mathematical Monthly. — 1975. — Т. 82, вип. 3. — С. 221–239. — DOI:10.2307/2319844. — JSTOR 2319844.
  8. Martin Gardner.  // Scientific American. — 1976. — Т. 4, вип. 234. — С. 126–130.
  9. Steffen E. Classification and characterizations of snarks // . — 1998. — Т. 188, вип. 1–3. — С. 183–203. — DOI:10.1016/S0012-365X(97)00255-0.
  10. Steffen E. On bicritical snarks // Math. Slovaca. — 2001. — Т. 51, вип. 2. — С. 141–150.
  11. Z. Skupień. 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. — Electronic Notes in Discrete Mathematics. — 2007. — Т. 28. — С. 417–424. — DOI:10.1016/j.endm.2007.01.059.
  12. послідовність A130315 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
  13. F. Jaeger. Annals of Discrete Mathematics 27 – Cycles in Graphs. — 1985. — Т. 27. — С. 1–12. — (North-Holland Mathematics Studies). — . — DOI:10.1016/S0304-0208(08)72993-1..
  14. Martin Kochol. Journal of Combinatorial Theory, Series B. — 1996. — Т. 67. — С. 34–47.
  15. Martin Kochol. Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani. — 2009. — Т. 5417. — С. 319–323..
  16. Martin Kochol. Proceedings of the American Mathematical Society. — 2009. — Т. 137. — С. 1613–1619.
  17. Robin Thomas. Surveys in Combinatorics, 1999. — Cambridge University Press, 1999. — С. 201–222.
  18. Sarah-Marie Belcastro. The continuing saga of snarks // The College Mathematics Journal. — 2012. — Т. 43, вип. 1. — С. 82–87. — DOI:10.4169/college.math.j.43.1.082.. Див. також гіпотезу Хадвігера і результати, пов'язані з розфарбовуванням мінорів графу.
  19. 4-flow conjecture [ 8 лютого 2012 у Wayback Machine.], Open Problem Garden.
  20. Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström. Generation and Properties of Snarks. — 2012.

Посилання

  • Weisstein, Eric W. Snark(англ.) на сайті Wolfram MathWorld.
  • Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (preprint). «». Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia.
Ця стаття має кілька недоліків. Будь ласка, допоможіть удосконалити її або обговоріть ці проблеми на . checktranslate
Ця стаття містить текст, що не відповідає . Будь ласка, допоможіть удосконалити цю статтю, погодивши стиль викладу зі . Можливо, містить зауваження щодо потрібних змін. (квітень 2016)

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Snark v teoriyi grafiv ce zv yaznij kubichnij graf bez mostiv z hromatichnim indeksom 4 Inshimi slovami ce graf z nadmirnoyu zv yaznistyu usunennya bud yakogo rebra ne prizvede do rozbittya grafu takozh kozhna vershina maye tri susidni vershini i rebra ne mozhna rozfarbuvati tilki v tri kolori tak shob dva rebra odnogo koloru ne shodilisya v odnij vershini Z teoremi Vizinga hromatichnij indeks kubichnogo grafu dorivnyuye 3 abo 4 Shob uniknuti trivialnih vipadkiv do snarkiv ne vidnosyat grafi yaki mayut obhvat menshe 5 Graf Petersena ye najmenshim snarkom vsogo 10 vershin Snark Kvitka J5 odin z shesti snarkiv z 20 vershinami Vvazhayetsya sho nezvazhayuchi na proste viznachennya i trivalu istoriyu vivchennya vlastivosti i struktura snarka malovidomi Pri vivchenni riznih vazhlivih i skladnih problem teoriyi grafiv takih yak en i gipoteza pro 5 potik traplyayutsya cikavi ale v chomus divni grafi yaki nazivayutsya snarkami Vsuperech svoyij prostomu viznachennyu i bilsh nizh vikovomu vivchennyu yih vlastivosti ta struktura zdebilshogo zalishayutsya nevidomimi Originalnij tekst angl In the study of various important and difficult problems in graph theory such as the Cycle double cover conjecture and the 5 Flow Conjecture one encounters an interesting but somewhat mysterious variety of graphs called snarks In spite of their simple definition and over a century long investigation their properties and structure are largely unknown IstoriyaSnark Sekeresha Piter Tet vpershe zacikavivsya snarkami v 1880 roci koli vin doviv sho teorema pro chotiri farbi ekvivalentna tverdzhennyam sho niyakij snark ne ye planarnim Pershim vidomim snarkom stav graf Petersena znajdenij v 1898 roci U 1946 roci yugoslavskij matematik en znajshov she dva snarki obidva z 18 vershinami sho otrimali nazvu Snark Blanushi Chetvertogo snarka znajshov dvoma rokami piznishe Tatt yakij pracyuvav pid psevdonimom Blansh Dekart Blanche Descartes i ce buv graf poryadku 210 U 1973 roci Djord Sekeresh znajshov p yatij snark Snark Sekeresha U 1975 roci en uzagalniv metod Blanushi dlya pobudovi dvoh neskinchennih rodin snarkiv kviti i BDS snark Blanushi Dekarta Sekeresha simejstvo sho vklyuchaye dva snarki Blanushi snark Dekarta i snark Sekeresha Ajzeks viyaviv takozh snark z 30 vershinami sho ne nalezhit simejstvu BDS i ne ye kvitkoyu podvijnu zirku Termin snark uviv Martin Gardner 1976 roku za nazvoyu nevlovimoyi istoti Snark z poemi Polyuvannya na Snarka Lyuyisa Kerrolla VlastivostiVsi snarki ye negamiltonovimi i bilshist z vidomih snarkiv ye en vidalennya bud yakoyi okremoyi vershini daye gamiltonov pidgraf Gipogamiltonovi snarki povinni buti bikritichnimi vidalennya bud yakih dvoh vershin daye pidgraf rozfarbovuvanij reberno v 3 kolori Bulo pokazano sho chislo snarkiv dlya zadanogo chisla vershin obmezhena eksponencijnoyi funkciyeyu Buduchi kubichnimi grafami vsi snarki povinni mati parne chislo vershin OEIS poslidovnist A130315 mistit chislo netrivialnih snarkiv z 2n vershinami dlya malih znachen n en stverdzhuye sho v bud yakomu grafi bez mostiv mozhna znajti nabir cikliv sho pokrivayut kozhne rebro dvichi abo sho ekvivalentno sho graf mozhna vklasti v poverhnyu takim chinom sho vsi grani budut prostimi ciklami Snarki utvoryuyut vazhkij vipadok dlya ciyeyi gipotezi yaksho vona pravilna dlya snarkiv vona pravilna dlya vsih grafiv U zv yazku z cim Branko Gryunbaum visloviv gipotezu sho ne mozhna vklasti bud yakij snark v poverhnyu takim sposobom sho vsi grani ye prostimi ciklami i pri comu dvi bud yakih mezhi abo ne mayut spilnih reber abo mayut odne spilne rebro Odnak Martin Kohol znajshov kontrpriklad do ciyeyi gipotezi Gryunbaum Teorema pro snarkiTatt visloviv gipotezu sho bud yakij snark maye graf Petersena yak minor Takim chinom vin pripustiv sho najmenshij snark graf Petersena mozhna otrimati z bud yakogo inshogo snarka shlyahom styaguvannya deyakih reber i vidalennya inshih Sho ekvivalentno oskilki graf Petersena maye maksimalnij stepin tri tverdzhennyu sho bud yakij snark mistit pidgraf yakij mozhna otrimati z grafu Petersena shlyahom dilennya deyakih reber Cya gipoteza ye posilennyam teoremi pro chotiri farbi oskilki bud yakij graf sho mistit graf Petersena yak minoru ne mozhe buti planarnim U 1999 roci en en en i en ogolosili pro dovedennya gipotezi odnak za stanom na 2012 rik dovedennya tak i ne opublikovano Tatt takozh zaproponuvav yak gipotezu uzagalnenu teoremu pro snarki dlya dovilnih grafiv bud yakij graf bez mostiv sho ne maye grafu Petersena yak minoru maye nide ne nulovij 4 potik Sho oznachaye sho rebram grafu mozhna zadati napryamki i poznachiti chislami z mnozhini 1 2 3 tak sho suma vhidnih chisel minus suma vihidnih v kozhnij vershini dilitsya na chotiri Yak pokazav Tatt take priznachennya dlya kubichnih grafiv isnuye v tomu i tilki v tomu vipadku koli rebra mozhna rozfarbuvati v tri kolori tak sho v comu vipadku gipoteza viplivaye z teoremi pro snarki Odnak gipoteza zalishayetsya vidkritoyu dlya inshih grafiv NE kubichnih Spisok snarkivGraf Petersena 10 vershin vidkritij v 1898 roci Graf Titce 12 vershin ale z obhvatom 3 zazvichaj ne vvazhayetsya snarkom Snark Blanushi dva snarki z 18 vershinami vidkriti v 1946 roci Snark Dekarta 210 vershin vidkritij piznishe Tatu en v 1948 roci Snark Podvijna zirka 30 vershin Snark Sekeresha 50 vershin vidkritij v 1973 roci Snark Uotkinsa 50 vershin vidkritij v 1989 Snark Kvitka neskinchenne simejstvo z 20 28 36 44 vershinami vidkrito v 1975 roci Spisok vsih snarkiv z 36 vershinami za vinyatkom snarka z 36 vershinami i obhvatom 4 buv stvorenij Gunnarom Brinkmannom Yanom Gedgeberom Dzhonasom Hegglundom i Klasom Markstremom v 2012 roci PrimitkiChladny Miroslav Skoviera Martin 2010 Factorisation of snarks 17 R32 P G Tait Remarks on the colourings of maps Proc R Soc Edinburgh 1880 T 10 S 729 Danilo Blanusa Problem cetiriju boja Glasnik Mat Fiz Astr Ser II 1946 T 1 S 31 42 Blanche Descartes Network colourings The Mathematical Gazette London 32 67 69 1948 Martin Gardner The Last Recreations Hydras Eggs and Other Mathematical Mystifications Springer 2007 ISBN 0 387 25827 2 ISBN 978 0 387 25827 0 G Szekeres Polyhedral decompositions of cubic graphs Bull Austral Math Soc 1973 T 8 vip 3 S 367 387 DOI 10 1017 S0004972700042660 R Isaacs Infinite families of non trivial trivalent graphs which are not Tait colorable American Mathematical Monthly 1975 T 82 vip 3 S 221 239 DOI 10 2307 2319844 JSTOR 2319844 Martin Gardner Scientific American 1976 T 4 vip 234 S 126 130 Steffen E Classification and characterizations of snarks 1998 T 188 vip 1 3 S 183 203 DOI 10 1016 S0012 365X 97 00255 0 Steffen E On bicritical snarks Math Slovaca 2001 T 51 vip 2 S 141 150 Z Skupien 6th Czech Slovak International Symposium on Combinatorics Graph Theory Algorithms and Applications Electronic Notes in Discrete Mathematics 2007 T 28 S 417 424 DOI 10 1016 j endm 2007 01 059 poslidovnist A130315 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS F Jaeger Annals of Discrete Mathematics 27 Cycles in Graphs 1985 T 27 S 1 12 North Holland Mathematics Studies ISBN 978 0 444 87803 8 DOI 10 1016 S0304 0208 08 72993 1 Martin Kochol Journal of Combinatorial Theory Series B 1996 T 67 S 34 47 Martin Kochol Graph Drawing 2008 Editors I G Tollis M Patrignani 2009 T 5417 S 319 323 Martin Kochol Proceedings of the American Mathematical Society 2009 T 137 S 1613 1619 Robin Thomas Surveys in Combinatorics 1999 Cambridge University Press 1999 S 201 222 Sarah Marie Belcastro The continuing saga of snarks The College Mathematics Journal 2012 T 43 vip 1 S 82 87 DOI 10 4169 college math j 43 1 082 Div takozh gipotezu Hadvigera i rezultati pov yazani z rozfarbovuvannyam minoriv grafu 4 flow conjecture 8 lyutogo 2012 u Wayback Machine Open Problem Garden Gunnar Brinkmann Jan Goedgebeur Jonas Hagglund and Klas Markstrom Generation and Properties of Snarks 2012 PosilannyaWeisstein Eric W Snark angl na sajti Wolfram MathWorld Alen Orbanic Tomaz Pisanski Milan Randic and Brigite Servatius preprint Institute for Mathematics Physics and Mechanics in Ljubljana Slovenia Cya stattya maye kilka nedolikiv Bud laska dopomozhit udoskonaliti yiyi abo obgovorit ci problemi na checktranslateCya stattya mistit tekst sho ne vidpovidaye enciklopedichnomu stilyu Bud laska dopomozhit udoskonaliti cyu stattyu pogodivshi stil vikladu zi stilistichnimi pravilami Vikipediyi Mozhlivo mistit zauvazhennya shodo potribnih zmin kviten 2016

Дата публікації:
Топ