Гипотеза Барнетта - Barnettes conjecture - Wikipedia

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Является ли каждый двудольный простой многогранник гамильтонианом?
(больше нерешенных задач по математике)

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

Определения

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

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

История

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

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

Кельманс (1994)[2] показал, что гипотеза Барнетта эквивалентна более сильному на первый взгляд утверждению, что для любых двух ребер е и ж на той же грани двудольного кубического многогранника существует гамильтонов цикл, содержащий е но не содержит ж. Ясно, что если это утверждение верно, то каждый двудольный кубический многогранник содержит гамильтонов цикл: просто выберите е и ж произвольно. С другой стороны, Кельманс показал, что контрпример можно преобразовать в контрпример к исходной гипотезе Барнетта.

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

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

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

Если гипотеза Барнетта окажется ложной, то можно показать, что она верна. НП-полный чтобы проверить, является ли двудольный кубический многогранник гамильтоновым.[5] Если планарный граф двудольный и кубический, но только со связностью 2, то он может быть негамильтоновым и NP-полным для проверки гамильтоновости этих графов.[6] Другой результат был получен Alt et al. (2016): если двойственный граф может быть окрашен вершинами в синий, красный и зеленый цвета, так что каждый красно-зеленый цикл содержит вершину степени 4, то прямой граф является гамильтоновым.

Связанные проблемы

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

Эти две гипотезы пересекаются с тем, что любой двудольный кубический многогранный граф, в котором все грани имеют четыре или шесть ребер, является гамильтоновым. Это было доказано Гуди (1975).

Примечания

  1. ^ Тутте (1971); Хортон (1982).
  2. ^ Видеть Alt et al. (2016) для доказательств
  3. ^ Флорек (2010).
  4. ^ Холтон, Манвел и Маккей (1985); Хертель (2005).
  5. ^ Федер и Суби (2006).
  6. ^ Акияма, Нисизеки и Сайто (1980).
  7. ^ Aldred et al. (2000).

Рекомендации

внешняя ссылка