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 K₅ teljes gráf vagy a K_3,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	Sablon:Harvtxt, p. 107
1-külsíkgráfok	öt tiltott minor	gráfminor	Sablon:Harvtxt
Fix génuszú gráfok	véges obstrukciós halmaz	gráfminor	Sablon:Harvtxt, p. 275
Csúcsgráfok	véges obstrukciós halmaz	gráfminor
Láncmentesen beágyazható gráfok	a Petersen-gráfcsalád	gráfminor
Páros gráfok	páratlan körök	részgráf
Húrgráfok	≥4 hosszúságú körök	feszített részgráf
Perfekt gráfok	≥5 hosszúságú páratlan körök vagy komplementerük	feszített részgráf
Gráfok élgráfjai	kilenc tiltott részgráf (lásd a szócikkben)	feszített részgráf
Kaktuszgráfok uniója	a K4 teljes gráfból egy él eltávolításával kapott gyémántgráf	gráfminor
Létragráfok	K2,3 és duálisa	topologikus minor
Helly-féle ívgráfok		feszített részgráf
split gráfok	$C_4,C_5,\overline{C_4}(=K_2+K_2)$	feszített részgráf
Soros-párhuzamos gráf (favastagság ≤ 2 fafelbontás szélessége ≤ 2)	K4	gráfminor	Sablon:Harvtxt, p. 327
favastagság ≤ 3	K5, oktaéder, ötszögalapú hasáb, Wagner-gráf	gráfminor
fafelbontás szélessége ≤ 3	K5, oktaéder, kocka, Wagner-gráf	gráfminor
Kográfok	4-csúcsú P4 útgráf	feszített részgráf
Triviálisan perfekt gráfok	4-csúcsú P4 útgráf és 4-csúcsú C4 körgráf	feszített részgráf
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
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
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
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
Á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

• Erdős–Hajnal-sejtés
• Tiltott részgráf probléma
• Matroid minor
• Zarankiewicz-probléma

Fordítás

• Sablon:Fordítás