Гипотеза Барнетта — нерешённая проблема в теории графов , разделе математики , касающаяся гамильтоновых циклов в графах. Она названа в честь Дэвида У. Барнетта, почётного профессора Калифорнийского университета в Дэвисе ; она утверждает, что каждый двудольный полиэдральный граф с тремя рёбрами на вершину имеет гамильтонов цикл.
Планарный граф — это неориентированный граф , который может быть вложен в евклидову плоскость без каких-либо пересечений . Планарный граф называется полиэдральным тогда и только тогда, когда он является 3-вершинно-связным , то есть если не существует двух вершин, удаление которых разъединило бы остальную часть графа. Граф является двудольным , если его вершины можно раскрасить в два разных цвета так, чтобы каждое ребро имело одну конечную точку каждого цвета. Граф является кубическим (или 3-регулярным ), если каждая вершина является конечной точкой ровно трех ребер. Наконец, граф является гамильтоновым , если существует цикл, который проходит через каждую из его вершин ровно один раз. Гипотеза Барнетта утверждает, что каждый кубический двудольный полиэдральный граф является гамильтоновым.
По теореме Штейница планарный граф представляет ребра и вершины выпуклого многогранника тогда и только тогда, когда он является многогранником. Трехмерный многогранник имеет кубический граф тогда и только тогда, когда он является простым многогранником . И планарный граф является двудольным тогда и только тогда, когда в плоском вложении графа все циклы граней имеют четную длину. Поэтому гипотезу Барнетта можно сформулировать в эквивалентной форме: предположим, что трехмерный простой выпуклый многогранник имеет четное число ребер на каждой из своих граней. Тогда, согласно гипотезе, граф многогранника имеет гамильтонов цикл.
PG Tait (1884) предположил, что каждый кубический многогранный граф является гамильтоновым; это стало известно как гипотеза Тейта . Она была опровергнута WT Tutte (1946), который построил контрпример с 46 вершинами; другие исследователи позже нашли еще меньшие контрпримеры. Однако ни один из этих известных контрпримеров не является двудольным. Сам Tutte предположил, что каждый кубический 3-связный двудольный граф является гамильтоновым, но это было показано ложным открытием контрпримера, графа Хортона . [1] Дэвид У. Барнетт (1969) предложил ослабленную комбинацию гипотез Тейта и Tutte, заявив, что каждый двудольный кубический многогранник является гамильтоновым, или, что эквивалентно, что каждый контрпример к гипотезе Тейта не является двудольным.
Кельманс (1994) [2] показал, что гипотеза Барнетта эквивалентна более сильному на первый взгляд утверждению, что для любых двух ребер e и f на одной грани двудольного кубического многогранника существует гамильтонов цикл, содержащий e , но не содержащий f . Очевидно, если это утверждение верно, то каждый двудольный кубический многогранник содержит гамильтонов цикл: просто выберите e и f произвольно. В других направлениях Кельманс показал, что контрпример можно преобразовать в контрпример к исходной гипотезе Барнетта.
Гипотеза Барнетта также эквивалентна утверждению, что вершины двойственного графа любого кубического двудольного полиэдрального графа могут быть разделены на два подмножества, чьи индуцированные подграфы являются деревьями. Разрез, индуцированный таким разбиением в двойственном графе, соответствует гамильтонову циклу в первичном графе. [3]
Хотя истинность гипотезы Барнетта остается неизвестной, вычислительные эксперименты показали, что не существует контрпримера с числом вершин менее 86. [4]
Если гипотеза Барнетта окажется ложной, то можно показать, что она является NP-полной для проверки того, является ли двудольный кубический многогранник гамильтоновым. [5] Если планарный граф является двудольным и кубическим, но имеет только связность 2, то он может быть негамильтоновым, и проверка гамильтоновости этих графов является NP-полной. [6] Другой результат был получен Альтом и др. (2016): если вершины двойственного графа можно раскрасить в синий, красный и зеленый цвета так, чтобы каждый красно-зеленый цикл содержал вершину степени 4, то первичный граф является гамильтоновым.
Связанная гипотеза Барнетта утверждает, что любой кубический полиэдральный граф, в котором все грани имеют шесть или меньше ребер, является гамильтоновым. Вычислительные эксперименты показали, что если контрпример существует, он должен иметь более 177 вершин. [7] Гипотеза была доказана Кардошем (2020).
Пересечение этих двух гипотез будет заключаться в том, что любой двудольный кубический полиэдральный граф, в котором все грани имеют четыре или шесть ребер, является гамильтоновым. Это было доказано Гуди (1975).