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

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

Определения

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

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

История

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

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

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

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

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

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

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

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

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

Примечания

Литература

• 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 . . Как процитировано у Хертеля (( )).
• R. E. L. Aldred, S. Bau, D. A. Holton, Brendan D. McKay. Nonhamiltonian 3-connected cubic planar graphs // . — 2000. — Т. 13 , вып. 1 . — С. 25–32 . — doi : .
• 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 : .
• 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 : . .
• J. D. Horton. On two-factors of bipartite regular graphs // Discrete Mathematics. — 1982. — Т. 41 , вып. 1 . — С. 35–41 . — doi : . .
• 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 : . .
• W. T. Tutte . On the 2-factors of bicubic graphs // Discrete Mathematics. — 1971. — Т. 1 , вып. 2 . — С. 203–208 . — doi : .

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
• от 14 декабря 2021 на Wayback Machine in the Open Problem Garden, Robert Samal, 2007.