Wikipédia

Tiltott gráfok szerinti osztályozás

matematikai fogalom a gráfelméletben
(Tiltott részgráf szócikkből átirányítva)
Ez a közzétett változat, ellenőrizve: 2019. június 5.

A matematika, azon belül a gráfelmélet területén számos gráfcsalád jellemezhető annak kikötésével, hogy mely véges számú egyedi gráf nem tartozik bele a családba – azokat a gráfokat is kizárva a családból, melyek az említett tiltott gráfokat (feszített) részgráfként vagy minorként tartalmazzák. A jelenség leggyakrabban említett példája a Kuratowski-tétel, ami szerint egy gráf akkor és csak akkor síkba rajzolható, ha nem tartalmazza a K5 teljes gráf vagy a K3,3 teljes páros gráf egyikét sem. A Kuratowski-tétel esetében a tartalmazás típusa gráfhomeomorfizmus, melyben egy gráf felosztása egy másik gráf részgráfjaként jelenik meg. Tehát minden gráfra igaz, hogy vagy síkba rajzolható (ekkor a síkgráfok családjába tartozik) vagy van olyan felosztása, ami az említett két gráfot részgráfként tartalmazza (és ekkor nem tartozik a síkgráfok közé).

Általánosabban, egy tiltott gráfok szerinti osztályozás egy gráf vagy hipergráf családjának oly módon történő meghatározása, melynek során a családba sorolt gráfokban tiltott részstruktúrákat sorolunk fel. Az egyes családokban különbözhet a „tiltott” fogalmának pontos meghatározása. Általánosan egy G struktúra akkor és csak akkor az család tagja, ha egy tiltott részstruktúra nem része G-nek. A tiltott a következő opciók valamelyike lehet:

  • részgráfok, az eredeti gráf csúcsainak és éleinek részhalmazai által alkotott gráfok;
  • feszített részgráfok, az eredeti gráf csúcsainak részhalmazából, az eredetileg köztük lévő összes él meghagyásával (ahol az él mindkét végpontja a részhalmazon belül van) alkotott gráfok;
  • homeomorf részgráfok (topologikus minorok), az eredeti gráfból 2 fokú csúcsot tartalmazó utak éllé alakításával;
  • gráfminorok, az élek törlésével, összehúzásával, izolált csúcsok törlésével megkapható kisebb gráfok.

Az adott gráfcsaládban tiltott részstruktúrák halmazát az ahhoz a gráfcsaládhoz tartozó obstrukcióhalmaznak („akadályhalmaz”, obstruction set) nevezik.

Az obstrukcióhalmazok szerinti osztályozásokat felhasználják gráfok valamely gráfcsaládhoz való tartozásának eldöntésére szolgáló algoritmusokban. Sok esetben polinomiális idő alatt eldönthető, hogy egy gráf tartalmazza-e az obstrukcióhalmaz valamely elemét, és így beletartozik-e az obstrukcióhalmaz által meghatározott gráfcsaládba.

Ahhoz, hogy egy gráfcsaládnak létezhessen tiltott gráfok szerinti osztályozása, adott típusú részstruktúrával, a családnak zártnak kell lennie a részstruktúraképzés műveletére nézve. Más szavakkal, az adott típusú gráfcsalád tagjai minden részstruktúrájának is a családba tartozó gráfnak kell lennie. Ezzel ekvivalens módon, ha egy gráf nem tagja a családnak, akkor egyetlen, a gráfot részstruktúraként tartalmazó gráf sem lehet tagja a családnak. Ha ezek az állítások igazak, akkor minden esetben létezik akadályhalmaz (melynek viszont a részstruktúrái beletartoznak a családba). A részstruktúraképzés egyes megfogalmazásaiban az obstrukcióhalmaz végtelen is lehet. A Robertson–Seymour-tétel a gráfminorok esetére igazolja, hogy egy gráfminorképzésre nézve zárt gráfcsalád mindig véges obstrukciós halmazzal rendelkezik.

Gráfok és hipergráfok tiltás alapú osztályozásai

