Гіпотеза Тета — спростована математична гіпотеза про те, що будь-який 3-зв'язний планарний кубічний граф має гамільтонів цикл, що проходить через усі його вершини .
Висловлена в Пітером Тетом , спростована в Вільямом Таттом , який побудував контрприклад з 25 гранями, 69 ребрами і 46 вершинами — граф Татта. Пізніше, 1988 року, знайдено контрприклад з 21 гранню, 57 ребрами і 38 вершинами і доведено, що цей граф мінімальний.
Умова 3-регулярності (3-регулярні графи називаються кубічними) необхідна, оскільки існують багатогранники, такі як ромбододекаедр. Ромбододекаедр утворює двочастковий граф і будь-який гамільтонів цикл у цьому графі має почергово змінювати частки (сторони) графа, так що число вершин в частках має бути однаковим, проте граф має шість вершин степеня 4 на одному боці і вісім вершин степеня 3 на іншому.
Якби гіпотеза була правильна, то з неї випливав би простий розв'язок задачі чотирьох фарб. Згідно з Тетом, задача чотирьох фарб еквівалентна задачі пошуку реберної 3-розмальовки кубічних планарних графів без мостів. У гамільтоновому кубічному планарному графі таку розмальовку ребер легко знайти — по черзі використовуємо два кольори для розмальовування ребер уздовж гамільтонового циклу, а третім кольором пофарбуємо решту ребер. Альтернативно можна побудувати розмальовку в чотири кольори граней гамільтонового кубічного планарного графа прямо, якщо використовувати два кольори для розмальовування граней всередині циклу і два кольори для граней зовні.
Контрприклад Татта
Ключем контрприкладу є граф, який зараз називають фрагментом Татта. Якщо цей фрагмент є частиною більшого графа, будь-який гамільтонів цикл має проходити через (висяче) ребро при верхній вершині (і через одне з нижніх ребер). Шлях не може увійти через нижнє ребро і вийти через інше нижнє ребро.
Фрагмент Татта використовується для побудови негамільтонового графа Татта, якщо скласти докупи три таких фрагмента. «Обов'язкові» ребра фрагментів, які повинні бути частинами гамільтонового шляху через фрагмент, з'єднані в центрі. Оскільки будь-який цикл може проходити тільки через два з трьох ребер у центрі, гамільтонового циклу для цього графа бути не може. Одержаний граф Татта є 3-зв'язним і планарним, так що він є графом багатогранника за теоремою Штайніца. Граф має 25 граней, 69 ребер і 46 вершин. Геометрично граф можна отримати з тетраедра (грані якого відповідають чотирьом великим граням на малюнку — три грані між парами фрагментів, а четверта грань є зовнішньою) шляхом багаторазового усічення трьох його вершин.
Менші контрприклади
Як показали Голтон і Маккей 1988 року, існує рівно шість негамільтонових 3-регулярних багатогранників з 38 вершинами. Багатогранники утворені заміною двох вершин п'ятикутної призми тим самим фрагментом з прикладу Татта.
Див. також
- [ru] — необхідна умова існування гамільтонового циклу, яку можна використати, щоб показати, що граф є контрприкладом до гіпотези Тета.
- Гіпотеза Барнета — залишається відкритим удосконаленням гіпотези Тета; гіпотеза стверджує, що будь-який двочастковий кубічний багатогранний граф є гамільтоновим.
Примітки
- 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Ne plutati z gipotezami Teta v teoriyi vuzliv Gipoteza Teta sprostovana matematichna gipoteza pro te sho bud yakij 3 zv yaznij planarnij kubichnij graf maye gamiltoniv cikl sho prohodit cherez usi jogo vershini Vislovlena v Piterom Tetom sprostovana v Vilyamom Tattom yakij pobuduvav kontrpriklad z 25 granyami 69 rebrami i 46 vershinami graf Tatta Piznishe 1988 roku znajdeno kontrpriklad z 21 grannyu 57 rebrami i 38 vershinami i dovedeno sho cej graf minimalnij Umova 3 regulyarnosti 3 regulyarni grafi nazivayutsya kubichnimi neobhidna oskilki isnuyut bagatogranniki taki yak rombododekaedr Rombododekaedr utvoryuye dvochastkovij graf i bud yakij gamiltoniv cikl u comu grafi maye pochergovo zminyuvati chastki storoni grafa tak sho chislo vershin v chastkah maye buti odnakovim prote graf maye shist vershin stepenya 4 na odnomu boci i visim vershin stepenya 3 na inshomu Yakbi gipoteza bula pravilna to z neyi viplivav bi prostij rozv yazok zadachi chotiroh farb Zgidno z Tetom zadacha chotiroh farb ekvivalentna zadachi poshuku rebernoyi 3 rozmalovki kubichnih planarnih grafiv bez mostiv U gamiltonovomu kubichnomu planarnomu grafi taku rozmalovku reber legko znajti po cherzi vikoristovuyemo dva kolori dlya rozmalovuvannya reber uzdovzh gamiltonovogo ciklu a tretim kolorom pofarbuyemo reshtu reber Alternativno mozhna pobuduvati rozmalovku v chotiri kolori granej gamiltonovogo kubichnogo planarnogo grafa pryamo yaksho vikoristovuvati dva kolori dlya rozmalovuvannya granej vseredini ciklu i dva kolori dlya granej zovni Kontrpriklad TattaFragment Tatta Klyuchem kontrprikladu ye graf yakij zaraz nazivayut fragmentom Tatta Yaksho cej fragment ye chastinoyu bilshogo grafa bud yakij gamiltoniv cikl maye prohoditi cherez visyache rebro pri verhnij vershini i cherez odne z nizhnih reber Shlyah ne mozhe uvijti cherez nizhnye rebro i vijti cherez inshe nizhnye rebro Kontrpriklad Tatta tri fragmenta Tatta z yednani v centri Fragment Tatta vikoristovuyetsya dlya pobudovi negamiltonovogo grafa Tatta yaksho sklasti dokupi tri takih fragmenta Obov yazkovi rebra fragmentiv yaki povinni buti chastinami gamiltonovogo shlyahu cherez fragment z yednani v centri Oskilki bud yakij cikl mozhe prohoditi tilki cherez dva z troh reber u centri gamiltonovogo ciklu dlya cogo grafa buti ne mozhe Oderzhanij graf Tatta ye 3 zv yaznim i planarnim tak sho vin ye grafom bagatogrannika za teoremoyu Shtajnica Graf maye 25 granej 69 reber i 46 vershin Geometrichno graf mozhna otrimati z tetraedra grani yakogo vidpovidayut chotirom velikim granyam na malyunku tri grani mizh parami fragmentiv a chetverta gran ye zovnishnoyu shlyahom bagatorazovogo usichennya troh jogo vershin Menshi kontrprikladiYak pokazali Golton i Makkej 1988 roku isnuye rivno shist negamiltonovih 3 regulyarnih bagatogrannikiv z 38 vershinami Bagatogranniki utvoreni zaminoyu dvoh vershin p yatikutnoyi prizmi tim samim fragmentom z prikladu Tatta Div takozh ru neobhidna umova isnuvannya gamiltonovogo ciklu yaku mozhna vikoristati shob pokazati sho graf ye kontrprikladom do gipotezi Teta Gipoteza Barneta zalishayetsya vidkritim udoskonalennyam gipotezi Teta gipoteza stverdzhuye sho bud yakij dvochastkovij kubichnij bagatogrannij graf ye gamiltonovim PrimitkiTait 1884 Tutte 1946 Holton McKay 1988 Barnette s conjecture 14 grudnya 2021 u Wayback Machine the Open Problem Garden retrieved 2009 10 12 LiteraturaD A Holton B D McKay The smallest non Hamiltonian 3 connected cubic planar graphs have 38 vertices Journal of Combinatorial Theory Series B 1988 T 45 vip 3 S 305 319 DOI 10 1016 0095 8956 88 90075 5 P G Tait Listing s Topologie Philosophical Magazine 5th ser 1884 T 17 S 30 46 Statya perepechatana v Scientific Papers tom II str 85 98 W T Tutte On Hamiltonian circuits Journal of the London Mathematical Society 1946 T 21 vip 2 S 98 101 DOI 10 1112 jlms s1 21 2 98 PosilannyaWeisstein Eric W Tait s Hamiltonian Graph Conjecture angl na sajti Wolfram MathWorld