Теорема Фляйшнера Теорема Фляйшнера — твердження в теорії графів, що дає достатню умову, щоб граф містив гамільтонів цикл: якщо граф є 2-вершинно-зв'язним, то квадрат графа гамільтонів. Названа ім'ям Герберта Фляйшнера[en], який опублікував доведення теореми 1974 року. Визначення та твердженняНеорієнтований граф G є гамільтоновим, якщо він містить цикл, який проходить через кожну вершину рівно один раз. Граф є 2-вершинно-зв'язним, якщо він не містить зчленувальних вершин, тобто вершин, видалення яких робить граф, що залишився, незв'язним. Не будь-який 2-вершинно-зв'язний граф є гамільтоновим. Контрприкладами є граф Петерсена та повний двоковий граф K2,3. Квадрат графа G — це граф G2, який має ту саму множину вершин, що й граф G, і в якому дві вершини суміжні тоді й лише тоді, коли відстань між ними в G не перевищує 2. Теорема Фляйшнера стверджує, що квадрат скінченного 2-вершинно-зв'язного графа з трьома і більше вершинами завжди гамільтонів. Еквівалентно, вершини будь-якого 2-вершинно-зв'язного графа G можна організувати в циклічний порядок, так що відстань у графі G між вершинами, суміжними в цьому порядку, не перевищує 2. РозширенняУ теоремі Фляйшнера можна накласти обмеження на гамільтонів цикл так, щоб він включав три вибраних ребра, які проходять через дві вибрані вершини[1][2]. Крім наявності гамільтонового циклу, квадрат 2-вершинно-зв'язного графа G має бути також гамільтоново пов'язаним (що означає, що він має гамільтонів шлях, який починається і закінчується в будь-яких двох вибраних вершинах) і 1-гамільтонів (що означає, що якщо видалити будь-яку вершину, граф, що залишився, також міститиме гамільтонів цикл)[3][4]. Граф має бути також вершинно панциклічним, що означає, що для будь-якої вершини v та будь-якого цілого k з 3 ≤ k ≤ |V(G)| існує цикл довжини k, що містить v[5] . Якщо граф G не 2-вершинно-зв'язний, його квадрат може мати, а може і не мати гамільтонового циклу і визначення, чи має граф такий цикл, є NP-повною задачею[6][7]. Нескінченний граф не може мати гамільтонового циклу, оскільки будь-який цикл скінченний, але Карстен Томассен[en] довів, що у випадку, коли G є нескінченним локально скінченним 2-вершинно-зв'язним графом з єдиним кінцем, то G2 обов'язково має двічі нескінченний гамільтонів шлях[8]. Загальніше, якщо G локально скінченний, 2-вершинно-зв'язний і має будь-яке число кінців, то G2 має гамільтонів цикл. У компактному топологічному просторі, утвореному розглядом графа як симпліційного комплексу і доданням точки на нескінченності для кожного кінця графа, гамільтонів цикл визначають як підпростір, який гомеоморфний евклідовому колу і покриває всі вершини[9][10]. ІсторіяПро доведення теореми Герберт Фляйшнер[de] оголосив 1971 року й опублікував 1974 року, вирішивши цим гіпотезу 1966 року Неш-Вільямса[en], яку незалежно висловили також Л. В. Байник[en] і Пламмер[en][11]. У своєму огляді статті Фляйшнера Неш-Вільямс пише, що той вирішив «добре відому проблему, об яку кілька років розбивалася винахідливість інших теоретиків теорії графів»[12]. Оригінальне доведення Фляйшнера було складним. Вацлав Хватал у праці, в якій він увів поняття жорсткості графа, зауважив, що квадрат k-вершинно-зв'язного графа обов'язково k-жорсткий. Він висловив припущення, що 2-жорсткі графи є гамільтоновими, з чого вийшло б інше доведення теореми Фляйшнера[13][7]. Пізніше виявлено контрприклади до цієї гіпотези[14], але можливість, що зі скінченної межі жорсткості могла б випливати гамільтоновість, залишилася важливою відкритою проблемою теорії графів. Простіше доведення як теореми Фляйшнера, так і її розширень, які зробили Чартранд, Хоббс, Янг і Капуур[3], надав Ріха[15][7][4], а ще одне спрощене доведення теореми надав Георгакопулус[16][4][10]. Примітки
Література
|
Portal di Ensiklopedia Dunia
