Теорема Фляйшнера

Материал из testwiki
Перейти к навигации Перейти к поиску
Вершинно 2-связный граф, его квадрат и гамильтонов цикл в квадрате

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

Определения и утверждение

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

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

Расширения

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

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

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

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

История

О доказательстве теоремы Шаблон:Нп5 объявил в 1971 году и опубликовал в 1974 году, решив тем самым гипотезу 1966 года Шаблон:Не переведено 5, которую независимо высказали также Шаблон:Не переведено 5 и Шаблон:Не переведено 5[2]. В своём обозрении статья Фляйшнера Нэш-Вильямс пишет, что тот решил «хорошо известную проблему, о которую несколько лет разбивалась изобретательность других теоретиков теории графов»[3].

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

  1. ↑ Хоббс (Шаблон:Harvtxt), ответ на гипотезу Бонди (Шаблон:Sfn0).
  2. ↑ Шаблон:Harvtxt. О более ранних гипотезах см. У Фляйшнера и Чартранда, Лесниака и Чжана (Шаблон:Harvtxt).
  3. ↑ Шаблон:MR.
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Теорема_Фляйшнера&oldid=18008