Гіпотеза Тета (теорія графів)
Гіпотеза Тета — спростована математична гіпотеза про те, що будь-який 3-зв'язний планарний кубічний граф має гамільтонів цикл, що проходить через усі його вершини .
Висловлена в 1884 році Пітером Тетом [1], спростована в 1946 році Вільямом Таттом [2], який побудував контрприклад з 25 гранями, 69 ребрами і 46 вершинами — граф Татта. Пізніше, 1988 року, знайдено контрприклад з 21 гранню, 57 ребрами і 38 вершинами і доведено, що цей граф мінімальний[3].
Умова 3-регулярності (3-регулярні графи називаються кубічними) необхідна, оскільки існують багатогранники, такі як ромбододекаедр. Ромбододекаедр утворює двочастковий граф і будь-який гамільтонів цикл у цьому графі має почергово змінювати частки (сторони) графа, так що число вершин в частках має бути однаковим, проте граф має шість вершин степеня 4 на одному боці і вісім вершин степеня 3 на іншому.
Якби гіпотеза була правильна, то з неї випливав би простий розв'язок задачі чотирьох фарб. Згідно з Тетом, задача чотирьох фарб еквівалентна задачі пошуку реберної 3-розмальовки кубічних планарних графів без мостів. У гамільтоновому кубічному планарному графі таку розмальовку ребер легко знайти — по черзі використовуємо два кольори для розмальовування ребер уздовж гамільтонового циклу, а третім кольором пофарбуємо решту ребер. Альтернативно можна побудувати розмальовку в чотири кольори граней гамільтонового кубічного планарного графа прямо, якщо використовувати два кольори для розмальовування граней всередині циклу і два кольори для граней зовні.
Ключем контрприкладу є граф, який зараз називають фрагментом Татта. Якщо цей фрагмент є частиною більшого графа, будь-який гамільтонів цикл має проходити через (висяче) ребро при верхній вершині (і через одне з нижніх ребер). Шлях не може увійти через нижнє ребро і вийти через інше нижнє ребро.
Фрагмент Татта використовується для побудови негамільтонового графа Татта, якщо скласти докупи три таких фрагмента. «Обов'язкові» ребра фрагментів, які повинні бути частинами гамільтонового шляху через фрагмент, з'єднані в центрі. Оскільки будь-який цикл може проходити тільки через два з трьох ребер у центрі, гамільтонового циклу для цього графа бути не може. Одержаний граф Татта є 3-зв'язним і планарним, так що він є графом багатогранника за теоремою Штайніца. Граф має 25 граней, 69 ребер і 46 вершин. Геометрично граф можна отримати з тетраедра (грані якого відповідають чотирьом великим граням на малюнку — три грані між парами фрагментів, а четверта грань є зовнішньою) шляхом багаторазового усічення трьох його вершин.
Як показали Голтон і Маккей 1988 року[3], існує рівно шість негамільтонових 3-регулярних багатогранників з 38 вершинами. Багатогранники утворені заміною двох вершин п'ятикутної призми тим самим фрагментом з прикладу Татта.
- Теорема Грінберга[ru] — необхідна умова існування гамільтонового циклу, яку можна використати, щоб показати, що граф є контрприкладом до гіпотези Тета.
- Гіпотеза Барнета — залишається відкритим удосконаленням гіпотези Тета; гіпотеза стверджує, що будь-який двочастковий кубічний багатогранний граф є гамільтоновим.[4]
- ↑ Tait, 1884.
- ↑ Tutte, 1946.
- ↑ а б Holton, McKay, 1988.
- ↑ Barnette's conjecture [Архівовано 14 грудня 2021 у Wayback Machine.], the Open Problem Garden, retrieved 2009-10-12.
- D. A. Holton, B. D. McKay. The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices // Journal of Combinatorial Theory, Series B. — 1988. — Т. 45, вип. 3. — С. 305–319. — DOI:10.1016/0095-8956(88)90075-5.
- P. G. Tait. Listing's Topologie // Philosophical Magazine (5th ser.). — 1884. — Т. 17. — С. 30–46. Статья перепечатана в Scientific Papers, том II, стр. 85-98.
- W. T. Tutte. On Hamiltonian circuits // Journal of the London Mathematical Society. — 1946. — Т. 21, вип. 2. — С. 98–101. — DOI:10.1112/jlms/s1-21.2.98.
- Weisstein, Eric W. Tait's Hamiltonian Graph Conjecture(англ.) на сайті Wolfram MathWorld.