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

Теорема о гамильтоновых графах

Граф с двумя вершинами, его квадрат и гамильтонов цикл в квадрате

В теории графов , разделе математики, теорема Флейшнера дает достаточное условие для того, чтобы граф содержал гамильтонов цикл . Она утверждает, что если — граф с двумя вершинами , то квадрат является гамильтоновым. Она названа в честь Герберта Флейшнера , который опубликовал ее доказательство в 1974 году. ${\displaystyle G}$ ${\displaystyle G}$

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

Неориентированный граф является гамильтоновым, если он содержит цикл , который касается каждой из его вершин ровно один раз. Он является 2-вершинно-связным, если у него нет вершины сочленения, вершины, удаление которой оставшийся граф останется несвязным. Не каждый 2-вершинно-связный граф является гамильтоновым; контрпримерами являются граф Петерсена и полный двудольный граф . ${\displaystyle G}$ ${\displaystyle K_{2,3}}$

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

Расширения

В теореме Флейшнера можно ограничить гамильтонов цикл в так, чтобы для заданных вершин и из он включал два ребра инцидентные с и одно ребро инцидентные с . Более того, если и смежны в , то это три различных ребра из . ^[1] ${\displaystyle G^{2}}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$

В дополнение к наличию гамильтонова цикла, квадрат графа с двумя вершинами должен быть также гамильтоново связным (что означает, что он имеет гамильтонов путь, начинающийся и заканчивающийся в любых двух указанных вершинах) и 1-гамильтоновым (что означает, что если удалить любую вершину, оставшийся граф все еще будет иметь гамильтонов цикл). ^[2] Он также должен быть вершинно панциклическим , что означает, что для каждой вершины и каждого целого числа с , существует цикл длины, содержащий . ^[3] ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle 3\leq k\leq |V(G)}$ ${\displaystyle k}$ ${\displaystyle v}$

Если граф не является 2-вершинно-связным, то его квадрат может иметь или не иметь гамильтонов цикл, и определение того, имеет ли он его, является NP-полной задачей . ^[4] ${\displaystyle G}$

Бесконечный граф не может иметь гамильтонов цикл, потому что каждый цикл конечен, но Карстен Томассен доказал, что если является бесконечным локально конечным 2-вершинно связным графом с одним концом , то обязательно имеет дважды бесконечный гамильтонов путь. ^[5] В более общем случае, если является локально конечным, 2-вершинно связным и имеет любое количество концов, то имеет гамильтонову окружность. В компактном топологическом пространстве, образованном путем рассмотрения графа как симплициального комплекса и добавления дополнительной точки на бесконечности к каждому из его концов, гамильтонова окружность определяется как подпространство, гомеоморфное евклидовой окружности и покрывающее каждую вершину. ^[6] ${\displaystyle G}$ ${\displaystyle G^{2}}$ ${\displaystyle G}$ ${\displaystyle G^{2}}$

Алгоритмы

Гамильтонов цикл в квадрате -вершинного 2-связного графа может быть найден за линейное время, ^[7] улучшая первое алгоритмическое решение Лау ^[8] времени выполнения . Теорема Флейшнера может быть использована для предоставления 2-приближения к проблеме коммивояжера с узким местом в метрических пространствах . ^[9] ${\displaystyle n}$ ${\displaystyle O(n^{2})}$

История

Доказательство теоремы Флейшнера было объявлено Гербертом Флейшнером в 1971 году и опубликовано им в 1974 году, решая гипотезу Криспина Нэша-Вильямса 1966 года, также выдвинутую независимо Л. В. Бейнеке и Майклом Д. Пламмером . ^[10] В своем обзоре статьи Флейшнера Нэш-Вильямс написал, что она решила «хорошо известную проблему, которая в течение нескольких лет побеждала изобретательность других специалистов по теории графов». ^[11]

Первоначальное доказательство Флейшнера было сложным. Вацлав Хватал , в работе, в которой он изобрел прочность графа , заметил, что квадрат -вершинно-связного графа обязательно является -жестким; он предположил , что 2-жесткие графы являются гамильтоновыми, из чего следовало бы другое доказательство теоремы Флейшнера. ^[12] Позднее были обнаружены контрпримеры к этой гипотезе, ^[13] но возможность того, что конечная граница прочности может подразумевать гамильтоновость, остается важной открытой проблемой в теории графов. Более простое доказательство как теоремы Флейшнера, так и ее расширений Шартранда и др. (1974), было дано Ржихой (1991), ^[14] , а другое упрощенное доказательство теоремы было дано Георгакопулосом (2009a). ^[15] ${\displaystyle k}$ ${\displaystyle k}$

Ссылки

Примечания

1. Флейшнер (1976); Мюттель и Раутенбах (2012).
2. Чартран и др. (1974); Чартран, Лесняк и Чжан (2010)
3. Хоббс (1976), отвечая на гипотезу Бонди (1971).
4. Андеграунд (1978); Бонди (1995).
5. Томассен (1978).
6. Георгакопулос (2009b); Дистель (2012).
7. Альструп и др. (2018)
8. Лау (1980); Паркер и Рардин (1984).
9. Паркер и Рардин (1984); Хохбаум и Шмойс (1986).
10. Флейшнер (1974). Более ранние предположения см. в работах Флейшнера и Шартрана, Лесняка и Чжана (2010).
11. МР 0332573.
12. Хватал (1973); Бонди (1995).
13. Бауэр, Броерсма и Вельдман (2000).
14. Бонди (1995); Чартран, Лесняк и Чжан (2010).
15. Чартран, Лесняк и Чжан (2010); Дистель (2012).

