Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Теорема Фляйшнера твердження в теорії графів що дає достатню умову щоб граф містив гамільтонів цикл якщо граф G displays

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

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

Теорема Фляйшнера — твердження в теорії графів, що дає достатню умову, щоб граф містив гамільтонів цикл: якщо граф є 2-вершинно-зв'язним, то квадрат графа гамільтонів. Названа ім'ям [en], який опублікував доведення теореми .

image
Вершинно 2-зв'язний граф, його квадрат і гамільтонів цикл у квадраті

Визначення та твердження

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

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

Розширення

У теоремі Фляйшнера можна накласти обмеження на гамільтонів цикл так, щоб він включав три вибраних ребра, які проходять через дві вибрані вершини.

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

Якщо граф G не 2-вершинно-зв'язний, його квадрат може мати, а може і не мати гамільтонового циклу і визначення, чи має граф такий цикл, є NP-повною задачею.

Нескінченний граф не може мати гамільтонового циклу, оскільки будь-який цикл скінченний, але [en] довів, що у випадку, коли G є нескінченним локально скінченним 2-вершинно-зв'язним графом з єдиним кінцем, то G2 обов'язково має двічі нескінченний гамільтонів шлях. Загальніше, якщо G локально скінченний, 2-вершинно-зв'язний і має будь-яке число кінців, то G2 має гамільтонів цикл. У компактному топологічному просторі, утвореному розглядом графа як симпліційного комплексу і доданням точки на нескінченності для кожного кінця графа, гамільтонів цикл визначають як підпростір, який гомеоморфний евклідовому колу і покриває всі вершини.

Історія

Про доведення теореми [de] оголосив 1971 року й опублікував 1974 року, вирішивши цим гіпотезу 1966 року [en], яку незалежно висловили також [en] і [en]. У своєму огляді статті Фляйшнера Неш-Вільямс пише, що той вирішив «добре відому проблему, об яку кілька років розбивалася винахідливість інших теоретиків теорії графів».

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

Примітки

  1. Fleischner, 1976, с. 125–149.
  2. Müttel, Rautenbach, 2012.
  3. Chartrand, Hobbs, Jung, Kapoor, 1974.
  4. Chartrand, Lesniak, Zhang, 2010.
  5. Хоббс (Hobbs, (1976)), відповідь на гіпотезу Бонді (Bondy, 1971).
  6. Underground, 1978.
  7. Bondy, 1995.
  8. Thomassen, (1978).
  9. Georgakopoulos, 2009b.
  10. Diestel, 2012.
  11. Fleischner, (1974). Про раніші гіпотези див. у Фляйшнера і Чартранда, Лесняка і Чжана (Chartrand, Lesniak, Zhang, (2010)).
  12. MR0332573.
  13. Chvátal, 1973.
  14. Bauer, Broersma, Veldman, 2000.
  15. Říha, 1991.
  16. Georgakopoulos, 2009a.

