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

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

Граф Петерсена є найменшим снарком — всього 10 вершин.

Снарк «Квітка» J₅ — один з шести снарків з 20 вершинами.

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

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

Історія

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

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

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

Властивості

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

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

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

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

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

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

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

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

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