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

Характериза ція заборо неними гра фами це метод опису сімейства графів або гіперграфів вказанням підструктур яким заборо

Характеризація забороненими графами

Характеризація забороненими графами

Характериза́ція заборо́неними гра́фами — це метод опису сімейства графів або гіперграфів вказанням підструктур, яким заборонено з'являтися всередині будь-якого графа сімейства.

Заборонені графи

У теорії графів багато важливих сімейств графів можна описати скінченним числом графів, які не належать сімейству, виключивши із сімейства всі графи, які містять будь-який з цих заборонених графів як (породжений) підграф або мінор. Прототипом явища є теорема Понтрягіна — Куратовського, яка стверджує, що граф планарний (граф, який можна намалювати на площині без перетинів) тоді й лише тоді, коли він не містить будь-якого з двох заборонених підграфів: повного графа K5 і повного двочасткового графа K3,3.

У різних сімействах природа забороненого змінюється. В загальному випадку структура G є членом сімейства image тоді й лише тоді, коли заборонена структура не міститься в G. Заборонена підструктура може бути однією з:

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

Характеризація забороненими графами можна використати в алгоритмах для перевірки, чи належить граф до даного сімейства. У багатьох випадках можна перевірити за поліноміальний час, чи містить даний граф який-небудь член перешкоджальної множини, а тому, чи належить граф до сімейства, визначеного перешкоджальною множиною.

Щоб сімейство мало характеризацію забороненими графами з певним типом підструктур, воно має бути замкнутим за підструктурами. Тобто будь-яка підструктура (даного типу) графа в сімействі повинна бути іншим графом у сімействі. Еквівалентно, якщо граф не входить у сімейство, всі більші графи, які містять його як підструктуру, мають бути виключені із сімейства. Якщо це так, завжди існує перешкоджальна множина (множина графів, які не належать сімейству, але всі менші їх підструктури належать сімейству). Проте, при деяких поданнях, що розуміти під підструктурою, ця перешкоджальна множина може виявитися нескінченною. Теорема Робертсона — Сеймура доводить, що в певних випадках мінорів графа, сімейство, замкнуте за мінорами, завжди має скінченну перешкоджальну множину.

Список характеризацій забороненими графами (для графів і гіперграфів)

Сімейство Заборонені графи Залежність Зв'язок
Ліси петлі, пари паралельних ребер і цикли будь-якої довжини підграф визначення
петля (для мультиграфів) або трикутник K3 (для простих графів) мінор графа визначення
Графи без клешень зірка K1,3 породжений підграф визначення
Графи порівнянності породжений підграф
Графи без трикутників трикутник K3 породжений підграф визначення
Планарні графи K5 і K3,3 гомеоморфний підграф теорема Понтрягіна — Куратовського
K5 і K3,3 мінор графа теорема Вагнера
Зовніпланарні графи K4 і K2,3 мінор графа Дістель стор. 107
Зовнішні 1-планарні графи п'ять заборонених мінорів мінор графа Авер, Бахмаєр та ін.
Графи з фіксованим родом скінченна перешкоджальна множина мінор графа Дістель стор. 275
Верхівковий граф скінченна перешкоджальна множина мінор графа

Графи, що допускають вкладення без зачеплень

