Русская Википедия:Гипотеза Тэйта (теория графов)
Шаблон:Другие значения Гипотеза Тэйта — опровергнутая математическая гипотеза о том, что любой 3-связный планарный кубический граф имеет гамильтонов цикл, проходящий через все его вершины.
Высказана в 1884 году Питером ТэйтомШаблон:Sfn, опровергнута в 1946 году Уильямом ТаттомШаблон:Sfn, который построил контрпример с 25 гранями, 69 рёбрами и 46 вершинами — граф Татта. Позднее, в 1988 году, найден контрпример с 21 гранями, 57 рёбрами и 38 вершинами и доказано, что этот граф минималенШаблон:Sfn.
Условие 3-регулярности (3-регулярные графы называются кубическими) необходимо, поскольку существуют многогранники, такие как ромбододекаэдр. Ромбододекаэдр образует двудольный граф и любой гамильтонов цикл в этом графе должен поочерёдно менять доли (стороны) графа, так что число вершин в долях должно быть равно, однако граф имеет шесть вершин степени 4 на одной стороне и восемь вершин степени 3 на другой.
Если бы гипотеза была верна, то из неё следовало бы простое решение проблемы четырёх красок. Согласно Тэйту, задача четырёх красок эквивалентна задаче поиска рёберной 3-раскраски кубических планарных графов без мостов. В гамильтоновом кубическом планарном графе такую раскраску рёбер легко найти — поочерёдно используем два цвета для раскраски рёбер вдоль гамильтонова цикла, а третьим цветом выкрасим оставшиеся рёбра. Альтернативно можно построить раскраску в четыре цвета граней гамильтонова кубического планарного графа прямо, если использовать два цвета для раскраски граней внутри цикла и два цвета для граней снаружи.
Контрпример Татта
Ключом контрпримера является граф, называемый теперь фрагментом Татта. Если этот фрагмент является частью большего графа, любой гамильтонов цикл должен проходить через (висячее) ребро при верхней вершине (и через одно из нижних рёбер). Путь не может войти через нижнее ребро и выйти через другое нижнее ребро.
Фрагмент Татта используется для построения негамильтонова графа Татта, если сложить вместе три таких фрагмента. «Обязательные» рёбра фрагментов, которые обязаны быть частями гамильтонова пути через фрагмент, соединены в центре. Поскольку любой цикл может проходить только через два из трёх рёбер в центре, гамильтонова цикла для этого графа быть не может. Получившийся граф Татта является 3-связным и планарным, так что он является графом многогранника по теореме Штайница. Граф имеет 25 граней, 69 рёбер и 46 вершин. Геометрически граф можно получить из тетраэдра (грани которого соответствуют четырём большим граням на рисунке — три грани между парами фрагментов, а четвёртая грань является внешней) путём многократного усечения трёх его вершин.
Меньшие контрпримеры
Как показали Холтон и Маккей в 1988 годуШаблон:Sfn, существует ровно шесть негамильтоновых 3-регулярных многогранников с 38 вершинами. Многогранники образованы заменой двух вершин пятиугольной призмы тем же фрагментом из примера Татта.
См. также
- Теорема Гринберга — необходимое условие существования гамильтонова цикла, которое можно использовать, чтобы показать, что граф является контрпримером гипотезе Тэйта.
- Гипотеза Барнетта — остающееся открытым усовершенствование гипотезы Тэйта; гипотеза утверждает, что любой двудольный кубический полиэдральный граф является гамильтоновым.[1]
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья Статья перепечатана в Scientific Papers, том II, стр. 85-98.
- Шаблон:Статья
Ссылки
- ↑ Barnette’s conjecture Шаблон:Wayback, the Open Problem Garden, retrieved 2009-10-12.
