Теорема Фляйшнера — утверждение в теории графов, дающее достаточное условие, чтобы граф содержал гамильтонов цикл: если граф является вершинно 2-связным графом, то квадрат графа гамильтонов. Названа именем Герберта Фляйшнера, опубликовавшего доказательство теоремы в 1974 году.

Определения и утверждение Неориентированный граф G является гамильтоновым, если он содержит цикл, который проходит через каждую вершину в точности один раз. Граф является вершинно 2-связным, если он не содержит сочленяющих вершин, то есть вершин, удаление которых делает оставшийся граф несвязным. Не любой вершинно 2-связный граф является гамильтоновым. Контрпримеры включают граф Петерсена и полный двудольный граф K2,3.

Квадрат графа G — это граф G2, имеющий то же самое множество вершин, что и граф G, и в котором две вершины смежны тогда и только тогда, когда расстояние между ними в G не превосходит числа два. Теорема Фляйшера утверждает, что квадрат конечного вершинно 2-связного графа с тремя и более вершинами должен всегда быть гамильтоновым. Эквивалентно, вершины любого вершинно 2-связного графа G могут быть организованы в циклический порядок, так что смежные вершины в этом порядке в графе G находятся друг от друга на расстоянии, не превосходящем двух.

Расширения В теореме Фляйшнера можно наложить ограничение на гамильтонов цикл так, чтобы он включал три выбранных ребра, проходящие через две выбранные вершины.

Кроме содержания гамильтонова цикла, квадрат вершинно 2-связного графа G должен быть также гамильтоново связан (что означает, что он имеет гамильтонов путь, начинающийся и заканчивающийся в любых двух выбранных вершинах) и 1-гамильтонов (что означает, что если удалить любую вершину, оставшийся граф также будет содержать гамильтонов цикл). Граф должен быть также вершинно панциклическим, что означает, что для любой вершины v и любого целого k с 3 ≤ k ≤ |V(G)| существует цикл длины k, содержащий vХоббс (), ответ на гипотезу Бонди ()..

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

Бесконечный граф не может иметь гамильтонов цикл, поскольку любой цикл конечен, но доказали, что в случае, когда G является бесконечным локально конечным вершинно 2-связным графом с единым концом, то G2 обязательно имеет дважды бесконечный гамильтонов путь. Более обще, если G локально конечен, вершинно 2-связен и имеет любое число концов, то G2 имеет гамильтонов цикл. В компактном топологическом пространстве, образованный рассмотрением графа как симплициальный комплекс и добавлением дополнительной точки на бесконечности для каждого конца графа, гамильтонов цикл определяется как подпространство, которое гомеоморфно евклидовой окружности и покрывает все вершины.

История О доказательстве теоремы объявил в 1971 году и опубликовал в 1974 году, решив тем самым гипотезу 1966 года , которую независимо высказали также и . О более ранних гипотезах см. У Фляйшнера и Чартранда, Лесниака и Чжана ().. В своём обозрении статья Фляйшнера Нэш-Вильямс пишет, что тот решил «хорошо известную проблему, о которую несколько лет разбивалась изобретательность других теоретиков теории графов»..

Оригинальное доказательство Фляйшера было сложно. Вацлав Хватал в работе, в которой он ввёл понятие жёсткости графа, заметил, что квадрат вершинно k-связного графа обязательно k-жёсток. Он высказал предположение, что 2-жёсткие графы являются гамильтоновыми, из чего получилось бы другое доказательство теоремы Фляйшера. Позднее были обнаружены контрпримеры этой гипотезе, но возможность, что из конечной границы жёсткости могла бы следовать гамильтоновость, осталась важной открытой проблемой в теории графов. Более простое доказательство как теоремы Флейшнера, так и её расширения, сделанные Чартрандом, Хоббсом, Янгом и Капууром, было дано Риха, а ещё одно упрощённое доказательство теоремы дал Георгакопулус.

Примечания

Литература

Категория:Теоремы теории графов