петерсенове сімейство графів мінор графа
Двочасткові графи непарні цикли підграф
Хордальні графи цикли довжини 4 або більше породжений підграф
Досконалі графи непарні цикли довжини 5 і більше та їх доповнення породжений підграф
Реберні графи для графів дев'ять заборонених підграфів (перелічені тут) породжений підграф
Об'єднання графів-кактусів алмаз, утворений видаленням ребра з повного графа K4 мінор графа
Драбини K2,3 і його двоїстий граф гомеоморфний підграф
(Циркулярні графи дуг Геллі) породжений підграф
image породжений підграф
Паралельно-послідовні графи (деревна ширина ≤ 2, ширина галуження ≤ 2) K4 мінор графа Дістель стор. 327
Деревна ширина ≤ 3 K5, октаедр, п'ятикутна призма, граф Вагнера мінор графа
Ширина галуження ≤ 3 K5, октаедр, куб, граф Вагнера мінор графа
Додатково звідні графи (кографи) Граф P4 породжений підграф
Тривіально досконалі графи Граф P4 і цикл C4 породжений підграф
Порогові графи Граф P4, цикл C4 і доповнення C4 породжений підграф
скінченний список заборонених породжених підграфів з мінімальним степенем, не меншим від 19 породжений підграф
скінченний список заборонених породжених підграфів з мінімальним степенем ребер принаймні 2k2 − 3k + 1 породжений підграф
Основні теореми
Сімейство, визначене породженою успадкованою властивістю (не обов'язково скінченна) перешкоджальна множина породжений підграф
Сімейство, визначене мінорною успадкованою властивістю скінченна перешкоджальна множина мінор графа теорема Робертсона — Сеймура

Див. також

Примітки

  1. Diestel Reinhard. Graph Theory. — Springer-Verlag, 2000. — Т. 173. — (Graduate Texts in Mathematics) — ..
  2. Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff,. — 2013. — Т. 8242. — С. 107–118. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-03841-4_10..
  3. A. Gupta, R. Impagliazzo. . — IEEE Computer Society, 1991. — С. 802–811. — DOI:10.1109/SFCS.1991.185452..
  4. Neil Robertson, P. D. Seymour, Robin Thomas. Linkless embeddings of graphs in 3-space // Bulletin of the American Mathematical Society. — 1993. — Т. 28, вип. 1 (16 червня). — С. 84–89. — arXiv:math/9301216. — DOI:10.1090/S0273-0979-1993-00335-5..
  5. [en]. p. 9 Modern Graph Theory. — Springer, 1998. — .
  6. Toshinobu Kashiwabara. Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings / Nobuji Saito, Takao Nishizeki. — Springer-Verlag, 1981. — Т. 108. — С. 171–181. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-10704-5\_15..
  7. Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вип. 1 (16 червня). — С. 51–229. — arXiv:math/0212070v1. — DOI:10.4007/annals.2006.164.51..
  8. L. W. Beineke. Beiträge zur Graphentheorie / H. Sachs, H.-J. Voss, H.-J. Walter. — Leipzig : Teubner, 1968. — С. 17–33..
  9. Ehab El-Mallah, Charles Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вип. 3 (16 червня). — С. 354–362. — DOI:10.1109/31.1748..
  10. K. Takamizawa, Takao Nishizeki, Nobuji Saito. Combinatorial problems on series-parallel graphs // Discrete Applied Mathematics. — 1981. — Т. 3, вип. 1 (16 червня). — С. 75–76. — DOI:10.1016/0166-218X(81)90031-7..
  11. Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Linear-Time Recognition of Helly Circular-Arc Models and Graphs // Algorithmica. — 2009. — Т. 59, вип. 2 (16 червня). — С. 215–239. — DOI:10.1007/s00453-009-9304-5.
  12. Stéphane Földes, Peter L. Peter Hammer. Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977). — Winnipeg : Utilitas Math, 1977a. — Т. XIX. — С. 311–315. — (Congressus Numerantium)
  13. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2 (16 червня). — С. 1–45. — DOI:10.1016/S0304-3975(97)00228-4..
  14. Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вип. 2 (16 червня). — С. 167–194. — DOI:10.1006/jagm.1999.1011..
  15. D. Seinsche. On a property of the class of n-colorable graphs // Journal of Combinatorial Theory, Series B. — 1974. — Т. 16, вип. 2 (16 червня). — С. 191–193. — DOI:10.1016/0095-8956(74)90063-X.
  16. Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вип. 1 (16 червня). — С. 105–107. — DOI:10.1016/0012-365X(78)90178-4.
  17. Yury Metelsky, Regina Tyshkevich. On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. — 1997. — Т. 25, вип. 4 (16 червня). — С. 243–251. — DOI:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K.
  18. M. S. Jacobson, Andre E. Kézdy, Jeno Lehel. Recognizing intersection graphs of linear uniform hypergraphs // . — 1997. — Т. 13 (16 червня). — С. 359–367. — DOI:10.1007/BF03353014.
  19. Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi. Intersection graphs of k-uniform hypergraphs // European J. Combinatorics. — 1982. — Т. 3 (16 червня). — С. 159–172. — DOI:10.1016/s0195-6698(82)80029-2.

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