Література

  • D. Bauer, H. J. Broersma, H. J. Veldman. Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997) // Discrete Applied Mathematics. — 2000. — Vol. 99, no. 1—3. — P. 317–321. — DOI:10.1016/S0166-218X(99)00141-9.
  • J. A. Bondy. Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971). — Baton Rouge, Louisiana : Louisiana State University, 1971. — P. 167–172.
  • G. Chartrand, Arthur M. Hobbs, H. A. Jung, S. F. Kapoor, C. St. J. A. Nash-Williams. The square of a block is Hamiltonian connected // . — 1974. — Vol. 16. — P. 290–292. — (Series B). — DOI:10.1016/0095-8956(74)90075-6.
  • Václav Chvátal. Tough graphs and Hamiltonian circuits // . — 1973. — Vol. 5, iss. 3. — P. 215–228. — DOI:10.1016/0012-365X(73)90138-6.
  • Herbert Fleischner. The square of every two-connected graph is Hamiltonian // . — 1974. — Vol. 16. — (Series B). — DOI:10.1016/0095-8956(74)90091-4.
  • H. Fleischner. In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts // Monatshefte für Mathematik. — 1976. — Vol. 82, iss. 2. — DOI:10.1007/BF01305995.
  • Agelos Georgakopoulos. A short proof of Fleischner's theorem // . — 2009a. — Vol. 309, iss. 23—24. — P. 6632–6634. — DOI:10.1016/j.disc.2009.06.024.
  • Agelos Georgakopoulos. Infinite Hamilton cycles in squares of locally finite graphs // Advances in Mathematics. — 2009b. — Vol. 220, iss. 3. — P. 670–705. — DOI:10.1016/j.aim.2008.09.014.
  • Arthur M. Hobbs. The square of a block is vertex pancyclic // . — 1976. — Vol. 20, iss. 1. — P. 1–4. — (Series B). — DOI:10.1016/0095-8956(76)90061-7.
  • Janina Müttel, Dieter Rautenbach. A short proof of the versatile version of Fleischner’s theorem // . — 2012. — DOI:10.1016/j.disc.2012.07.032.
  • Stanislav Říha. A new proof of the theorem by Fleischner // . — 1991. — Vol. 52, iss. 1. — P. 117–123. — (Series B). — DOI:10.1016/0095-8956(91)90098-5.
  • Carsten Thomassen. Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) / B. Bollobás. — Elsevier, 1978. — Т. 3. — С. 269–277. — (Annals of Discrete Mathematics) — . — DOI:10.1016/S0167-5060(08)70512-0.
  • Paris Underground. On graphs with Hamiltonian squares // . — 1978. — Vol. 21, iss. 3. — P. 323. — DOI:10.1016/0012-365X(78)90164-4.
  • J. A. Bondy. Handbook of combinatorics, Vol. 1, 2. — Amsterdam : Elsevier, 1995. — С. 3–110.
  • Gary Chartrand, Linda Lesniak, Ping Zhang. Graphs & Digraphs. — 5th. — CRC Press, 2010. — С. 139. — .
  • Reinhard Diestel. Graph Theory. — corrected 4th electronic. — 2012.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Teorema Flyajshnera tverdzhennya v teoriyi grafiv sho daye dostatnyu umovu shob graf mistiv gamiltoniv cikl yaksho graf G displaystyle G ye 2 vershinno zv yaznim to kvadrat grafa G displaystyle G gamiltoniv Nazvana im yam en yakij opublikuvav dovedennya teoremi Vershinno 2 zv yaznij graf jogo kvadrat i gamiltoniv cikl u kvadratiViznachennya ta tverdzhennyaNeoriyentovanij graf G ye gamiltonovim yaksho vin mistit cikl yakij prohodit cherez kozhnu vershinu rivno odin raz Graf ye 2 vershinno zv yaznim yaksho vin ne mistit zchlenuvalnih vershin tobto vershin vidalennya yakih robit graf sho zalishivsya nezv yaznim Ne bud yakij 2 vershinno zv yaznij graf ye gamiltonovim Kontrprikladami ye graf Petersena ta povnij dvokovij graf K2 3 Kvadrat grafa G ce graf G2 yakij maye tu samu mnozhinu vershin sho j graf G i v yakomu dvi vershini sumizhni todi j lishe todi koli vidstan mizh nimi v G ne perevishuye 2 Teorema Flyajshnera stverdzhuye sho kvadrat skinchennogo 2 vershinno zv yaznogo grafa z troma i bilshe vershinami zavzhdi gamiltoniv Ekvivalentno vershini bud yakogo 2 vershinno zv yaznogo grafa G mozhna organizuvati v ciklichnij poryadok tak sho vidstan u grafi G mizh vershinami sumizhnimi v comu poryadku ne perevishuye 2 RozshirennyaU teoremi Flyajshnera mozhna naklasti obmezhennya na gamiltoniv cikl tak shob vin vklyuchav tri vibranih rebra yaki prohodyat cherez dvi vibrani vershini Krim nayavnosti gamiltonovogo ciklu kvadrat 2 vershinno zv yaznogo grafa G maye buti takozh gamiltonovo pov yazanim sho oznachaye sho vin maye gamiltoniv shlyah yakij pochinayetsya i zakinchuyetsya v bud yakih dvoh vibranih vershinah i 1 gamiltoniv sho oznachaye sho yaksho vidaliti bud yaku vershinu graf sho zalishivsya takozh mistitime gamiltoniv cikl Graf maye buti takozh vershinno panciklichnim sho oznachaye sho dlya bud yakoyi vershini v ta bud yakogo cilogo k z 3 k V G isnuye cikl dovzhini k sho mistit v Yaksho graf G ne 2 vershinno zv yaznij jogo kvadrat mozhe mati a mozhe i ne mati gamiltonovogo ciklu i viznachennya chi maye graf takij cikl ye NP povnoyu zadacheyu Neskinchennij graf ne mozhe mati gamiltonovogo ciklu oskilki bud yakij cikl skinchennij ale en doviv sho u vipadku koli G ye neskinchennim lokalno skinchennim 2 vershinno zv yaznim grafom z yedinim kincem to G2 obov yazkovo maye dvichi neskinchennij gamiltoniv shlyah Zagalnishe yaksho G lokalno skinchennij 2 vershinno zv yaznij i maye bud yake chislo kinciv to G2 maye gamiltoniv cikl U kompaktnomu topologichnomu prostori utvorenomu rozglyadom grafa yak simplicijnogo kompleksu i dodannyam tochki na neskinchennosti dlya kozhnogo kincya grafa gamiltoniv cikl viznachayut yak pidprostir yakij gomeomorfnij evklidovomu kolu i pokrivaye vsi vershini IstoriyaPro dovedennya teoremi de ogolosiv 1971 roku j opublikuvav 1974 roku virishivshi cim gipotezu 1966 roku en yaku nezalezhno vislovili takozh en i en U svoyemu oglyadi statti Flyajshnera Nesh Vilyams pishe sho toj virishiv dobre vidomu problemu ob yaku kilka rokiv rozbivalasya vinahidlivist inshih teoretikiv teoriyi grafiv Originalne dovedennya Flyajshnera bulo skladnim Vaclav Hvatal u praci v yakij vin uviv ponyattya zhorstkosti grafa zauvazhiv sho kvadrat k vershinno zv yaznogo grafa obov yazkovo k zhorstkij Vin visloviv pripushennya sho 2 zhorstki grafi ye gamiltonovimi z chogo vijshlo b inshe dovedennya teoremi Flyajshnera Piznishe viyavleno kontrprikladi do ciyeyi gipotezi ale mozhlivist sho zi skinchennoyi mezhi zhorstkosti mogla b viplivati gamiltonovist zalishilasya vazhlivoyu vidkritoyu problemoyu teoriyi grafiv Prostishe dovedennya yak teoremi Flyajshnera tak i yiyi rozshiren yaki zrobili Chartrand Hobbs Yang i Kapuur nadav Riha a she odne sproshene dovedennya teoremi nadav Georgakopulus PrimitkiFleischner 1976 s 125 149 Muttel Rautenbach 2012 Chartrand Hobbs Jung Kapoor 1974 Chartrand Lesniak Zhang 2010 Hobbs Hobbs 1976 vidpovid na gipotezu Bondi Bondy 1971 Underground 1978 Bondy 1995 Thomassen 1978 Georgakopoulos 2009b Diestel 2012 Fleischner 1974 Pro ranishi gipotezi div u Flyajshnera i Chartranda Lesnyaka i Chzhana Chartrand Lesniak Zhang 2010 MR0332573 Chvatal 1973 Bauer Broersma Veldman 2000 Riha 1991 Georgakopoulos 2009a LiteraturaD Bauer H J Broersma H J Veldman Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization Enschede 1997 Discrete Applied Mathematics 2000 Vol 99 no 1 3 P 317 321 DOI 10 1016 S0166 218X 99 00141 9 J A Bondy Proceedings of the Second Louisiana Conference on Combinatorics Graph Theory and Computing Louisiana State Univ Baton Rouge La 1971 Baton Rouge Louisiana Louisiana State University 1971 P 167 172 G Chartrand Arthur M Hobbs H A Jung S F Kapoor C St J A Nash Williams The square of a block is Hamiltonian connected 1974 Vol 16 P 290 292 Series B DOI 10 1016 0095 8956 74 90075 6 Vaclav Chvatal Tough graphs and Hamiltonian circuits 1973 Vol 5 iss 3 P 215 228 DOI 10 1016 0012 365X 73 90138 6 Herbert Fleischner The square of every two connected graph is Hamiltonian 1974 Vol 16 Series B DOI 10 1016 0095 8956 74 90091 4 H Fleischner In the square of graphs Hamiltonicity and pancyclicity Hamiltonian connectedness and panconnectedness are equivalent concepts Monatshefte fur Mathematik 1976 Vol 82 iss 2 DOI 10 1007 BF01305995 Agelos Georgakopoulos A short proof of Fleischner s theorem 2009a Vol 309 iss 23 24 P 6632 6634 DOI 10 1016 j disc 2009 06 024 Agelos Georgakopoulos Infinite Hamilton cycles in squares of locally finite graphs Advances in Mathematics 2009b Vol 220 iss 3 P 670 705 DOI 10 1016 j aim 2008 09 014 Arthur M Hobbs The square of a block is vertex pancyclic 1976 Vol 20 iss 1 P 1 4 Series B DOI 10 1016 0095 8956 76 90061 7 Janina Muttel Dieter Rautenbach A short proof of the versatile version of Fleischner s theorem 2012 DOI 10 1016 j disc 2012 07 032 Stanislav Riha A new proof of the theorem by Fleischner 1991 Vol 52 iss 1 P 117 123 Series B DOI 10 1016 0095 8956 91 90098 5 Carsten Thomassen Advances in Graph Theory Cambridge Combinatorial Conf Trinity College Cambridge 1977 B Bollobas Elsevier 1978 T 3 S 269 277 Annals of Discrete Mathematics ISBN 978 0 7204 0843 0 DOI 10 1016 S0167 5060 08 70512 0 Paris Underground On graphs with Hamiltonian squares 1978 Vol 21 iss 3 P 323 DOI 10 1016 0012 365X 78 90164 4 J A Bondy Handbook of combinatorics Vol 1 2 Amsterdam Elsevier 1995 S 3 110 Gary Chartrand Linda Lesniak Ping Zhang Graphs amp Digraphs 5th CRC Press 2010 S 139 ISBN 9781439826270 Reinhard Diestel Graph Theory corrected 4th electronic 2012

Дата публікації:
Топ