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

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

Історія

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

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

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

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

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

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

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

Список снарків Граф Петерсена (10 вершин, відкритий в 1898 році) Граф Тітце (12 вершин, але з обхватом 3, зазвичай не вважається снарком) Снарк Блануші (два снарки з 18 вершинами, відкриті в 1946 році) Снарк Декарта (210 вершин, відкритий пізніше Тату [en] в 1948 році) Снарк «Подвійна зірка» (30 вершин) Снарк Секереша (50 вершин, відкритий в 1973 році) Снарк Уоткінса (50 вершин, відкритий в 1989) Снарк «Квітка» (нескінченне сімейство з 20, 28, 36, 44 … вершинами, відкрито в 1975 році)

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

Примітки

Посилання

Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (preprint). «Blanuša Double». Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia.