Вікіпедія

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

метод опису сімейства графів або гіперграфів

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

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

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

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

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

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

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

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

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

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

петерсенове сімейство графів мінор графа [4]
Двочасткові графи непарні цикли підграф [5]
Хордальні графи цикли довжини 4 або більше породжений підграф [6]
Досконалі графи непарні цикли довжини 5 і більше та їх доповнення породжений підграф [7]
Реберні графи для графів дев'ять заборонених підграфів (перелічені тут) породжений підграф [8]
Об'єднання графів-кактусів алмаз, утворений видаленням ребра з повного графа K4 мінор графа [9]
Драбини K2,3 і його двоїстий граф гомеоморфний підграф [10]
Циркулярні графи дуг Геллі породжений підграф [11]
Розщепні графи   породжений підграф [12]
Паралельно-послідовні графи (деревна ширина ≤ 2, ширина галуження ≤ 2) K4 мінор графа Дістель стор. 327
Деревна ширина ≤ 3 K5, октаедр, п'ятикутна призма, граф Вагнера мінор графа [13]
Ширина галуження ≤ 3 K5, октаедр, куб, граф Вагнера мінор графа [14]
Додатково звідні графи (кографи) Граф P4 породжений підграф [15]
Тривіально досконалі графи Граф P4 і цикл C4 породжений підграф [16]
Порогові графи Граф P4, цикл C4 і доповнення C4 породжений підграф
Реберні графи 3-однорідних лінійних гіперграфів скінченний список заборонених породжених підграфів з мінімальним степенем, не меншим від 19 породжений підграф [17]
Реберні графи k-однорідні лінійні гіперграфи, k > 3 скінченний список заборонених породжених підграфів з мінімальним степенем ребер принаймні 2k2 − 3k + 1 породжений підграф [18][19]
Основні теореми
Сімейство, визначене породженою успадкованою властивістю (не обов'язково скінченна) перешкоджальна множина породжений підграф
Сімейство, визначене мінорною успадкованою властивістю скінченна перешкоджальна множина мінор графа теорема Робертсона — Сеймура

Див. також ред.

Примітки ред.

  1. ↑ Diestel Reinhard. Graph Theory. — Springer-Verlag, 2000. — Т. 173. — (Graduate Texts in Mathematics) — ISBN 0-387-98976-5..
  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. Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91). — 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 (21 квітня). — С. 84–89. — arXiv:math/9301216. — DOI:10.1090/S0273-0979-1993-00335-5..
  5. ↑ Béla Bollobás[en]. p. 9 Modern Graph Theory. — Springer, 1998. — ISBN 0-387-98488-7.
  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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 191–193. — DOI:10.1016/0095-8956(74)90063-X.
  16. ↑ Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вип. 1 (21 квітня). — С. 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 (21 квітня). — С. 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 // Graphs and Combinatorics. — 1997. — Т. 13 (21 квітня). — С. 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 (21 квітня). — С. 159–172. — DOI:10.1016/s0195-6698(82)80029-2.
Отримано з https://uk.wikipedia.org/w/index.php?title=Характеризація_забороненими_графами&oldid=36499768