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

Kapcsolódó szócikkek
Erdős–Hajnal-sejtés
Tiltott részgráf probléma
Matroid minor
Zarankiewicz-probléma

Fordítás

Jegyzetek

Gráfelmélet
Gráfminorok
Gráfcsaládok
Hipergráfok
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ólfokú 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 Kapcsolódó szócikkek Erdős–Hajnal-sejtés Tiltott részgráf probléma Matroid minor Zarankiewicz-probléma Fordítás Jegyzetek Gráfelmélet Gráfminorok Gráfcsaládok Hipergráfok