Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Підгамільтонів граф це підграф планарного гамільтонового графа ВизначенняГраф G displaystyle G підгамільтонів якщо G dis

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

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

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

Визначення

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

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

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

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

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

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

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

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

Примітки

  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 // . — 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) — .
  • 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.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Pidgamiltoniv graf ce pidgraf planarnogo gamiltonovogo grafa ViznachennyaGraf G displaystyle G pidgamiltoniv yaksho G displaystyle G ye pidgrafom deyakogo inshogo grafa aug G displaystyle aug G z tiyeyu zh mnozhinoyu vershin pri comu graf aug G displaystyle aug G planarnij i mistit gamiltoniv cikl Shob ci umovi vikonuvalisya sam graf G displaystyle G maye buti planarnim i krim togo maye buti mozhlivist dodati rebra zi zberezhennyam planarnosti shob stvoriti u rozshirenomu grafi cikl yakij prohodit usi vershini rivno po odnomu razu Graf aug G displaystyle aug G nazivayut gamiltonovim rozshirennyam grafa G displaystyle G Mozhna bulo b dati viznachennya pidgamiltonovogo grafa yak pidgrafa gamiltonovogo grafa bez vimogi sho cej bilshij graf maye tu zh mnozhinu vershin Tobto v comu alternativnomu viznachenni mozhna bulo b dodavati vershini ta rebra Odnak yaksho graf mozhna zrobiti gamiltonovim za dopomogoyu dodavannya vershin i reber jogo mozhna zrobiti takim i bez dodavannya vershin tomu cya dodatkova svoboda ne zminyuye viznachennya U pidgamiltonovomu grafi cikl ce ciklichna poslidovnist vershin taka sho dodavannya rebra v bud yaku paru vershin u poslidovnosti ne porushuye planarnosti grafa Graf ye pidgamiltonovim todi j lishe todi koli vin maye pidgamiltoniv cikl Istoriya ta zastosuvannyaKlas pidgamiltonovih grafiv ale ne nazvu klasu zaproponuvali Berngart ta Kajnen Voni doveli sho ce tochno ti grafi yaki mayut dvi storinki v knizhkovih vkladennyah Pidgamiltonovi grafi ta gamiltonovi rozshirennya vikoristovuyut takozh u galuzi vizualizaciyi grafiv dlya zadach vkladennya grafiv u universalnu mnozhinu tochok odnochasnogo vkladennya kilkoh grafiv ta Pov yazani simejstva grafivDeyaki klasi planarnih grafiv obov yazkovo gamiltonovi tomu j pidgamiltonovi Syudi vhodyat 4 vershinno zv yazni grafi ta grafi Halina Bud yakij planarnij graf iz najbilshim stepenem sho ne perevishuye chotiroh ye pidgamiltonovim yak i bud yakij planarnij graf bez rozdilyuvalnih trikutnikiv Yaksho rebra dovilnogo planarnogo grafa rozbito na shlyahi dovzhini dva graf sho vijshov zavzhdi pidgamiltoniv PrimitkiHeath 1987 s 198 218 Di Giacomo Liotta 2010 s 35 46 Napriklad u tehnichnomu zviti 2003 roku Book embeddings of graphs and a theorem of Whitney Pol Kajnen viznachaye pidgamiltonovi grafi yak pidgrafi planarnih gamiltonovih grafiv bez obmezhennya mnozhini vershin u rozshirenomu grafi ale pishe sho u viznachenni pidgamiltonovogo grafa mozhna vimagati sho rozshirennya zdijsnyuyetsya lishe dodavannyam reber Bekos Gronemann Raftopoulou 2014 Bernhart Kainen 1979 Bernhart Kainen 1979 s 320 331 Nishizeki Chiba 2008 s 171 184 Cornuejols Naddef Pulleyblank 1983 s 287 294 Kainen Overbay 2007 s 835 837 Rozdilyuvalnij trikutnik ce podgraf sho mistit tri vershini i tri rebra vidalennya yakogo razom iz sumizhnimi rebrami prizvodit do rozbittya grafa na nezv yazani chastini Duncan Goodrich Kobourov 2003 Tobto kozhne rebro peretvoreno na dva rebra shlyahom pomishennya na rebro vershini LiteraturaLenwood S Heath Embedding outerplanar graphs in small books SIAM Journal on Algebraic and Discrete Methods 1987 T 8 vip 2 S 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 T 5942 S 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 1979 T 27 vip 3 S 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 S 171 184 Dover Books on Mathematics ISBN 9780486466712 G Cornuejols D Naddef W R Pulleyblank Halin graphs and the travelling salesman problem Mathematical Programming 1983 T 26 vip 3 S 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 T 20 vip 7 S 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 Vip 24

Дата публікації:
Топ