Вікіпедія

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

Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. Ви можете допомогти вдосконалити цю статтю, погодивши її із чинними мовними стандартами. (травень 2016)

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

Визначення ред.

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

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

Історія ред.

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

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

Кельманс, (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, 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.

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Гіпотеза_Барнета&oldid=39318524