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

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

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

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

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

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

Розширення

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

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

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

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

Історія

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

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

Примітки

Шаблон:Reflist

Література

  1. ↑ Хоббс (Шаблон:Harvtxt), відповідь на гіпотезу Бонді (Шаблон:Sfn0).
  2. ↑ Шаблон:Harvtxt. Про раніші гіпотези див. у Фляйшнера і Чартранда, Лесняка і Чжана (Шаблон:Harvtxt).
  3. ↑ Шаблон:MathSciNet.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Теорема_Фляйшнера&oldid=9937