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

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

Визначення

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

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

Історія

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

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

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

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

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

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

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

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

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

Примітки

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

Див. також

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

Джерела

• Акіяма, T.; Нішісекі, T.; Саіто, Н. (1980), NP-повнота задачі Гамільтона циклу для двочасткових графів, Журнал обробки інформації, 3 (2): 73—76. Як цитує Хертел, (2005).
• Альдред, Р. Є. Л.; Бау, С.; Холтон, Д. A.; Маккей, Брендан Д. (2000), Негамільтонові 3 з'єднані кубічні планарні графи, SIAM Журнал з дискретної математики, 13 (1): 25—32, doi:10.1137/S0895480198348665
• Барнет, Девід В. (1969), Гіпотеза 5, у Тутте, В. Т. (ред.), Останні успіхи в комбінаторики: Праці Третьої Waterloo конференції з комбінаторики, Травень 1968, Нью Йорк: Академія Преси, MR 0250896.
• Федір, Томас; Субі, Карлос (2006), Про гіпотезу Барнетта, Шаблон:ECCC.
• Фльорек, Ян (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.
• Тутте, В. T. (1946), Про Гамільтонові цикли (PDF), Журнал Лондонського математичного товариства, 21 (2): 98—101, doi:10.1112/jlms/s1-21.2.98.
• Тутте, В. T. (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.