Гіпо́теза Ло́васа про гамільто́нів цикл — класична гіпотеза в теорії графів.
Сформульована в четвертому томі «Мистецтва програмування», але, найпевніше, була відома значно раніше.
Формулювання Кожен скінченний зв'язний вершинно-транзитивний граф містить гамільтонів шлях.
Варіації та узагальнення
Будь-який скінченний зв'язний вершинно-транзитивний граф, крім п'яти винятків, містить гамільтонів цикл; винятками є: Повний граф , Граф Петерсена і граф, отриманий з нього заміною кожної вершини трикутником, Граф Коксетера і граф, отриманий з нього заміною кожної вершини трикутником. Жоден із п'яти винятків не є графом Келі. Це спостереження приводить до слабшої версії гіпотези:
Будь-який граф Келі скінченної групи містить гамільтонів цикл.
Для орієнтованих графів Келі гіпотеза хибна.
Окремі випадки
Відомо, що орієнтований граф Келі абелевої групи має гамільтонів шлях. З іншого боку, циклічні групи, порядок яких не є степенем простого числа, допускають орієнтований граф Келі без гамільтонового циклу.. 1986 року Д. Вітте довів, що гіпотеза істинна для графів Келі p-груп. Питання залишається відкритим для діедральних груп.
Відомо, що для симетричної групи гіпотеза істинна для таких наборів твірних:
(довгий цикл і транспозиція). (твірні Коксетера). У цьому випадку гамільтонів цикл будується . .
Література
Посилання