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

Перейти к навигацииПерейти к поиску
Нерешённые проблемы математики: Является ли двудольный простой многогранник гамильтоновым?

Гипотеза Барнетта — нерешённый вопрос в теории графов о существовании гамильтоновых циклов в графах. Гипотеза названа именем Дэвида В. Барнетта, эмерита калифорнийского университета в Дейвисе. Гипотеза утверждает, что любой двудольный граф многогранника с тремя рёбрами в каждой вершине имеет гамильтонов цикл.

Определения

Планарный граф — это неориентированный граф, который может быть вложен в евклидово пространство без пересечений. Планарный граф называется полиэдральным (или графом многогранника) тогда и только тогда, когда он вершинно 3-связен, то есть, если не существует двух вершин, удаление которых разбивает граф на два (или более) графа. Граф называется двудольным, если его вершины можно раскрасить в два цвета таким образом, что каждое ребро соединяет вершины разных цветов. Граф называется кубическим (или 3-регулярным), если каждая вершина является концом в точности трёх рёбер. Наконец, граф гамильтонов, если существует цикл, проходящий через все вершины в точности один раз. Гипотеза Барнетта утверждает, что любой кубический двудольный граф многогранника гамильтонов.

По теореме Штайница планарный граф представляет рёбра и вершины выпуклого многогранника тогда и только тогда, когда он полиэдрален. Трёхмерный многогранник образует кубический граф тогда и только тогда, когда он является простым. Планарный граф является двудольным тогда и только тогда, когда в его планарном вложении все циклы граней (границы) имеют чётную длину. Таким образом, гипотеза Барнетта может быть сформулирована в эквивалентном виде. Представим, что трёхмерный простой выпуклый многогранник имеет чётное число рёбер в каждой грани. Тогда, согласно гипотезе, граф многогранника имеет гамильтонов цикл.

История

В 1884 году Тэйт высказал предположение, что любой кубический полиэдральный граф является гамильтоновым. Теперь эта гипотеза известна как гипотеза Тэйта. Гипотезу опроверг Татт в 1946[1], построив контрпример с 46 вершинами. Другие исследователи позднее нашли меньшие контрпримеры, однако ни один из этих контрпримеров не является двудольным. Сам Татт предположил, что любой кубический 3-связный двудольный граф гамильтонов, но был найден контрпример, граф Хортона[2][3]. Дэвид В. Барнетт в 1969[4] предложил ослабленную комбинацию гипотез Тэйта и Татта, утверждающую, что любой двудольный кубический полиэдральный граф гамильтонов, или, эквивалентно, что любой контрпример гипотезы Тэйта не является двудлольным.

Эквивалентные формы

Келманс[5] показал, что гипотеза Барнетта эквивалентна утверждению, что для любых двух рёбер e и f на одной и той же грани двудольного кубического многогранника существует гамильтонов цикл, который содержит e, но не содержит f. Ясно, что если утверждение верно, то любой двудольный кубический полиэдральный содержит гамильтонов цикл — просто выберем e или f. В другом направлении Келман показал, что конртпример этому утверждению можно преобразовать в контрпример оригинальной гипотезы Барнетта.

Гипотеза Барнетта эквивалентна также утверждению, что вершины двойственного графа для любого кубического двудольного полиэдрального графа можно разделить на два подмножества и порождённые графы на этих подмножествах являются деревьями. Сечение, порождённое таким разделением в двойственном графе, соответствует гамильтонову пути в исходном графе[6].

Частичные результаты

Хотя неизвестно, верна ли гипотеза Барнетта, вычислительные эксперименты показывают, что контрпримера с числом вершин меньше 86 нет[7][8].

Если окажется, что гипотеза Барнетта неверна, то можно показать, что проверка, является ли двудольный кубический многогранник гамильтоновым, является NP-полной задачей[9]. Если планарный граф является двудольным и кубическим, но только 2-связным, то он может не быть гамильтоновым, и проверка, является ли граф гамильтоновым, является NP-полной задачей[10].

Связанные задачи

Гипотеза, связанная с гипотезой Барнетте, утверждает, что любой кубический полиэдральный граф, в котором все грани имеют шесть и менее рёбер, является гамильтоновым. Вычислительные эксперименты показали, что если контрпример существует, он будет иметь более 177 вершин[11].

Примечания

  1. ↑ Tutte, 1946.
  2. ↑ Tutte, 1971.
  3. ↑ Horton, 1982.
  4. ↑ Barnette, 1969.
  5. ↑ Kelmans, 1994.
  6. ↑ Florek, 2010.
  7. ↑ Holton, Manvel, McKay, 1985.
  8. ↑ Hertel, 2005.
  9. ↑ Feder, Subi, 2006.
  10. ↑ Akiyama, Nishizeki, Saito, 1980.
  11. ↑ Aldred, Bau, Holton, McKay, 2000.

Литература

  • T. Akiyama, T. Nishizeki, N. Saito. NP-completeness of the Hamiltonian cycle problem for bipartite graphs // Journal of Information Processing. — 1980. — Т. 3, вып. 2. — С. 73–76.. Как процитировано у Хертеля ((Hertel 2005)).
  • R. E. L. Aldred, S. Bau, D. A. Holton, Brendan D. McKay. Nonhamiltonian 3-connected cubic planar graphs // SIAM Journal on Discrete Mathematics. — 2000. — Т. 13, вып. 1. — С. 25–32. — doi:10.1137/S0895480198348665.
  • David W. Barnette. Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968 / W. T. Tutte. — New York: Academic Press, 1969..
  • Tomas Feder, Carlos Subi. On Barnette's conjecture. — 2006.
  • Jan Florek. On Barnette's conjecture // Discrete Mathematics. — 2010. — Т. 310, вып. 10—11. — С. 1531–1535. — doi:10.1016/j.disc.2010.01.018.
  • Alexander Hertel. A survey & strengthening of Barnette’s conjecture. — 2005.
  • D. A. Holton, B. Manvel, B. D. McKay. Hamiltonian cycles in cubic 3-connected bipartite planar graphs // Journal of Combinatorial Theory, Series B. — 1985. — Т. 38, вып. 3. — С. 279–297. — doi:10.1016/0095-8956(85)90072-3..
  • J. D. Horton. On two-factors of bipartite regular graphs // Discrete Mathematics. — 1982. — Т. 41, вып. 1. — С. 35–41. — doi:10.1016/0012-365X(82)90079-6..
  • A. K. Kelmans. Selected Topics in Discrete Mathematics: Proceedings of the Moscow Discrete Mathematics Seminar 1972–1990 / A. K. Kelmans. — 1994. — Т. 158. — С. 127–140. — (American Mathematical Society Translations, Series 2)..
  • W. T. Tutte. Listing's Topologie // Philosophical Magazine (5th ser.). — 1884. — Т. 17. — С. 30–46.. Reprinted in Scientific Papers, Vol. II, pp. 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..
  • W. T. Tutte. On the 2-factors of bicubic graphs // Discrete Mathematics. — 1971. — Т. 1, вып. 2. — С. 203–208. — doi:10.1016/0012-365X(71)90027-6.

Ссылки