В теории графов , разделе математики, теорема Флейшнера дает достаточное условие для того, чтобы граф содержал гамильтонов цикл . Он утверждает, что если G - двухвершинно-связный граф , то квадрат G гамильтонов. он назван в честь Герберта Флейшнера , опубликовавшего свое доказательство в 1974 году.
Определения и заявление
Неориентированный граф G гамильтонов , если он содержит цикл , который затрагивает каждого из его вершин ровно один раз. Он является 2-вершинно-связным, если у него нет вершины сочленения, вершины, удаление которой оставило бы оставшийся граф несвязным. Не всякий двухвершинно-связный граф является гамильтоновым; контрпримеры включают граф Петерсена и полный двудольный граф K 2,3 .
Квадрат G представляет собой график , G 2 , который имеет такую же множество вершин , как G , и в котором две вершины смежны тогда и только тогда , когда они имеют расстояние не более двух в G . Теорема Флейшнера утверждает, что квадрат конечного 2-вершинно-связного графа по крайней мере с тремя вершинами всегда должен быть гамильтоновым. Эквивалентно, вершины каждого 2-вершинного связного графа G могут быть расположены в циклическом порядке таким образом, что соседние вершины в таком порядке находятся на расстоянии не более двух друг от друга в G .
Расширения
В теореме Fleischner, это можно тягот гамильтонов цикл в G 2 , так что при заданных вершин V и W из G включает в себя два ребра G инцидента с V и один край G инцидента с ш . Более того, если V и W являются смежными в G , то эти три различных ребра G . [1]
В дополнение к наличию гамильтонова цикла квадрат двухвершинно-связного графа G должен быть гамильтоновым связным (это означает, что он имеет гамильтонов путь, начинающийся и заканчивающийся в любых двух обозначенных вершинах) и 1-гамильтоновым (что означает, что если любой вершина удаляется, оставшийся граф по-прежнему имеет гамильтонов цикл). [2] Она также должна быть панциклической вершиной , что означает, что для каждой вершины v и любого целого числа k с 3 ≤ k ≤ | V ( G ) | существует цикл длины k, содержащий v . [3]
Если граф G не является 2-вершинно-связным, то его квадрат может иметь или не иметь гамильтонов цикл, и определение того, есть ли он у него, является NP-полным . [4]
Бесконечный граф не может иметь гамильтонова цикла, потому что каждый цикл конечен, но Карстен Томассен доказал, что если G - бесконечный локально конечный 2-вершинно-связанный граф с одним концом, то G 2 обязательно имеет дважды бесконечный гамильтонов путь. [5] В более общем смысле, если G локально конечна, 2-вершинно-связна и имеет любое количество концов, то G 2 имеет гамильтонову окружность. В компактном топологическом пространстве, образованном путем рассмотрения графа как симплициального комплекса и добавления дополнительной бесконечно удаленной точки к каждому из его концов, гамильтонова окружность определяется как подпространство, гомеоморфное евклидовой окружности и покрывающее каждую вершину. [6]
Алгоритмы
Гамильтонов цикл в квадрате двусвязного графа с n вершинами может быть найден за линейное время [7], улучшая первое алгоритмическое решение Лау [8] времени работы O (n 2 ) . Теорема Флейшнера может быть использована для обеспечения 2-приближения к проблеме коммивояжера на узкое место в метрических пространствах . [9]
История
Доказательство теоремы Флейшнера было объявлено Гербертом Флейшнером в 1971 году и опубликовано им в 1974 году, решая гипотезу Криспина Нэша-Вильямса 1966 года, также независимо сделанную Л. В. Бейнеке и Майклом Д. Пламмером . [10] В своем обзоре статьи Флейшнера Нэш-Вильямс писал, что она решила «хорошо известную проблему, которая в течение нескольких лет побеждала изобретательность других теоретиков графов». [11]
Первоначальное доказательство Флейшнера было сложным. Вацлав Хваталь в работе, в которой он изобрел стойкость графа , заметил, что квадрат графа с k- вершинной связью обязательно k- жесткий; он предположил, что 2-жесткие графы являются гамильтоновыми, из чего следовало бы другое доказательство теоремы Флейшнера. [12] Контрпримеры к этой гипотезе были позже обнаружены [13], но возможность того, что конечная оценка устойчивости может подразумевать гамильтоничность, остается важной открытой проблемой в теории графов. Более простое доказательство как теоремы Флейшнера, так и ее расширений Chartrand et al. (1974) , был дан Тихой (1991) , [14], а другое упрощенное доказательство теоремы было дано Георгакопулосом (2009a) . [15]
Рекомендации
Заметки
- ^ Флейшнер (1976) ; Мюттель и Раутенбах (2012) .
- ^ Chartrand et al. (1974) ; Чартран, Лесняк и Чжан (2010)
- ^ Хоббс (1976) , отвечая на гипотезу Бонди (1971) .
- ^ Подземный (1978) ; Бонди (1995) .
- ^ Thomassen (1978) .
- ^ Георгакопулос (2009b) ; Дистель (2012) .
- ^ Альструп, Георгакопулос, Ротенберг, Томассен (2018)
- ^ Лау (1980) ; Паркер и Рардин (1984) .
- ^ Паркер & Rardin (1984) ; Хохбаум и Шмойс (1986) .
- ^ Флейшнер (1974) . По поводу более ранних предположений см. Fleischner and Chartrand, Lesniak & Zhang (2010) .
- ^ MR 0332573 .
- ^ Chvátal (1973) ; Бонди (1995) .
- ^ Bauer, Брусм & Вельдман (2000) .
- ^ Бонди (1995) ; Чартран, Лесняк и Чжан (2010) .
- ^ Chartrand, Лесняк & Zhang (2010) ; Дистель (2012) .
Основные источники
- Альструп, Стивен; Георгакопулос, Агелос; Ротенберг, Ева; Томассен, Карстен (2018), «Гамильтонов цикл в квадрате двусвязного графа в линейном времени», Труды двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 1645–1649, doi : 10.1137 / 1.9781611975031.107 , ISBN 978-1-61197-503-1
- Bauer, D .; Broersma, HJ; Велдман, HJ (2000), «Не каждый 2-жесткий граф является гамильтоновым» , Труды 5-го семинара Twente по графам и комбинаторной оптимизации (Enschede, 1997), Дискретная прикладная математика , 99 (1–3): 317–321, DOI : 10.1016 / S0166-218X (99) 00141-9 , MR 1743840.
- Бонди, Дж. А. (1971), «Панциклические графы», Труды Второй Луизианской конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана , Батон-Руж, штат Луизиана , 1971 г.) , Батон-Руж, Луизиана: Университет штата Луизиана, стр. 167–172, MR 0325458.
- Chartrand, G .; Хоббс, Артур М .; Юнг, HA; Капур, Сан-Франциско; Нэш-Уильямс, К. Сент-Дж. А. (1974), «Квадрат блока гамильтоново связан», Журнал комбинаторной теории , серия B, 16 (3): 290–292, DOI : 10.1016 / 0095-8956 (74 ) 90075-6 , Руководство по ремонту 0345865.
- Chvátal, Вацлав (1973), "Жесткие графики и схемы Гамильтон", дискретная математика , 5 (3): 215-228, DOI : 10.1016 / 0012-365X (73) 90138-6 , МР 0316301.
- Флейшнер, Герберт (1974), «Квадрат каждого двусвязного графа является гамильтоновым», Журнал комбинаторной теории , серия B, 16 : 29–34, DOI : 10.1016 / 0095-8956 (74) 90091-4 , MR 0332573.
- Флейшнер, Х. (1976), «В квадрате графов гамильтоновость и панцикличность, гамильтонова связность и пансвязность являются эквивалентными понятиями», Monatshefte für Mathematik , 82 (2): 125–149, doi : 10.1007 / BF01305995 , MR 0427135.
- Georgakopoulos, Agelos (2009a), "Короткое доказательство теоремы Fleischner в", дискретной математики , 309 (23-24): 6632-6634, DOI : 10.1016 / j.disc.2009.06.024 , MR 2558627.
- Georgakopoulos, Agelos (2009b), "Бесконечные циклы в Гамильтон квадратов локально конечных графов", Успехи математических наук , 220 (3): 670-705, DOI : 10.1016 / j.aim.2008.09.014 , МР 2483226.
- Хоббс, Артур М. (1976), «Квадрат блока является панциклической вершиной», Журнал комбинаторной теории , серия B, 20 (1): 1–4, DOI : 10.1016 / 0095-8956 (76) 90061-7 , Руководство по ремонту 0416980.
- Хохбаум, Дорит С .; Shmoys, David B. (1986), "Единый подход к приближенных алгоритмов для задач узких мест" , Журнал ACM , Нью - Йорк, Нью - Йорк, США: ACM, 33 (3): 533-550, DOI : 10,1145 / 5925,5933.
- Лау, Х.Т. (1980), Нахождение гамильтонова цикла в квадрате блока. , Кандидат наук. дипломная работа, Монреаль: Университет Макгилла. Цитируется Hochbaum & Shmoys (1986) .
- Мюттель, Янина; Раутенбах, Дитер (2012), «Краткое доказательство универсальной версии теоремы Флейшнера», Дискретная математика , 313 (19): 1929–1933, doi : 10.1016 / j.disc.2012.07.032.
- Паркер, Р. Гэри; Rardin, Ronald L. (1984), "Гарантированная эвристика производительности для узкого задачи коммивояжера", операции Research Letters , 2 (6): 269-272, DOI : 10,1016 / 0167-6377 (84) 90077-4.
- Íha, Станислав (1991), "Новое доказательство теоремы Флейшнера", Журнал комбинаторной теории , серия B, 52 (1): 117–123, DOI : 10.1016 / 0095-8956 (91) 90098-5 , MR 1109427.
- Томассен, Карстен (1978), "Гамильтоновы пути в квадратах бесконечных локально конечных блоков", в Bollobás, B. (ed.), Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , Annals of Discrete Математика, 3 , Elsevier, стр. 269-277 , DOI : 10.1016 / S0167-5060 (08) 70512-0 , ISBN 978-0-7204-0843-0, MR 0499125.
- Метро, Полли (1978), «О графах с гамильтоновыми квадратами», Дискретная математика , 21 (3): 323, DOI : 10.1016 / 0012-365X (78) 90164-4 , MR 0522906.
Вторичные источники
- Бонди, Дж. А. (1995), "Основы теории графов: пути и схемы", Справочник по комбинаторике, Vol. 1, 2 , Амстердам: Elsevier, стр. 3–110, MR 1373656.
- Чартран, Гэри ; Лесняк, Линда; Чжан, Пинг (2010), Графы и диграфы (5-е изд.), CRC Press, стр. 139, ISBN 9781439826270.
- Дистель, Рейнхард (2012), «10. Гамильтоновы циклы», Теория графов (PDF) (исправленное 4-е электронное изд.)