Теорема Флейшнерса - Википедия - Fleischners theorem
В теория графов, раздел математики, Теорема Флейшнера дает достаточное условие для того, чтобы граф содержал Гамильтонов цикл. В нем говорится, что если грамм это 2-вершинно-связный граф, то площадь грамм гамильтоново. он назван в честь Герберт Флейшнер, который опубликовал свое доказательство в 1974 г.
Определения и заявление
An неориентированный граф грамм является гамильтоновым, если он содержит цикл который касается каждой своей вершины ровно один раз. Он является 2-вершинно-связанным, если у него нет вершины сочленения, вершины, удаление которой оставило бы оставшийся граф несвязным. Не всякий двухвершинно-связный граф является гамильтоновым; контрпримеры включают Граф Петерсена и полный двудольный граф K2,3.
Площадь грамм это график грамм2 который имеет ту же вершину, что и грамм, и в котором две вершины смежны тогда и только тогда, когда они имеют расстояние не более двух в грамм. Теорема Флейшнера утверждает, что квадрат конечного 2-вершинно-связного графа по крайней мере с тремя вершинами всегда должен быть гамильтоновым. Эквивалентно, вершины каждого 2-вершинно-связного графа грамм может быть организован в циклический порядок такие, что соседние вершины в этом порядке находятся на расстоянии не более двух друг от друга в грамм.
Расширения
В теореме Флейшнера можно ограничить гамильтонов цикл в грамм2 так что для заданных вершин v и ш из грамм он включает два края грамм инцидент с v и один край грамм инцидент с ш. Более того, если v и ш соседствуют в грамм, то это три разных ребра грамм.[1]
Помимо гамильтонова цикла, квадрат 2-вершинно-связного графа грамм также должен быть гамильтоновым связным (что означает, что он имеет Гамильтонов путь начиная и заканчивая любыми двумя обозначенными вершинами) и 1-гамильтонианом (что означает, что если какая-либо вершина удалена, оставшийся граф все еще имеет гамильтонов цикл).[2] Он также должен быть вершиной панциклический, что означает, что для каждой вершины v и каждое целое число k с 3 ≤k ≤ |V(грамм) | существует цикл длиныk содержащийv.[3]
Если график грамм не является 2-вершинно-связным, то его квадрат может иметь или не иметь гамильтонов цикл, и определение того, есть ли он у него, является НП-полный.[4]
Бесконечный граф не может иметь гамильтонова цикла, потому что каждый цикл конечен, но Карстен Томассен доказал, что если грамм - бесконечный локально конечный 2-вершинно-связный граф с одним конец тогда грамм2 обязательно имеет вдвойне бесконечный гамильтонов путь.[5] В более общем смысле, если грамм локально конечна, 2-вершинно-связна и имеет любое количество концов, то грамм2 имеет гамильтонов круг. В компактное топологическое пространство формируется путем просмотра графика как симплициальный комплекс и добавляя дополнительную бесконечно удаленную точку к каждому из его концов, гамильтонова окружность определяется как подпространство, которое гомеоморфный в евклидову окружность и покрывает каждую вершину.[6]
Алгоритмы
Гамильтонов цикл в квадрате п-вершинный 2-связный граф можно найти за линейное время,[7] улучшение по сравнению с первым алгоритмическим решением Лау[8] времени работы На2)Теорема Флейшнера может быть использована для получения 2-приближение к проблема коммивояжера в метрические пространства.[9]
История
Доказательство теоремы Флейшнера было объявлено Герберт Флейшнер в 1971 г. и опубликованные им в 1974 г., решая гипотезу 1966 г. Криспин Нэш-Уильямс также сделано независимо Л. В. Бейнеке и Майкл Д. Пламмер.[10] В своем обзоре работы Флейшнера Нэш-Вильямс писал, что в ней была решена «хорошо известная проблема, которая в течение нескольких лет побеждала изобретательность других теоретиков графов».[11]
Первоначальное доказательство Флейшнера было сложным. Вацлав Хваталь, в работе, в которой он изобрел графическая стойкость, заметил, что квадрат k-связный граф обязательно k-жесткий; он предполагаемый что 2-жесткие графы являются гамильтоновыми, из чего следовало бы другое доказательство теоремы Флейшнера.[12] Позднее были обнаружены контрпримеры к этой гипотезе.[13] но возможность того, что конечная оценка устойчивости может подразумевать гамильтоничность, остается важной открытой проблемой в теории графов. Более простое доказательство как теоремы Флейшнера, так и ее расширений Chartrand et al. (1974), был предоставлен Íha (1991),[14] и другое упрощенное доказательство теоремы было дано Георгакопулос (2009a).[15]
Рекомендации
Примечания
- ^ Флейшнер (1976); Мюттель и Раутенбах (2012).
- ^ Chartrand et al. (1974); Чартран, Лесняк и Чжан (2010)
- ^ Хоббс (1976), отвечая на догадку Бонди (1971).
- ^ Подземный (1978); Бонди (1995).
- ^ Томассен (1978).
- ^ Георгакопулос (2009b); Дистель (2012).
- ^ Альструп, Георгакопулос, Ротенберг, Томассен (2018)
- ^ Лау (1980); Паркер и Рардин (1984).
- ^ Паркер и Рардин (1984); Хохбаум и Шмойс (1986).
- ^ Флейшнер (1974). По поводу более ранних предположений см. Fleischner and Чартран, Лесняк и Чжан (2010).
- ^ МИСТЕР0332573.
- ^ Хваталь (1973); Бонди (1995).
- ^ Бауэр, Броерсма и Вельдман (2000).
- ^ Бонди (1995); Чартран, Лесняк и Чжан (2010).
- ^ Чартран, Лесняк и Чжан (2010); Дистель (2012).
Основные источники
- Альструп, Стивен; Георгакопулос, Агелос; Ротенберг, Ева; Томассен, Карстен (2018), «Гамильтонов цикл в квадрате двусвязного графа в линейном времени», Материалы двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, стр. 1645–1649, Дои:10.1137/1.9781611975031.107, ISBN 978-1-61197-503-1
- Bauer, D .; Broersma, H.J .; Вельдман, Х. Дж. (2000), «Не каждый 2-жесткий граф является гамильтоновым», Труды 5-го семинара Twente по графам и комбинаторной оптимизации (Enschede, 1997), Дискретная прикладная математика, 99 (1–3): 317–321, Дои:10.1016 / S0166-218X (99) 00141-9, МИСТЕР 1743840.
- Бонди, Дж. А. (1971), «Панциклические графы», Труды Второй Луизианской конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, штат Луизиана, 1971 г.), Батон-Руж, Луизиана: Университет штата Луизиана, стр. 167–172, МИСТЕР 0325458.
- Шартран, Г.; Хоббс, Артур М.; Jung, H.A .; Капур, С. Ф .; Нэш-Уильямс, К. Сент-Дж. А. (1974), «Квадрат блока гамильтоново связан», Журнал комбинаторной теории, Серия B, 16 (3): 290–292, Дои:10.1016/0095-8956(74)90075-6, МИСТЕР 0345865.
- Хваталь, Вацлав (1973), "Жесткие графы и гамильтоновы схемы", Дискретная математика, 5 (3): 215–228, Дои:10.1016 / 0012-365X (73) 90138-6, МИСТЕР 0316301.
- Флейшнер, Герберт (1974), "Квадрат каждого двусвязного графа является гамильтоновым", Журнал комбинаторной теории, Серия B, 16: 29–34, Дои:10.1016/0095-8956(74)90091-4, МИСТЕР 0332573.
- Флейшнер, Х. (1976), «В квадрате графов гамильтоновость и панцикличность, гамильтонова связность и пансвязность являются эквивалентными понятиями», Monatshefte für Mathematik, 82 (2): 125–149, Дои:10.1007 / BF01305995, МИСТЕР 0427135.
- Георгакопулос, Агелос (2009a), "Краткое доказательство теоремы Флейшнера", Дискретная математика, 309 (23–24): 6632–6634, Дои:10.1016 / j.disc.2009.06.024, МИСТЕР 2558627.
- Георгакопулос, Агелос (2009b), "Бесконечные циклы Гамильтона в квадратах локально конечных графов", Успехи в математике, 220 (3): 670–705, Дои:10.1016 / j.aim.2008.09.014, МИСТЕР 2483226.
- Хоббс, Артур М. (1976), "Квадрат блока является панциклическим вершиной", Журнал комбинаторной теории, Серия B, 20 (1): 1–4, Дои:10.1016/0095-8956(76)90061-7, МИСТЕР 0416980.
- Хохбаум, Дорит С.; Шмойс, Дэвид Б. (1986), «Единый подход к алгоритмам аппроксимации для проблем узких мест», Журнал ACM, Нью-Йорк, Нью-Йорк, США: ACM, 33 (3): 533–550, Дои:10.1145/5925.5933.
- Лау, Х. Т. (1980), Нахождение гамильтонова цикла в квадрате блока., Кандидат наук. дипломная работа, Монреаль: Университет Макгилла. Как цитирует Хохбаум и Шмойс (1986).
- Мюттель, Янина; Раутенбах, Дитер (2012), «Краткое доказательство универсальной версии теоремы Флейшнера», Дискретная математика, 313 (19): 1929–1933, Дои:10.1016 / j.disc.2012.07.032.
- Паркер, Р. Гэри; Рардин, Рональд Л. (1984), "Эвристика гарантированной производительности для решения проблемы коммивояжера", Письма об исследованиях операций, 2 (6): 269–272, Дои:10.1016/0167-6377(84)90077-4.
- Íha, Станислав (1991), "Новое доказательство теоремы Флейшнера", Журнал комбинаторной теории, Серия B, 52 (1): 117–123, Дои:10.1016/0095-8956(91)90098-5, МИСТЕР 1109427.
- Томассен, Карстен (1978), "Гамильтоновы пути в квадратах бесконечных локально конечных блоков", в Боллобаш, Б. (ред.), Достижения в теории графов (Кембриджская комбинаторная конференция, Тринити-колледж, Кембридж, 1977), Анналы дискретной математики, 3, Elsevier, стр.269–277, Дои:10.1016 / S0167-5060 (08) 70512-0, ISBN 978-0-7204-0843-0, МИСТЕР 0499125.
- Метро, Полли (1978), «О графах с гамильтоновыми квадратами», Дискретная математика, 21 (3): 323, Дои:10.1016 / 0012-365X (78) 90164-4, МИСТЕР 0522906.
Вторичные источники
- Бонди, Дж. А. (1995), "Основы теории графов: пути и схемы", Справочник по комбинаторике, Vol. 1, 2, Амстердам: Elsevier, стр. 3–110, МИСТЕР 1373656.
- Чартран, Гэри; Лесняк, Линда; Чжан, Пин (2010), Графы и диграфы (5-е изд.), CRC Press, стр. 139, ISBN 9781439826270.
- Дистель, Рейнхард (2012), «10. Гамильтоновы циклы», Теория графов (PDF) (исправленное 4-е электронное изд.)