Tiltott gráfok szerinti osztályozás
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
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
Fordítá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
- ↑ a b c Diestel, Reinhard (2000), Graph Theory, vol. 173, Graduate Texts in Mathematics, Springer-Verlag, ISBN 0-387-98976-5.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Bollobás Béla (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 p. 9
- ↑ 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.
- ↑ 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>.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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
- ↑ 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
- ↑ 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.
- ↑ 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.
- ↑ 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
- ↑ a b Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics 24 (1): 105–107, DOI 10.1016/0012-365X(78)90178-4..
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ Yu, Yanming (2006), "More Forbidden Minors for Wye-Delta-Wye Reducibility", The Electronic Journal of Combinatorics 13 Website
|
|