|
Снарк (теорія графів)  Снарк в теорії графів — це зв'язний кубічний граф без мостів з хроматичним індексом 4. Іншими словами, це граф з надмірною зв'язністю — усунення будь-якого ребра не призведе до розбиття графу, також кожна вершина має три сусідні вершини і ребра не можна розфарбувати тільки в три кольори, так щоб два ребра одного кольору не сходилися в одній вершині. (З теореми Візінга хроматичний індекс кубічного графу дорівнює 3 або 4.) Щоб уникнути тривіальних випадків, до снарків не відносять графи, які мають обхват менше 5. Вважається, що незважаючи на просте визначення і тривалу історію вивчення, властивості і структура снарка маловідомі.
Історія Пітер Тет вперше зацікавився снарками в 1880 році, коли він довів, що теорема про чотири фарби еквівалентна твердженням, що ніякий снарк не є планарним[2]. Першим відомим снарком став граф Петерсена, знайдений в 1898 році. У 1946 році югославський математик Данило Блануша[en] знайшов ще два снарки, обидва з 18 вершинами, що отримали назву Снарк Блануші[3]. Четвертого снарка знайшов двома роками пізніше Татт, який працював під псевдонімом Бланш Декарт (Blanche Descartes), і це був граф порядку 210[4][5] У 1973 році Дьйордь Секереш знайшов п'ятий снарк — Снарк Секереша.[6] У 1975 році Айзекс Руфус[en] узагальнив метод Блануші для побудови двох нескінченних родин снарків — квіти і BDS (снарк Блануші — Декарта — Секереша), сімейство, що включає два снарки Блануші, снарк Декарта і снарк Секереша[7]. Айзекс виявив також снарк з 30 вершинами, що не належить сімейству BDS і не є квіткою — подвійну зірку. Термін «снарк» увів Мартін Гарднер 1976 року за назвою невловимої істоти «Снарк» з поеми «Полювання на Снарка» Льюїса Керролла[8]. ВластивостіВсі снарки є негамільтоновими і більшість з відомих снарків є гіпогамільтоновими[en] — видалення будь-якої окремої вершини дає гамильтонов підграф. Гіпогамільтонові снарки повинні бути бікритичними — видалення будь-яких двох вершин дає підграф, розфарбовуваний реберно в 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]. Список снарків
Список всіх снарків з 36 вершинами, за винятком снарка з 36 вершинами і обхватом 4, був створений Гуннаром Брінкманном, Яном Гедгебером, Джонасом Хегглундом і Класом Маркстремом в 2012 році[20]. Примітки
Посилання
|