szerkesztés
  Ez a lista egyelőre nem teljes. Segíts te is bővíteni, hogy teljes lista lehessen belőle!
Család Tiltott gráfok Kapcsolat Referencia
Erdők hurokélek, párhuzamos élpárok és bármilyen hosszúságú körök részgráf Definíció
hurok (multigráfoknál) vagy K3 háromszög (egyszerű gráfoknál) gráfminor Definíció
Karommentes gráfok K1,3 csillag feszített részgráf Definíció
összehasonlíthatósági gráfok feszített részgráf
Háromszögmentes gráfok K3 háromszög feszített részgráf Definíció
Síkgráfok K5 és K3,3 topologikus minor Kuratowski-tétel
K5 és K3,3 gráfminor Wagner-tétel
Külsíkgráfok K4 és K2,3 gráfminor (Diestel 2000),[1] p. 107
1-külsíkgráfok öt tiltott minor gráfminor (Auer et al. 2013)[2]
Fix génuszú gráfok véges obstrukciós halmaz gráfminor (Diestel 2000),[1] p. 275
Csúcsgráfok véges obstrukciós halmaz gráfminor [3]
Láncmentesen beágyazható gráfok a Petersen-gráfcsalád gráfminor [4]
Páros gráfok páratlan körök részgráf [5]
Húrgráfok ≥4 hosszúságú körök feszített részgráf [6]
Perfekt gráfok ≥5 hosszúságú páratlan körök vagy komplementerük feszített részgráf [7]
Gráfok élgráfjai kilenc tiltott részgráf (lásd a szócikkben) feszített részgráf [8]
Kaktuszgráfok uniója a K4 teljes gráfból egy él eltávolításával kapott gyémántgráf gráfminor [9]
Létragráfok K2,3 és duálisa topologikus minor [10]
Helly-féle ívgráfok feszített részgráf [11]
split gráfok   feszített részgráf [12]
Soros-párhuzamos gráf (favastagság ≤ 2 fafelbontás szélessége ≤ 2) K4 gráfminor (Diestel 2000),[1] p. 327
favastagság ≤ 3 K5, oktaéder, ötszögalapú hasáb, Wagner-gráf gráfminor [13]
fafelbontás szélessége ≤ 3 K5, oktaéder, kocka, Wagner-gráf gráfminor [14]
Kográfok 4-csúcsú P4 útgráf feszített részgráf [15]
Triviálisan perfekt gráfok 4-csúcsú P4 útgráf és 4-csúcsú C4 körgráf feszített részgráf [16]
Küszöbgráfok 4-csúcsú P4 útgráf és 4-csúcsú C4 körgráf és utóbbi komplementer gráfja feszített részgráf [16]
3-uniform lineáris hipergráfok élgráfjai legalább 19 fokú tilos feszített részgráfok véges listája feszített részgráf [17]
k-uniform lineáris hipergráfok, k > 3 tiltott feszített részgráfok véges listája; ezek élszáma legalább 2k2 − 3k + 1 feszített részgráf [18][19]
Egyetlen csúccsá ΔY-redukálható gráfok (1,2,3)-klikkösszegek véges, legalább 68 milliárd tagú listája gráfminor [20]
Általános tételek
a feszített részgráfokra öröklődő tulajdonság által meghatározott gráfcsalád egy (nem feltétlenül véges) obstrukciós halmaz feszített részgráf
a minorokra öröklődő tulajdonság által meghatározott gráfcsalád véges obstrukciós halmaz gráfminor Robertson–Seymour-tétel

Kapcsolódó szócikkek

szerkesztés

Fordítás

szerkesztés
  • Ez a szócikk részben vagy egészben a Forbidden graph characterization című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