Первичные источники

• Alstrup, Stephen; Georgakopoulos, Agelos; Rotenberg, Eva; Thomassen, Carsten (2018), «Гамильтонов цикл в квадрате 2-связного графа за линейное время», Труды двадцать девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 1645–1649, doi : 10.1137/1.9781611975031.107 , ISBN 978-1-61197-503-1
• Бауэр, Д.; Броерсма, Х. Дж.; Вельдман, Х. Дж. (2000), «Не каждый 2-жесткий граф является гамильтоновым», Труды 5-го семинара в Твенте по графам и комбинаторной оптимизации (Энсхеде, 1997), Дискретная прикладная математика , 99 (1–3): 317–321, doi : 10.1016/S0166-218X(99)00141-9 , MR  1743840.
• Бонди, JA (1971), «Панциклические графы», Труды Второй Луизианской конференции по комбинаторике, теории графов и вычислениям (Университет штата Луизиана, Батон-Руж, Луизиана, 1971) , Батон-Руж, Луизиана: Университет штата Луизиана, стр. 167–172, MR  0325458.
• Chartrand, G. ; Hobbs, Arthur M. ; Jung, HA; Kapoor, SF; Nash-Williams, C. St. JA (1974), "Квадрат блока гамильтоново связен", Журнал комбинаторной теории , Серия B, 16 (3): 290–292, doi : 10.1016/0095-8956(74)90075-6 , MR  0345865.
• Chvátal, Václav (1973), «Жесткие графы и гамильтоновы схемы», Discrete Mathematics , 5 (3): 215–228, doi : 10.1016/0012-365X(73)90138-6 , MR  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.
• Георгакопулос, Агелос (2009a), «Краткое доказательство теоремы Флейшнера», Дискретная математика , 309 (23–24): 6632–6634, doi : 10.1016/j.disc.2009.06.024 , MR  2558627.
• Георгакопулос, Агелос (2009b), «Бесконечные гамильтоновы циклы в квадратах локально конечных графов», Advances in Mathematics , 220 (3): 670–705, doi : 10.1016/j.aim.2008.09.014 , MR  2483226.
• Хоббс, Артур М. (1976), «Квадрат блока вершинно панцикличен», Журнал комбинаторной теории , Серия B, 20 (1): 1–4, doi : 10.1016/0095-8956(76)90061-7 , MR  0416980.
• Хохбаум, Дорит С.; Шмойс , Дэвид Б. (1986), «Единый подход к аппроксимационным алгоритмам для проблем с узкими местами», Журнал ACM , 33 (3), Нью-Йорк, США: ACM: 533–550, doi :10.1145/5925.5933.
• Лау, Х.Т. (1980), Нахождение гамильтонова цикла в квадрате блока. , докторская диссертация, Монреаль: Университет Макгилла. Как цитируют Хохбаум и Шмойс (1986).
• Мюттель, Янина; Раутенбах, Дитер (2012), «Краткое доказательство универсальной версии теоремы Флейшнера», Дискретная математика , 313 (19): 1929–1933, doi : 10.1016/j.disc.2012.07.032.
• Паркер, Р. Гэри; Рардин, Рональд Л. (1984), «Гарантированная эвристика производительности для задачи коммивояжера с узким местом», Operations Research Letters , 2 (6): 269–272, doi :10.1016/0167-6377(84)90077-4.
• Ржига, Станислав (1991), «Новое доказательство теоремы Флейшнера», Журнал комбинаторной теории , Серия B, 52 (1): 117–123, doi : 10.1016/0095-8956(91)90098-5 , MR  1109427.
• Томассен, Карстен (1978), «Гамильтоновы пути в квадратах бесконечных локально конечных блоков», в Bollobás, B. (ред.), Advances in Graph Theory (Кембриджская комбинаторная конференция, Тринити-колледж, Кембридж, 1977), Annals of Discrete Mathematics, т. 3, Elsevier, стр. 269–277, doi :10.1016/S0167-5060(08)70512-0, ISBN 978-0-7204-0843-0, МР  0499125.
• Underground, Polly (1978), «О графах с гамильтоновыми квадратами», Discrete Mathematics , 21 (3): 323, doi : 10.1016/0012-365X(78)90164-4 , MR  0522906.

Вторичные источники

• Бонди, JA (1995), «Основы теории графов: пути и контуры», Справочник по комбинаторике, т. 1, 2 , Амстердам: Elsevier, стр. 3–110, MR  1373656.
• Шартран, Гэри ; Лесняк, Линда; Чжан, Пин (2010), Графики и орграфы (5-е изд.), CRC Press, стр. 139, ISBN 9781439826270.
• Дистель, Рейнхард (2012), "10. Гамильтоновы циклы", Теория графов (PDF) (исправленное 4-е электронное издание)