Гіпо́теза Ло́васа про гамільто́нів цикл — класична гіпотеза в теорії графів.
Сформульована в четвертому томі «Мистецтва програмування», але, найпевніше, була відома значно раніше.
Формулювання
Кожен скінченний зв'язний вершинно-транзитивний граф містить гамільтонів шлях.
Варіації та узагальнення
- Будь-який скінченний зв'язний вершинно-транзитивний граф, крім п'яти винятків, містить гамільтонів цикл; винятками є:
- Повний граф ,
- Граф Петерсена і граф, отриманий з нього заміною кожної вершини трикутником,
- Граф Коксетера і граф, отриманий з нього заміною кожної вершини трикутником.
- Повний граф .
- Граф Петерсена.
- Граф Коксетера.
Жоден із п'яти винятків не є графом Келі. Це спостереження приводить до слабшої версії гіпотези:
- Будь-який граф Келі скінченної групи містить гамільтонів цикл.
Для орієнтованих графів Келі гіпотеза хибна.
Окремі випадки
- Відомо, що орієнтований граф Келі абелевої групи має гамільтонів шлях.
- З іншого боку, циклічні групи, порядок яких не є степенем простого числа, допускають орієнтований граф Келі без гамільтонового циклу.
- 1986 року Д. Вітте довів, що гіпотеза істинна для графів Келі p-груп.
- Питання залишається відкритим для діедральних груп.
Відомо, що для симетричної групи гіпотеза істинна для таких наборів твірних:
- (довгий цикл і транспозиція).
- (твірні Коксетера). У цьому випадку гамільтонів цикл будується [en].
- .
Посилання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Gipo teza Lo vasa pro gamilto niv cikl klasichna gipoteza v teoriyi grafiv Gamiltoniv shlyah u grafi Keli simetrichnoyi grupi Sformulovana v chetvertomu tomi Mistectva programuvannya ale najpevnishe bula vidoma znachno ranishe FormulyuvannyaKozhen skinchennij zv yaznij vershinno tranzitivnij graf mistit gamiltoniv shlyah Variaciyi ta uzagalnennyaBud yakij skinchennij zv yaznij vershinno tranzitivnij graf krim p yati vinyatkiv mistit gamiltoniv cikl vinyatkami ye Povnij graf K 2 displaystyle K 2 Graf Petersena i graf otrimanij z nogo zaminoyu kozhnoyi vershini trikutnikom Graf Koksetera i graf otrimanij z nogo zaminoyu kozhnoyi vershini trikutnikom Povnij graf K 2 displaystyle K 2 Graf Petersena Graf Koksetera Zhoden iz p yati vinyatkiv ne ye grafom Keli Ce sposterezhennya privodit do slabshoyi versiyi gipotezi Bud yakij graf Keli skinchennoyi grupi mistit gamiltoniv cikl Dlya oriyentovanih grafiv Keli gipoteza hibna Okremi vipadkiVidomo sho oriyentovanij graf Keli abelevoyi grupi maye gamiltoniv shlyah Z inshogo boku ciklichni grupi poryadok yakih ne ye stepenem prostogo chisla dopuskayut oriyentovanij graf Keli bez gamiltonovogo ciklu 1986 roku D Vitte doviv sho gipoteza istinna dlya grafiv Keli p grup Pitannya zalishayetsya vidkritim dlya diedralnih grup Vidomo sho dlya simetrichnoyi grupi gipoteza istinna dlya takih naboriv tvirnih a 1 2 n b 1 2 displaystyle a 1 2 dots n b 1 2 dovgij cikl i transpoziciya s 1 1 2 s 2 2 3 s n 1 n 1 n displaystyle s 1 1 2 s 2 2 3 dots s n 1 n 1 n tvirni Koksetera U comu vipadku gamiltoniv cikl buduyetsya en a 1 2 b 1 2 3 4 c 2 3 4 5 displaystyle a 1 2 b 1 2 3 4 cdots c 2 3 4 5 cdots PosilannyaHolsztynski W Strube R F E 1978 Paths and circuits in finite groups Discrete Mathematics 22 3 263 272 doi 10 1016 0012 365X 78 90059 6 MR 0522721