Minor (gráfelmélet)

A matematika, azon belül a gráfelmélet területén a H irányítatlan gráf a G gráf minora, ha H előállítható G-ből élek és csúcsok törlésével, valamint élösszehúzás segítségével.

A gráfminorok elmélete a Wagner-tétellel kezdődött, miszerint egy gráf pontosan akkor síkbarajzolható, ha minorai között nem található meg sem a K₅ teljes gráf, sem a K_3,3 teljes páros gráf.^[1] A Robertson–Seymour-tétel szerint ezzel analóg módon, a törlések és élösszehúzások által nem befolyásolt minden gráftulajdonsághoz tartozik tiltott minorok szerinti karakterizáció.^[2] Adott H gráfra polinom idő alatt tesztelhető, hogy az a bemeneti G gráf minora-e;^[3] ebből a tiltott minorok szerinti osztályozást is tekintve az következik, hogy minden, törlések és élösszehúzások mellett is megmaradó gráftulajdonság polinom időben felismerhető.^[4]

További, a gráfminorokat érintő eredmények és sejtések közé tartozik a gráfminor-tétel, ami szerint a H-t minorként nem tartalmazó gráfok előállíthatók egyszerűbb darabok összeragasztásával, továbbá a mély Hadwiger-sejtés, ami a gráfok színezésének problémáját összeköti a nagyméretű teljes gráfminorok létezésével. A gráfminorok fajtái közül megemlítendők a topologikus minorok és az immerziós minorok.

Definíciók

Az élösszehúzás művelete során a gráfból eltávolítunk egy élt, miközben összevonjuk a két csúcsot, melyet az él kötött össze. Egy H irányítatlan gráfot akkor nevezünk a G irányítatlan gráf minorának, ha a H-val izomorf gráf előállítható G-ből élek összehúzásával, törlésével, illetve izolált csúcsok törlésével. Ezen műveletek G-n való elvégzésének sorrendje nem befolyásolja az eredményül kapott H gráfot.

A gráfminorok vizsgálata gyakran általánosabban, a matroid minorok kontextusában történik. Itt általában feltételezik, hogy a gráfok összefüggőek, megengedjük a többszörös és hurokéleket (tehát multigráfokról van szó); a hurokél összehúzása és az elválasztó élek törlése tiltott műveletnek számít. Ennek a nézőpontnak az előnye, hogy az éltörlések a gráf rangját változatlanul hagyják, az élösszehúzások pedig pontosan eggyel csökkentik.

Más kontextusokban (például a pszeudoerdők vizsgálatakor) hasznosabb lehet megengedni a nem összefüggő gráfokat és az élválasztó élek törlését, tiltani viszont a multigráfokat. Ebben a változatban az élösszehúzások után a gráfot egyszerűsíteni kell, kiküszöbölendő a hurokéleket és többszörös éleket.^[5]

Az f függvény akkor minor-monoton, ha fennáll, hogy ha H a G minora, akkor f(H) ≤ f(G).

Példa

A következő példában H a G gráf minora:

H.

G.

Ez a következő ábrán látható. Először állítsuk elő a G egy részgráfját a szaggatott élek kitörlésével, távolítsuk el a megmaradó izolált csúcsot, majd húzzuk össze a szürke élt (összevonva az általa összekötött két csúcsot):

Jelentős eredmények és sejtések

Egyszerűen ellenőrizhető, hogy a minorképzés, mint bináris reláció részbenrendezést alkot az irányítatlan gráfok izomorfizmus-osztályain: tranzitív (G minorának minora magának G-nek is minora), G és H pedig akkor és csak akkor lehetnek kölcsönösen egymás minorai, ha izomorfak egymással, mivel bármely nemtriviális minorképzési művelet éleket vagy csúcsokat szüntet meg. Neil Robertson és Paul Seymour mély eredménye szerint ez a részbenrendezés valójában egy jó előrendezés: ha tekintjük a véges gráfok G₁, G₂... végtelen listáját, mindig létezik két olyan i < j index, melyre G_i a G_j minora. Ezzel ekvivalens kijelentés, hogy gráfok tetszőleges halmazának a minorrendezést tekintve csak véges számú minimális eleme lehet.^[6] Ez az eredmény igazolta Klaus Wagner korábbi sejtését, amit Wagner-sejtésként ismertek; Wagner jóval korábban megsejtette, de csak 1970-ben publikálta.^[7]

