В математике гипотеза Тэйта утверждает, что «Каждый 3-связный плоский кубический граф имеет гамильтонов цикл (по ребрам), проходящий через все его вершины ». Он был предложен PG Tait ( 1884 ) и опровергнут WT Tutte ( 1946 ), который построил контрпример с 25 гранями, 69 ребрами и 46 вершинами. Несколько меньших контрпримеров с 21 гранью, 57 ребрами и 38 вершинами были позже доказаны Холтоном и Маккеем (1988) как минимальные . Условие 3-регулярности графа необходимо из-за наличия многогранников, таких как ромбический додекаэдр , который образуетдвудольный граф с шестью вершинами четвертой степени с одной стороны и восемью вершинами третьей степени с другой стороны; поскольку любой гамильтонов цикл должен чередоваться между двумя сторонами двудольного разделения, но у них неравное количество вершин, ромбический додекаэдр не является гамильтоновым.
Гипотеза была значительной, потому что если это правда, было бы предполагала теорему четыре цвета : как описано Тэйт, проблема четыре цвета эквивалентна задаче нахождения рёберные 3-раскрасок из bridgeless кубических планарных графов. В гамильтоновом кубическом плоском графе такую раскраску ребер легко найти: поочередно используйте два цвета на цикле и третий цвет для всех остальных ребер. В качестве альтернативы, 4-раскраска граней гамильтонова кубического плоского графа может быть построена напрямую, используя два цвета для граней внутри цикла и еще два цвета для граней снаружи.
Контрпример Тутте
Фрагмент Тутте
Ключ к этому контрпримеру - это то, что теперь известно как фрагмент Тутте , показанный справа.
Если этот фрагмент является частью большего графа, то любой гамильтонов цикл, проходящий через граф, должен входить или выходить из верхней вершины (и любой из нижних). Он не может заходить в одну нижнюю вершину и выходить из другой.
Контрпример
Затем этот фрагмент можно использовать для построения негамильтонова графа Тутте путем объединения трех таких фрагментов, как показано на рисунке. «Обязательные» ребра фрагментов, которые должны быть частью любого гамильтонова пути через фрагмент, соединяются в центральной вершине; поскольку любой цикл может использовать только два из этих трех ребер, гамильтонова цикла быть не может.
Полученный граф татта является 3-подключенной и плоским , так что с помощью Стейнца»теоремы является графиком многогранника. Всего у него 25 граней, 69 ребер и 46 вершин. Его можно реализовать геометрически из тетраэдра (грани которого соответствуют четырем большим граням на чертеже, три из которых находятся между парами фрагментов, а четвертая из которых образует внешность) путем многократного усечения трех его вершин.
Меньшие контрпримеры
Как показывают Холтон и Маккей (1988) , существует ровно шесть негамильтоновых многогранников с 38 вершинами, которые имеют нетривиальные трехреберные разрезы. Они образованы заменой двух вершин пятиугольной призмы тем же фрагментом, что и в примере Тутте.
Смотрите также
- Теорема Гринберга , необходимое условие существования гамильтонова цикла, которое можно использовать, чтобы показать, что граф является контрпримером к гипотезе Тейта.
- Гипотеза Барнетта , все еще открытое уточнение гипотезы Тэта о том, что каждый двудольный кубический многогранный граф является гамильтоновым. [1]
Заметки
- ^ Гипотеза Барнетты в открытой Проблеме Сад, извлекаться 2009-10-12.
Рекомендации
- Holton, DA; Маккей, BD (1988), "Наименьшие негамильтонова 3-связанные кубических планарных графов есть 38 вершин", Журнал комбинаторной теории, Series B , 45 (3): 305-319, DOI : 10.1016 / 0095-8956 (88 ) 90075-5.
- Tait, PG (1884), " Топология листинга ", Philosophical Magazine , 5-я серия, 17 : 30–46. Перепечатано в Scientific Papers , Vol. II, стр. 85–98.
- Тутте, В. Т. (1946), «О гамильтоновых схемах» (PDF) , Журнал Лондонского математического общества , 21 (2): 98–101, DOI : 10.1112 / jlms / s1-21.2.98.
Частично основано на публикации Билла Тейлора в sci.math , использованной с разрешения.