Гіпотеза Барнетте

Гіпо́теза Ба́рнетта є припущенням у теорії графів, розділ математики, щодо гамільтонових циклів у графах. Вона названа на честь , почесного професора Каліфорнійського університету в Девісі. У ньому йдеться про те, що кожен двочастковий багатогранний граф з трьома ребрами на вершині має гамільтонів цикл.

Визначення

Плоский граф це неорієнтований граф, який може бути вкладеним до Евклідового простору без перетинань. Планарний граф називається багатогранним графом тоді, і тільки тоді, коли це k-вершинно-зв'язний граф, тобто, якщо не існує двох вершин, таких що видалення одної буде розривати решту графа. Граф є двочастковим, якщо його вершини можуть бути пофарбовані у два різні кольори, такі, що кожне ребро має одну кінцеву точку кожного кольору. Граф є кубічним, якщо кожна вершина є кінцевою точкою рівно трьох ребер. І граф є Гамільтонів, якщо існує цикл, який проходить рівно один раз через кожну з його вершин. Гіпотеза Барнетта стверджує, що кожен кубічний двочастковий граф є гамільтоновим.

За теоремою Штайніца, плоский граф є ребрами й вершинами опуклого політопа тоді, і тільки тоді, коли він багатогранний. Тривимірний поліедрон має кубічний граф тоді, і тільки тоді, коли це простий многогранник. І плоский граф є двочастковим тоді, і тільки тоді, коли в плоскому графі, всі цикли графу довжину. Таким чином, гіпотеза Барнетта може бути сформульована в еквівалентній формі: припустимо, що тривимірний простий опуклого політопа має парне число ребер на кожній з його граней. Тоді, відповідно до гіпотези, граф многогранника має гамільтонів цикл.

Історія

Пітер Ґатрі Тет висловив припущення, що кожен кубічний багатогранний граф є гамільтоновим, відоме як гіпотеза Тета. Це спростував Вільям Татт, який побудував контрприклад з 46 вершинами; інші дослідники пізніше знайшли ще менші контрприклади. Проте жоден з цих відомих контрприкладів не є двочастковим. Сам Татт висловив припущення, що кожен кубічний 3-зв'язний двочастковий граф є гамільтоновим, але це було спростовано виявленням контрприкладу, граф Хортона запропонував поєднання гіпотез Тета і Татта, заявивши, що кожен двочастковий кубічний поліедр гамільтонів, або, що те ж саме, що кожен контрприклад до гіпотези Тета не є двочастковим.

Еквівалентні форми

Кельманс, (1994) показав, що гіпотеза Барнетта є еквівалентно ззовні є більш сильне твердження, що для кожного з двох ребер e and f на тій самій межі двудольного кубічного поліедрона, існує Гамільтонів цикл, що містить e, але не містить f. Ясно, що якщо це твердження вірне, то кожен двочастковий кубічний поліедр містить Гамільтонів цикл: просто вибрати e та f довільно. В інших напрямках, Кельман показав, що контрприклад може бути перетворений в контрприклад до вихідної гіпотези Барнетта.

Гіпотеза Барнетта є також рівносильно твердженням, що вершини кожного кубічного двочасткового багатогранного графа можна розбити на дві підмножини, породжені підграфи дерева. Розріз, індукований розділ в неоднозначному графі відповідає Гамільтоновому циклу в первісній графі.

Часткові результати

Хоча істинність гіпотези Барнетта залишається невідомою, обчислювальні експерименти показали, що не існує контрприклад з менш ніж 86 вершин.

Якщо гіпотеза Барнетта виявиться хибною, то вона може показати, що NP-повна задача для перевірки чи є граф Гамільтоновим двочастковим кубічним поліедром.Якщо плоский граф є двочастковим і кубічним, але тільки 2-зв'язковим, то це може бути негамільтонів граф, і це є NP-повна задача на перевірку графу

Пов'язані проблеми

Пов'язана з цим гіпотеза Барнетта стверджує, що кожен кубічний багатогранний граф, у якому всі грані мають шість або менше ребер, є Гамільтоновим. Обчислювальні експерименти показали, що якщо контрприклад існує, то граф повинен був би мати більше ніж 177 вершин.

Примітки

1. Florek, (2010).
2. Holton, Manvel та McKay, (1985); Hertel, (2005).
3. Feder та Subi, (2006).
4. Akiyama, Nishizeki та Saito, (1980).
5. Aldred та ін., (2000).

Див. також

• Задача про гамільтонів шлях

Джерела

• Акіяма, T.; ; Саіто, Н. (1980), NP-повнота задачі Гамільтона циклу для двочасткових графів, Журнал обробки інформації, 3 (2): 73—76. Як цитує Хертел, (2005).
• Альдред, Р. Є. Л.; Бау, С.; Холтон, Д. A.; (2000), Негамільтонові 3 з'єднані кубічні планарні графи, , 13 (1): 25—32, doi:10.1137/S0895480198348665
• Барнет, Девід В. (1969), Гіпотеза 5, у (ред.), Останні успіхи в комбінаторики: Праці Третьої Waterloo конференції з комбінаторики, Травень 1968, Нью Йорк: Академія Преси, MR 0250896.
• Федір, Томас; Субі, Карлос (2006), Про гіпотезу Барнетта, .
• Фльорек, Ян (2010), Про гіпотезу Барнетта, Дискретна математика, 310 (10-11): 1531—1535, doi:10.1016/j.disc.2010.01.018, MR 2601261.
• Хертель, Олександр (2005), (PDF), архів оригіналу (PDF) за 24 лютого 2022, процитовано 13 березня 2022.
• Холтон, Д. A.; Манвел, Б.; (1985), Гамільтона цикли в кубічних 3-зв'язний двочасткових плоских графів, Журнал комбінаторної теорії, серії B, 38 (3): 279—297, doi:10.1016/0095-8956(85)90072-3.
• Хортон, Дж. Д. (1982), На двох факторів двудольних регулярних графів, Дискретна математика, 41 (1): 35—41, doi:10.1016/0012-365X(82)90079-6.
• Кельманс, A. K. (1994), Конструкції кубічних двочасткових 3-зв'язкових графів без гамільтонових циклів, у Кельманс, A. K. (ред.), Вибрані теми в дискретної математики: Праці Московського семінару дискретної математики 1972-1990, Американське математичне товариство Переклади, серія 2, т. 158, с. 127—140.
• (1884), лістингу Топологія, Філософський журнал (5th ser.), 17: 30—46. Друкується в Наукових доповідях, Том. II, pp. 85–98.
• (1946), Про Гамільтонові цикли (PDF), Журнал Лондонського математичного товариства, 21 (2): 98—101, doi:10.1112/jlms/s1-21.2.98.
• (1971), На 2-х чинників кубічних графів, Дискретна математика, 1 (2): 203—208, doi:10.1016/0012-365X(71)90027-6.

Посилання

• Weisstein, Eric W. Barnette's Conjecture(англ.) на сайті Wolfram MathWorld.
• Barnette's Conjecture [ 14 грудня 2021 у Wayback Machine.] in the Open Problem Garden, Robert Samal, 2007.