szerkesztés
  1. ↑ a b c Diestel, Reinhard (2000), Graph Theory, vol. 173, Graduate Texts in Mathematics, Springer-Verlag, ISBN 0-387-98976-5.
  2. ↑ Auer, Christopher; Bachmaier, Christian & Brandenburg, Franz J. et al. (2013), "Recognizing outer 1-planar graphs in linear time", in Wismath, Stephen & Wolff, Alexander, 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers, vol. 8242, Lecture Notes in Computer Science, pp. 107–118, DOI 10.1007/978-3-319-03841-4_10.
  3. ↑ Gupta, A. & Impagliazzo, R. (1991), "Computing planar intertwines", Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91), IEEE Computer Society, pp. 802–811, doi:10.1109/SFCS.1991.185452.
  4. ↑ Robertson, Neil; Seymour, P. D. & Thomas, Robin (1993), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society 28 (1): 84–89, DOI 10.1090/S0273-0979-1993-00335-5.
  5. ↑ Bollobás Béla (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 p. 9
  6. ↑ Kashiwabara, Toshinobu (1981), "Algorithms for some intersection graphs", in Saito, Nobuji & Nishizeki, Takao, Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings, vol. 108, Lecture Notes in Computer Science, Springer-Verlag, pp. 171–181, DOI 10.1007/3-540-10704-5\_15.
  7. ↑ Chudnovsky, Maria; Robertson, Neil & Seymour, Paul et al. (2006), "The strong perfect graph theorem", Annals of Mathematics 164 (1): 51–229, doi:10.4007/annals.2006.164.51, <http://people.math.gatech.edu/~thomas/PAP/spgc.pdf>.
  8. ↑ Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J. & Walter, H.-J., Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.
  9. ↑ El-Mallah, Ehab & Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems 35 (3): 354–362, DOI 10.1109/31.1748.
  10. ↑ Takamizawa, K.; Nishizeki, Takao & Saito, Nobuji (1981), "Combinatorial problems on series-parallel graphs", Discrete Applied Mathematics 3 (1): 75–76, DOI 10.1016/0166-218X(81)90031-7.
  11. ↑ Joeris, Benson L.; Lin, Min Chih & McConnell, Ross M. et al. (2009), "Linear-Time Recognition of Helly Circular-Arc Models and Graphs", Algorithmica 59 (2): 215–239, DOI 10.1007/s00453-009-9304-5
  12. ↑ Földes, Stéphane & Hammer, Peter Ladislaw (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), vol. XIX, Congressus Numerantium, Winnipeg: Utilitas Math., pp. 311–315
  13. ↑ Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science 209 (1–2): 1–45, DOI 10.1016/S0304-3975(97)00228-4.
  14. ↑ Bodlaender, Hans L. & Thilikos, Dimitrios M. (1999), "Graphs with branchwidth at most three", Journal of Algorithms 32 (2): 167–194, DOI 10.1006/jagm.1999.1011.
  15. ↑ Seinsche, D. (1974), "On a property of the class of n-colorable graphs", Journal of Combinatorial Theory, Series B 16 (2): 191–193, DOI 10.1016/0095-8956(74)90063-X
  16. ↑ a b Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics 24 (1): 105–107, DOI 10.1016/0012-365X(78)90178-4..
  17. ↑ Metelsky, Yury & Tyshkevich, Regina (1997), "On line graphs of linear 3-uniform hypergraphs", Journal of Graph Theory 25 (4): 243–251, DOI 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K
  18. ↑ Jacobson, M. S.; Kézdy, Andre E. & Lehel, Jeno (1997), "Recognizing intersection graphs of linear uniform hypergraphs", Graphs and Combinatorics 13: 359–367, DOI 10.1007/BF03353014
  19. ↑ Naik, Ranjan N.; Rao, S. B. & Shrikhande, S. S. et al. (1982), "Intersection graphs of k-uniform hypergraphs", European J. Combinatorics 3: 159–172, DOI 10.1016/s0195-6698(82)80029-2
  20. ↑ Yu, Yanming (2006), "More Forbidden Minors for Wye-Delta-Wye Reducibility", The Electronic Journal of Combinatorics 13 Website
A lap eredeti címe: „https://hu.wiki.x.io/w/index.php?title=Tiltott_gráfok_szerinti_osztályozás&oldid=21401936”