Loading AI tools
Из Википедии, свободной энциклопедии
Теорема Фляйшнера — утверждение в теории графов, дающее достаточное условие, чтобы граф содержал гамильтонов цикл: если граф является вершинно 2-связным графом, то квадрат графа гамильтонов. Названа именем Герберта Фляйшнера, опубликовавшего доказательство теоремы в 1974 году.
Неориентированный граф G является гамильтоновым, если он содержит цикл, который проходит через каждую вершину в точности один раз. Граф является вершинно 2-связным, если он не содержит сочленяющих вершин, то есть вершин, удаление которых делает оставшийся граф несвязным. Не любой вершинно 2-связный граф является гамильтоновым. Контрпримеры включают граф Петерсена и полный двудольный граф K2,3.
Квадрат графа G — это граф G2, имеющий то же самое множество вершин, что и граф G, и в котором две вершины смежны тогда и только тогда, когда расстояние между ними в G не превосходит числа два. Теорема Фляйшера утверждает, что квадрат конечного вершинно 2-связного графа с тремя и более вершинами должен всегда быть гамильтоновым. Эквивалентно, вершины любого вершинно 2-связного графа G могут быть организованы в циклический порядок, так что смежные вершины в этом порядке в графе G находятся друг от друга на расстоянии, не превосходящем двух.
В теореме Фляйшнера можно наложить ограничение на гамильтонов цикл так, чтобы он включал три выбранных ребра, проходящие через две выбранные вершины[1][2].
Кроме содержания гамильтонова цикла, квадрат вершинно 2-связного графа G должен быть также гамильтоново связан (что означает, что он имеет гамильтонов путь, начинающийся и заканчивающийся в любых двух выбранных вершинах) и 1-гамильтонов (что означает, что если удалить любую вершину, оставшийся граф также будет содержать гамильтонов цикл)[3][4]. Граф должен быть также вершинно панциклическим, что означает, что для любой вершины v и любого целого k с 3 ≤ k ≤ |V(G)| существует цикл длины k, содержащий v[5].
Если граф G не вершинно 2-связен, его квадрат может иметь, а может и не иметь гамильтонов цикл и определение, имеет ли граф такой цикл, является NP-полной задачей[6][7].
Бесконечный граф не может иметь гамильтонов цикл, поскольку любой цикл конечен, но Карстен Томассен[англ.] доказали, что в случае, когда G является бесконечным локально конечным вершинно 2-связным графом с единым концом, то G2 обязательно имеет дважды бесконечный гамильтонов путь[8]. Более обще, если G локально конечен, вершинно 2-связен и имеет любое число концов, то G2 имеет гамильтонов цикл. В компактном топологическом пространстве, образованный рассмотрением графа как симплициальный комплекс и добавлением дополнительной точки на бесконечности для каждого конца графа, гамильтонов цикл определяется как подпространство, которое гомеоморфно евклидовой окружности и покрывает все вершины[9][10].
О доказательстве теоремы Герберт Фляшнер[нем.] объявил в 1971 году и опубликовал в 1974 году, решив тем самым гипотезу 1966 года Нэш-Вильямса[англ.], которую независимо высказали также Л.У. Байник[англ.] и Пламмер[англ.][11]. В своём обозрении статья Фляйшнера Нэш-Вильямс пишет, что тот решил «хорошо известную проблему, о которую несколько лет разбивалась изобретательность других теоретиков теории графов»[12].
Оригинальное доказательство Фляйшера было сложно. Вацлав Хватал в работе, в которой он ввёл понятие жёсткости графа, заметил, что квадрат вершинно k-связного графа обязательно k-жёсток. Он высказал предположение, что 2-жёсткие графы являются гамильтоновыми, из чего получилось бы другое доказательство теоремы Фляйшера[13][7]. Позднее были обнаружены контрпримеры этой гипотезе[14], но возможность, что из конечной границы жёсткости могла бы следовать гамильтоновость, осталась важной открытой проблемой в теории графов. Более простое доказательство как теоремы Флейшнера, так и её расширения, сделанные Чартрандом, Хоббсом, Янгом и Капууром[3], было дано Риха[15][7][4], а ещё одно упрощённое доказательство теоремы дал Георгакопулус[16][4][10].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