A bizonyítás folyamata során Seymour és Robertson a gráfminor-tételt is bebizonyítják; ebben azt határozzák meg, hogy bármely rögzített H gráf esetén milyen a durva szerkezete azoknak a gráfoknak, melyek nem tartalmazzák H-t minorként. A tétel megfogalmazása igen hosszú és bonyolult, de dióhéjban azt állítja, hogy az ilyen gráfok szerkezete olyan, kisebb gráfok klikkösszegének felel meg, melyek korlátos nemszámú felületekbe beágyazott gráfokból kisebb módosításokkal előállnak. Így elméletük feltárja a gráfminorok és a gráfok topologikus beágyazásai közötti alapvető kapcsolatokat.^[8]

Bármely H esetén az egyszerű, H-minor-mentes gráfok ritkák, tehát éleik száma kisebb a csúcsok valamely konstansszorosánál.^[9] Konkrétabban, ha H csúcsainak száma h, akkor egy n-csúcsú, egyszerű, H-minormentes gráf éleinek száma legfeljebb ${\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}$ lehet, és egyes K_h-minormentes gráfok rendelkeznek is ennyi éllel.^[10] Így tehát ha H csúcsainak száma h, akkor a H-minormentes gráfok átlagos fokszáma ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$, ezért degeneráltsága ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$. A H-minormentes gráfok ráadásul rendelkeznek a síkba rajzolható gráfok síkgráf-elválasztási tételéhez hasonló elválasztási tétellel: tetszőleges, rögzített H, továbbá bármely n-csúcsú H-minormentes G gráf, lehetséges olyan, ${\displaystyle \scriptstyle O({\sqrt {n}})}$ csúcsból álló részhalmazt találni, melyek eltávolítása a G-t két (esetleg nem összefüggő) részgráfba vágja szét, melyek mindegyike legfeljebb 2n/3 csúccsal rendelkezik.^[11] Ennél erősebb állítás, hogy bármely rögzített H-ra, a H-minormentes gráfok [[[favastagság]]a ${\displaystyle \scriptstyle O({\sqrt {n}})}$.^[12]

A gráfelméleti Hadwiger-sejtés szerint ha egy G gráf nem tartalmaz a k csúcsú teljes gráffal izomorf minort, akkor G-nek létezik k − 1 színnel történő jó színezése.^[13] A k = 5 eset éppen a négyszíntétel újrafogalmazása. Hadwiger fejtését igazolták k ≤ 6-ra,^[14] de általános esetben nem tudni, igaz-e. (Bollobás, Catlin & Erdős 1980) szerint ez „a gráfelmélet egyik legmélyebb megoldatlan problémája”. A négyszíntételt gráfminorokhoz kötő másik eredmény a Robertson, Sanders, Seymour és Thomas által bejelentett snarktétel, a négyszíntétel W. T. Tutte által megsejtett megerősítése, ami azt állítja, hogy az összes olyan elválasztó élmentes 3-reguláris gráf, melynek élszínezéséhez négy színre van szükség, tartalmazza minorként a Petersen-gráfot.^[15]

A minorképzés műveletére zárt gráfcsaládok

Bővebben: Robertson–Seymour-tétel

Számos gráfcsalád rendelkezik azzal a tulajdonsággal, hogy az F-ben lévő gráf összes minora is megtalálható F-ben; az ilyen gráfcsaládot a minorképzés műveletére zártnak, röviden minorzártnak nevezzük. Például egy síkbarajzolható gráfot (vagy bármely topologikus felületbe beágyazott gráfot) tekintve sem élek eltávolításával, sem összehúzásával nem lehetséges növelni a beágyazás nemszámát; ezért mind a síkbarajzolható gráfok, mind a rögzített felületbe ágyazható gráfok minorzárt gráfcsaládokat alkotnak.

Ha F egy minorzárt család, akkor (a minorok jó előrendezési tulajdonsága miatt) az F-be nem tartozó gráfok között a minor-minimális gráfok véges X halmaza. Ezek a gráfok az F tiltott minorai: egy gráf pontosan akkor tartozik F-hez, ha nem tartalmaz minorként egyetlen, X-beli gráfot sem. Tehát minden minorzárt F család jellemezhető az X-minormentes gráfok családjaként tiltott minorok valamely véges X halmazával.^[2]

A legismertebb ilyen karakterizáció a síkbarajzolható gráfok Wagner-tétel szerinti leírása, mely szerint ezek a gráfok, melyek nem tartalmazzák sem a K₅-öt, sem a K_3,3-at minorként.^[1]

Egyes esetekben a minorzárt család tagjainak jellemzői szorosan kapcsolódnak a tiltott minorok jellemzőihez. Például az F minorzárt gráfcsalád pontosan akkor rendelkezik korlátos útszélességgel, ha a tiltott minorai között legalább egy erdő szerepel,^[16] F pontosan akkor rendelkezik korlátos famélységgel, ha tiltott minorai között szerepel útgráfok diszjunkt uniója, F pontosan akkor rendelkezik korlátos favastagsággal, ha tiltott minorjai között szerepel egy síkbarajzolható gráf,^[17] végül F pontosan akkor rendelkezik korlátos helyi favastagsággal (a gráf átmérője és favastagsága közti kapcsolat), ha tiltott minorai között szerepel egy csúcsgráf (olyan gráf, ami egyetlen csúcsa eltávolításával síkbarajzolhatóvá tehető).^[18] Amennyiben H lerajzolható a síkba úgy, hogy egyetlen élmetszés jöjjön csak létre (tehát metszési száma egy), akkor a H-minormentes gráfokhoz egy egyszerűsített gráfszerkezet-tétel tartozik, mely szerint előállíthatók síkbarajzolható gráfok és korlátos favastagságú gráfok klikkösszegeként.^[19] Például a K₅ és a K_3,3 metszési száma is egy, és ahogy Wagner megmutatta, a K₅-mentes gráfok éppen síkbarajzolható gráfok és a nyolc csúcsú Wagner-gráf 3-klikkösszegei, míg a K_3,3-mentes gráfok éppen a síkbarajzolható gráfok és a K₅ 2-klikkösszegei.^[20]

Változatok

Topologikus minorok

Egy H gráfot a G gráf topologikus minora, ha H egy felosztása izomorf G egy részgráfjával.^[21] Könnyen belátható, hogy minden topologikus minor egyben minor is. Fordítva ez nem általánosan igaz (a Petersen-gráfnak a K₅ teljes gráf ugyan minora, de nem topologikus minora), de igaz minden gráfra, melynek maximális fokszáma nem nagyobb háromnál.^[22]

A topologikus minor-reláció a véges gráfok halmazán nem jó előrendezés^[23], ezért Robertson és Seymour eredménye a topologikus minorokra nem vonatkozik. Ennek ellenére a tiltott minor-karakterizációból viszonylag egyszerűen előállítható a tiltott topologikus minor-karakterizáció.

Immerziós minorok

Egy lifting-nek, azaz felemelésnek nevezett gráfművelet központi szerepet kap az immerziók fogalomkörében. A lifting szomszédos éleken végzett művelet. Ha adott három csúcs, v, u és w, ahol (v,u) és (u,w) a gráf élei, a vuw vagy az ezzel egyenértékű (v,u), (u,w) felemelése (liftingje) az a művelet, ami törli a (v,u) és (u,w) éleket, majd hozzáadja a (v,w) élt. Amennyiben már létezett a (v,w) él, a művelet után v és w már egynél több éllel lesz összekötve, ezért a lifting alapvetően multigráf-művelet.

Amennyiben a H gráf előállítható G gráfból a G-n végzett lifting műveletek sorozatával, majd egy izomorf részgráf megtalálásával, akkor H-t a G immerziós minorjának nevezzük. Az immerziós minorok a lifting művelettel ekvivalens módon másként is definiálhatók. Azt mondjuk, H akkor egy immerziós minorja G-nek, ha létezik H csúcsaiból G csúcsaiba olyan injektív leképezés, ahol H szomszédos elemeinek képét G-ben éldiszjunkt utak kötik össze.

Az immerziós minor-reláció a véges gráfokon értelmezett jó előrendezés, ezért Robertson és Seymour eredménye az immerziós minorokra is vonatkozik. Tehát minden, immerziós minorzárt gráfcsalád rendelkezik véges tiltott immerziós minor-alapú karakterizációval.

A gráfrajzolás során az immerziós minorok a síkba nem rajzolható gráfok planarizációja során jelentkeznek: ha egy gráf metszésekkel került lerajzolásra a síkba, létrehozható egy (már síkba rajzolható) immerziós minor a metszéspontokon új csúcsok beiktatásával, közben a metszett éleket utakká felosztásával. Ez lehetővé teszi a síkbarajzolható gráfokra alkalmazott rajzolási módszerek kiterjesztését a nem síkbarajzolható gráfokra.^[24]

Korlátos mélységű minorok

Egy G gráf sekély minorja vagy korlátos mélységű minorja olyan minor, melyben G élei úgy lettek összehúzva, hogy kis átmérőjű, diszjunkt részgráfok jöjjenek létre. A korlátos mélységű minorok félúton vannak a gráfminorok és részgráfok elmélete között, amennyiben a nagyobb mélységű sekély minorok a normál gráfminorokkal esnek egybe, a 0 mélységű sekély minorok pedig éppen a részgráfok.^[25] Lehetővé teszik továbbá a gráfminorok elméletének kiterjesztését a minorképzés műveletére nézve nem zárt gráfcsaládokra, amilyenek például az 1-síkgráfok.^[26]

Párossági feltételek

A gráfminorok alternatív, az előzőekkel ekvivalens definíciója szerint H akkor G minora, amennyiben H csúcsai reprezentálhatók G csúcsdiszjunkt részfáinak olyan gyűjteményeként, melyben két, H-ban szomszédos csúcshoz mindig létezik a megfelelő G-beli két fa között húzódó él. A páratlan minorok ezt a meghatározást szigorítják a részfákra vonatkozó paritási feltételekkel. Ha H-t a fenti módon G részfáinak gyűjteménye reprezentálja, abban az esetben H akkor páratlan minorja G-nek, ha G csúcsaihoz hozzá lehet rendelni két színt úgy, hogy egy-egy részfán belül G minden éle jól színezett (végpontjai eltérő színűek), a részfák közötti szomszédosságot megjelenítő élek pedig egyszínűek (végpontjaik azonos színűek). A minoroktól eltérően a tiltott páratlan minorokkal rendelkező gráfok nem feltétlenül ritkák.^[27] A Hadwiger-sejtést, ami szerint a k-kromatikus gráfok mindig tartalmaznak k-csúcsú teljes gráfminort, szintén tanulmányozták már a páratlan minorok kontextusában.^[28]

A gráfminorok koncepciójának további, paritás-alapú kiterjesztése a páros minor, ami páros gráfot eredményez minden esetben, ha a kiindulási gráf páros. Egy H gráf akkor a páros minorja a G gráfnak, ha H előállítható G-ből csúcsok törlésével, élek törlésével, illetve a gráf egy periferikus köre mentén egymástól kettő távolságra lévő csúcspárok „összeomlasztásával” (vertex collapsing). A páros minorokra kimondható a Wagner-tétel egy formája: egy G páros gráf pontosan akkor síkbarajzolható, ha nem tartalmazza a K_3,3 teljes páros gráfot páros minorként.^[29]

Algoritmusok

Annak eldöntése, hogy G gráf tartalmazza-e H-t minorként általában NP-teljes; például ha H körgráf G-vel megegyező számú csúccsal, akkor H pontosan akkor minorja G-nek, ha G tartalmaz Hamilton-kört. Ha viszont G-t bemenetként kapjuk, H viszont rögzített, akkor polinom időben eldönthető. Konkrétabban, rögzített H esetén annak eldöntése, hogy H minorja-e G-nek, O(n³) bonyolultságú, ahol n a G csúcsainak száma, az O jelölés pedig egy konstanst rejt el, ami szuperexponenciálisan függ H-tól;^[3] az eredeti cikk óta az algoritmust O(n²) időre sikerült feljavítani.^[30] Mivel a polinom idejű algoritmussal tesztelni lehet, hogy egy gráf tartalmazza-e bármelyik tiltott minort, ezért bármely minorzárt család tagjait is polinom időben fel lehet ismerni. Ennek az eredménynek a konstruktív felhasználásához természetesen ismerni kell, hogy adott gráfcsaládnak melyek pontosan a tiltott minorjai.^[4] Néhány esetben a tiltott minorok ismertek vagy kiszámíthatóak.^[31]

Amennyiben H rögzített síkbarajzolható gráf, akkor lineáris időben tesztelhető, hogy H minorja-e a bemeneti G gráfnak.^[32] Ha H nem rögzített, akkor is ismert gyorsabb algoritmus, amennyiben G-ről tudjuk, hogy síkba rajzolható.^[33]

Fordítás

• Ez a szócikk részben vagy egészben a Graph minor 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

1. (Lovász 2006), p. 77; (Wagner 1937a).
2. (Lovász 2006), theorem 4, p. 78; (Robertson & Seymour 2004).
3. (Robertson & Seymour 1995).
4. (Fellows & Langston 1988).
5. (Lovász 2006) nem konzisztens abban, hogy megengedi-e a hurokéleket és a többszörös szomszédságokat: a 76. oldalon azt írja: „a párhuzamos élek és hurkok megengedettek”, míg a 77-ediken kijelenti: „egy gráf pontosan akkor erdő, ha nem tartalmazza a K₃ háromszöget minorként”, ami csak egyszerű gráfokra igaz.
6. (Diestel 2005), Chapter 12: Minors, Trees, and WQO; (Robertson & Seymour 2004).
7. (Lovász 2006), p. 76.
8. (Lovász 2006), pp. 80–82; (Robertson & Seymour 2003).
9. (Mader 1967).
10. (Kostochka 1982); (Kostochka 1984); (Thomason 1984); (Thomason 2001).
11. (Alon, Seymour & Thomas 1990); (Plotkin, Rao & Smith 1994); (Reed & Wood 2009).
12. (Grohe 2003)
13. (Hadwiger 1943).
14. (Robertson, Seymour & Thomas 1993).
15. (Thomas 1999); (Pegg 2002).
16. (Robertson & Seymour 1983).
17. (Lovász 2006), Theorem 9, p. 81; (Robertson & Seymour 1986).
18. (Eppstein 2000); (Demaine & Hajiaghayi 2004).
19. (Robertson & Seymour 1993); (Demaine, Hajiaghayi & Thilikos 2002).
20. (Wagner 1937a); (Wagner 1937b); (Hall 1943).
21. Diestel 2005, p. 20
22. Diestel 2005, p. 22
23. Ding (1996).
24. Buchheim et al. (2014).
25. (Nešetřil & Ossona de Mendez 2012).
26. (Nešetřil & Ossona de Mendez 2012), pp. 319–321.
27. .
28. .
29. .
30. (Kawarabayashi, Kobayashi & Reed 2012).
31. Bodlaender, Hans L. (1993. november 4.). „A Tourist Guide through Treewidth”. Acta Cybernetica 11, 1–21. o. See end of Section 5.
32. Bodlaender, Hans L. (1993. november 4.). „A Tourist Guide through Treewidth”. Acta Cybernetica 11, 1–21. o. First paragraph after Theorem 5.3
33. Adler, Isolde (2012. szeptember 1.). „Fast Minor Testing in Planar Graphs” (angol nyelven). Algorithmica 64 (1), 69–84. o. DOI:10.1007/s00453-011-9563-9. ISSN 0178-4617.

• .
• Archiválva 2009. március 18-i dátummal a Wayback Machine-ben.
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

További információk

• Weisstein, Eric W.: Graph Minor (angol nyelven). Wolfram MathWorld