Підгамільтонів граф
Підгамільтонів граф — це підграф планарного гамільтонового графаШаблон:SfnШаблон:Sfn.
Визначення
Граф підгамільтонів, якщо є підграфом деякого іншого графа з тією ж множиною вершин, при цьому граф планарний і містить гамільтонів цикл. Щоб ці умови виконувалися, сам граф має бути планарним і, крім того, має бути можливість додати ребра зі збереженням планарності, щоб створити у розширеному графі цикл, який проходить усі вершини рівно по одному разу. Граф називають гамільтоновим розширенням графа Шаблон:Sfn.
Можна було б дати визначення підгамільтонового графа як підграфа гамільтонового графа без вимоги, що цей більший граф має ту ж множину вершин. Тобто в цьому альтернативному визначенні можна було б додавати вершини та ребра. Однак, якщо граф можна зробити гамільтоновим за допомогою додавання вершин і ребер, його можна зробити таким і без додавання вершин, тому ця додаткова свобода не змінює визначення[1].
У підгамільтоновому графі цикл — це циклічна послідовність вершин, така, що додавання ребра в будь-яку пару вершин у послідовності не порушує планарності графа. Граф є підгамільтоновим тоді й лише тоді, коли він має підгамільтонів циклШаблон:Sfn.
Історія та застосування
Клас підгамільтонових графів (але не назву класу) запропонували Бернгарт та КайненШаблон:Sfn. Вони довели, що це точно ті графи, які мають дві сторінки в книжкових вкладенняхШаблон:Sfn. Підгамільтонові графи та гамільтонові розширення використовують також у галузі візуалізації графів для задач вкладення графів у універсальну множину точок, одночасного вкладення кількох графів та пошарового малювання графаШаблон:Sfn.
Пов'язані сімейства графів
Деякі класи планарних графів обов'язково гамільтонові, тому й підгамільтонові. Сюди входять 4-вершинно-зв'язні графиШаблон:Sfn та графи ХалінаШаблон:Sfn.
Будь-який планарний граф із найбільшим степенем, що не перевищує чотирьох, є підгамільтоновимШаблон:Sfn, як і будь-який планарний граф без розділювальних трикутниківШаблон:Sfn[2]. Якщо ребра довільного планарного графа розбито на шляхи довжини два[3], граф, що вийшов, завжди підгамільтонівШаблон:Sfn.
Примітки
Література
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Стаття
- ↑ Наприклад, у технічному звіті 2003 року «Book embeddings of graphs and a theorem of Whitney», Пол Кайнен визначає підгамільтонові графи як підграфи планарних гамільтонових графів без обмеження множини вершин у розширеному графі, але пише, що «у визначенні підгамільтонового графа можна вимагати, що розширення здійснюється лише додаванням ребер»
- ↑ Розділювальний трикутник — це подграф, що містить три вершини і три ребра, видалення якого (разом із суміжними ребрами) призводить до розбиття графа на незв'язані частини Шаблон:Harvard citation.
- ↑ Тобто кожне ребро перетворено на два ребра шляхом поміщення на ребро вершини.