Підгамільтонів граф

Підгамільтонів граф — це підграф планарного гамільтонового графа[1][2].

Визначення

Граф підгамільтонів, якщо є підграфом деякого іншого графа з тією ж множиною вершин, при цьому граф планарний і містить гамільтонів цикл. Щоб ці умови виконувалися, сам граф має бути планарним і, крім того, має бути можливість додати ребра зі збереженням планарності, щоб створити у розширеному графі цикл, який проходить усі вершини рівно по одному разу. Граф називають гамільтоновим розширенням графа [2].

Можна було б дати визначення підгамільтонового графа як підграфа гамільтонового графа без вимоги, що цей більший граф має ту ж множину вершин. Тобто в цьому альтернативному визначенні можна було б додавати вершини та ребра. Однак, якщо граф можна зробити гамільтоновим за допомогою додавання вершин і ребер, його можна зробити таким і без додавання вершин, тому ця додаткова свобода не змінює визначення[3].

У підгамільтоновому графі цикл — це циклічна послідовність вершин, така, що додавання ребра в будь-яку пару вершин у послідовності не порушує планарності графа. Граф є підгамільтоновим тоді й лише тоді, коли він має підгамільтонів цикл[4].

Історія та застосування

Клас підгамільтонових графів (але не назву класу) запропонували Бернгарт та Кайнен[5]. Вони довели, що це точно ті графи, які мають дві сторінки в книжкових вкладеннях[6]. Підгамільтонові графи та гамільтонові розширення використовують також у галузі візуалізації графів для задач вкладення графів у універсальну множину точок, одночасного вкладення кількох графів та пошарового малювання графа[2].

Пов'язані сімейства графів

Деякі класи планарних графів обов'язково гамільтонові, тому й підгамільтонові. Сюди входять 4-вершинно-зв'язні графи[7] та графи Халіна[8].

Будь-який планарний граф із найбільшим степенем, що не перевищує чотирьох, є підгамільтоновим[4], як і будь-який планарний граф без розділювальних трикутників[9][10]. Якщо ребра довільного планарного графа розбито на шляхи довжини два[11], граф, що вийшов, завжди підгамільтонів[2].

Примітки

  1. ↑ Heath, 1987, с. 198–218.
  2. ↑ а б в г Di Giacomo, Liotta, 2010, с. 35–46.
  3. ↑ Наприклад, у технічному звіті 2003 року «Book embeddings of graphs and a theorem of Whitney», Пол Кайнен визначає підгамільтонові графи як підграфи планарних гамільтонових графів без обмеження множини вершин у розширеному графі, але пише, що «у визначенні підгамільтонового графа можна вимагати, що розширення здійснюється лише додаванням ребер»
  4. ↑ а б Bekos, Gronemann, Raftopoulou, 2014.
  5. ↑ Bernhart, Kainen, 1979.
  6. ↑ Bernhart, Kainen, 1979, с. 320–331.
  7. ↑ Nishizeki, Chiba, 2008, с. 171–184.
  8. ↑ Cornuéjols, Naddef, Pulleyblank, 1983, с. 287–294.
  9. ↑ Kainen, Overbay, 2007, с. 835–837.
  10. ↑ Розділювальний трикутник — це подграф, що містить три вершини і три ребра, видалення якого (разом із суміжними ребрами) призводить до розбиття графа на незв'язані частини (Duncan, Goodrich, Kobourov, 2003).
  11. ↑ Тобто кожне ребро перетворено на два ребра шляхом поміщення на ребро вершини.

Література

  • Lenwood S. Heath. Embedding outerplanar graphs in small books // SIAM Journal on Algebraic and Discrete Methods. — 1987. — Т. 8, вип. 2. — С. 198–218. — DOI:10.1137/0608018.
  • Emilio Di Giacomo, Giuseppe Liotta. WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010, Proceedings. — Berlin : Springer, 2010. — Т. 5942. — С. 35–46. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-11440-3_4.
  • Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph // Journal of Combinatorial Theory. — 1979. — Т. 27, вип. 3. — С. 320–331. — (Series B). — DOI:10.1016/0095-8956(79)90021-2.
  • Takao Nishizeki, Norishige Chiba,. Planar Graphs: Theory and Algorithms. — Courier Dover Publications, 2008. — С. 171–184. — (Dover Books on Mathematics) — ISBN 9780486466712.
  • G. Cornuéjols, D. Naddef, W. R. Pulleyblank. Halin graphs and the travelling salesman problem // Mathematical Programming. — 1983. — Т. 26, вип. 3. — С. 287–294. — DOI:10.1007/BF02591867.
  • Michael A. Bekos, Martin Gronemann, Chrysanthi N. Raftopoulou. STACS. — 2014.
  • Paul C. Kainen, Shannon Overbay. Extension of a theorem of Whitney // Applied Mathematics Letters. — 2007. — Т. 20, вип. 7. — С. 835–837. — DOI:10.1016/j.aml.2006.08.019.
  • Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov. Planarity-Preserving Clustering and Embedding for Large Planar Graphs // Computational Geomenty. — Elsevier, 2003. — Вип. 24.