Harakteriza ciya zaboro nenimi gra fami ce metod opisu simejstva grafiv abo gipergrafiv vkazannyam pidstruktur yakim zaboroneno z yavlyatisya vseredini bud yakogo grafa simejstva Zaboroneni grafiU teoriyi grafiv bagato vazhlivih simejstv grafiv mozhna opisati skinchennim chislom grafiv yaki ne nalezhat simejstvu viklyuchivshi iz simejstva vsi grafi yaki mistyat bud yakij z cih zaboronenih grafiv yak porodzhenij pidgraf abo minor Prototipom yavisha ye teorema Pontryagina Kuratovskogo yaka stverdzhuye sho graf planarnij graf yakij mozhna namalyuvati na ploshini bez peretiniv todi j lishe todi koli vin ne mistit bud yakogo z dvoh zaboronenih pidgrafiv povnogo grafa K5 i povnogo dvochastkovogo grafa K3 3 U riznih simejstvah priroda zaboronenogo zminyuyetsya V zagalnomu vipadku struktura G ye chlenom simejstva F displaystyle mathcal F todi j lishe todi koli zaboronena struktura ne mistitsya v G Zaboronena pidstruktura mozhe buti odniyeyu z pidgrafi menshi grafi oderzhuvani z pidmnozhini vershin i reber bilshogo grafa porodzheni pidgrafi menshi grafi oderzhuvani viborom pidmnozhini vershin i vklyuchennyam vsih reber u yakih obidvi vershini nalezhat cij pidmnozhini gomeomorfni pidgrafi zvani takozh topologichnimi minorami menshi grafi oderzhuvani z pidgrafiv zaminoyu shlyahiv z vershinami stepenya dva rebrami minoriv grafa menshih grafiv otrimuvanih z pidgrafiv dovilnim styaguvannyam reber Mnozhinu struktur yakim zaboroneno nalezhati danomu simejstvu grafiv mozhna takozh nazvati pereshkodzhalnoyu mnozhinoyu simejstva Harakterizaciya zaboronenimi grafami mozhna vikoristati v algoritmah dlya perevirki chi nalezhit graf do danogo simejstva U bagatoh vipadkah mozhna pereviriti za polinomialnij chas chi mistit danij graf yakij nebud chlen pereshkodzhalnoyi mnozhini a tomu chi nalezhit graf do simejstva viznachenogo pereshkodzhalnoyu mnozhinoyu Shob simejstvo malo harakterizaciyu zaboronenimi grafami z pevnim tipom pidstruktur vono maye buti zamknutim za pidstrukturami Tobto bud yaka pidstruktura danogo tipu grafa v simejstvi povinna buti inshim grafom u simejstvi Ekvivalentno yaksho graf ne vhodit u simejstvo vsi bilshi grafi yaki mistyat jogo yak pidstrukturu mayut buti viklyucheni iz simejstva Yaksho ce tak zavzhdi isnuye pereshkodzhalna mnozhina mnozhina grafiv yaki ne nalezhat simejstvu ale vsi menshi yih pidstrukturi nalezhat simejstvu Prote pri deyakih podannyah sho rozumiti pid pidstrukturoyu cya pereshkodzhalna mnozhina mozhe viyavitisya neskinchennoyu Teorema Robertsona Sejmura dovodit sho v pevnih vipadkah minoriv grafa simejstvo zamknute za minorami zavzhdi maye skinchennu pereshkodzhalnu mnozhinu Spisok harakterizacij zaboronenimi grafami dlya grafiv i gipergrafiv Simejstvo Zaboroneni grafi Zalezhnist Zv yazok Lisi petli pari paralelnih reber i cikli bud yakoyi dovzhini pidgraf viznachennya petlya dlya multigrafiv abo trikutnik K3 dlya prostih grafiv minor grafa viznachennya Grafi bez kleshen zirka K1 3 porodzhenij pidgraf viznachennya Grafi porivnyannosti porodzhenij pidgraf Grafi bez trikutnikiv trikutnik K3 porodzhenij pidgraf viznachennya Planarni grafi K5 i K3 3 gomeomorfnij pidgraf teorema Pontryagina Kuratovskogo K5 i K3 3 minor grafa teorema Vagnera Zovniplanarni grafi K4 i K2 3 minor grafa Distel stor 107 Zovnishni 1 planarni grafi p yat zaboronenih minoriv minor grafa Aver Bahmayer ta in Grafi z fiksovanim rodom skinchenna pereshkodzhalna mnozhina minor grafa Distel stor 275 Verhivkovij graf skinchenna pereshkodzhalna mnozhina minor grafa Grafi sho dopuskayut vkladennya bez zacheplen petersenove simejstvo grafiv minor grafa Dvochastkovi grafi neparni cikli pidgraf Hordalni grafi cikli dovzhini 4 abo bilshe porodzhenij pidgraf Doskonali grafi neparni cikli dovzhini 5 i bilshe ta yih dopovnennya porodzhenij pidgraf Reberni grafi dlya grafiv dev yat zaboronenih pidgrafiv perelicheni tut porodzhenij pidgraf Ob yednannya grafiv kaktusiv almaz utvorenij vidalennyam rebra z povnogo grafa K4 minor grafa Drabini K2 3 i jogo dvoyistij graf gomeomorfnij pidgraf Cirkulyarni grafi dug Gelli porodzhenij pidgraf C 4 C 5 C 4 K 2 K 2 displaystyle C 4 C 5 bar C 4 K 2 K 2 porodzhenij pidgraf Paralelno poslidovni grafi derevna shirina 2 shirina galuzhennya 2 K4 minor grafa Distel stor 327 Derevna shirina 3 K5 oktaedr p yatikutna prizma graf Vagnera minor grafa Shirina galuzhennya 3 K5 oktaedr kub graf Vagnera minor grafa Dodatkovo zvidni grafi kografi Graf P4 porodzhenij pidgraf Trivialno doskonali grafi Graf P4 i cikl C4 porodzhenij pidgraf Porogovi grafi Graf P4 cikl C4 i dopovnennya C4 porodzhenij pidgraf skinchennij spisok zaboronenih porodzhenih pidgrafiv z minimalnim stepenem ne menshim vid 19 porodzhenij pidgraf skinchennij spisok zaboronenih porodzhenih pidgrafiv z minimalnim stepenem reber prinajmni 2k2 3k 1 porodzhenij pidgraf Osnovni teoremi Simejstvo viznachene porodzhenoyu uspadkovanoyu vlastivistyu ne obov yazkovo skinchenna pereshkodzhalna mnozhina porodzhenij pidgraf Simejstvo viznachene minornoyu uspadkovanoyu vlastivistyu skinchenna pereshkodzhalna mnozhina minor grafa teorema Robertsona SejmuraDiv takozh en en Zadacha ZarankevichaPrimitkiDiestel Reinhard Graph Theory Springer Verlag 2000 T 173 Graduate Texts in Mathematics ISBN 0 387 98976 5 Christopher Auer Christian Bachmaier Franz J Brandenburg Andreas Gleissner Kathrin Hanauer Daniel Neuwirth Josef Reislhuber 21st International Symposium GD 2013 Bordeaux France September 23 25 2013 Revised Selected Papers Stephen Wismath Alexander Wolff 2013 T 8242 S 107 118 Lecture Notes in Computer Science DOI 10 1007 978 3 319 03841 4 10 A Gupta R Impagliazzo IEEE Computer Society 1991 S 802 811 DOI 10 1109 SFCS 1991 185452 Neil Robertson P D Seymour Robin Thomas Linkless embeddings of graphs in 3 space Bulletin of the American Mathematical Society 1993 T 28 vip 1 16 chervnya S 84 89 arXiv math 9301216 DOI 10 1090 S0273 0979 1993 00335 5 en p 9 Modern Graph Theory Springer 1998 ISBN 0 387 98488 7 Toshinobu Kashiwabara Graph Theory and Algorithms 17th Symposium of Research Institute of Electric Communication Tohoku University Sendai Japan October 24 25 1980 Proceedings Nobuji Saito Takao Nishizeki Springer Verlag 1981 T 108 S 171 181 Lecture Notes in Computer Science DOI 10 1007 3 540 10704 5 15 Maria Chudnovsky Neil Robertson Paul Seymour Robin Thomas The strong perfect graph theorem Annals of Mathematics 2006 T 164 vip 1 16 chervnya S 51 229 arXiv math 0212070v1 DOI 10 4007 annals 2006 164 51 L W Beineke Beitrage zur Graphentheorie H Sachs H J Voss H J Walter Leipzig Teubner 1968 S 17 33 Ehab El Mallah Charles Colbourn The complexity of some edge deletion problems IEEE Transactions on Circuits and Systems 1988 T 35 vip 3 16 chervnya S 354 362 DOI 10 1109 31 1748 K Takamizawa Takao Nishizeki Nobuji Saito Combinatorial problems on series parallel graphs Discrete Applied Mathematics 1981 T 3 vip 1 16 chervnya S 75 76 DOI 10 1016 0166 218X 81 90031 7 Benson L Joeris Min Chih Lin Ross M McConnell Jeremy P Spinrad Jayme L Szwarcfiter Linear Time Recognition of Helly Circular Arc Models and Graphs Algorithmica 2009 T 59 vip 2 16 chervnya S 215 239 DOI 10 1007 s00453 009 9304 5 Stephane Foldes Peter L Peter Hammer Proceedings of the Eighth Southeastern Conference on Combinatorics Graph Theory and Computing Louisiana State Univ Baton Rouge La 1977 Winnipeg Utilitas Math 1977a T XIX S 311 315 Congressus Numerantium Hans L Bodlaender A partial k arboretum of graphs with bounded treewidth Theoretical Computer Science 1998 T 209 vip 1 2 16 chervnya S 1 45 DOI 10 1016 S0304 3975 97 00228 4 Hans L Bodlaender Dimitrios M Thilikos Graphs with branchwidth at most three Journal of Algorithms 1999 T 32 vip 2 16 chervnya S 167 194 DOI 10 1006 jagm 1999 1011 D Seinsche On a property of the class of n colorable graphs Journal of Combinatorial Theory Series B 1974 T 16 vip 2 16 chervnya S 191 193 DOI 10 1016 0095 8956 74 90063 X Martin Charles Golumbic Trivially perfect graphs Discrete Mathematics 1978 T 24 vip 1 16 chervnya S 105 107 DOI 10 1016 0012 365X 78 90178 4 Yury Metelsky Regina Tyshkevich On line graphs of linear 3 uniform hypergraphs Journal of Graph Theory 1997 T 25 vip 4 16 chervnya S 243 251 DOI 10 1002 SICI 1097 0118 199708 25 4 lt 243 AID JGT1 gt 3 0 CO 2 K M S Jacobson Andre E Kezdy Jeno Lehel Recognizing intersection graphs of linear uniform hypergraphs 1997 T 13 16 chervnya S 359 367 DOI 10 1007 BF03353014 Ranjan N Naik S B Rao S S Shrikhande N M Singhi Intersection graphs of k uniform hypergraphs European J Combinatorics 1982 T 3 16 chervnya S 159 172 DOI 10 1016 s0195 6698 82 80029 2

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