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

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

Визначення

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

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

Історія

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

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

Кельманс, (1994) показав, що гіпотеза Барнетта є еквівалентно ззовні є більш сильне твердження, що для кожного з двох ребер e and 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. MR 2601261. doi:10.1016/j.disc.2010.01.018..
  • Хертель, Олександр (2005). Обстеження і посилення гіпотези Барнетта..
  • Холтон, Д. 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). Про Гамільтонові цикли. Журнал Лондонського математичного товариства 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..

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.