Tiltott gráfok szerinti osztályozás
matematikai fogalom a gráfelméletben / From Wikipedia, the free encyclopedia
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.