Minor (gráfelmélet) forrásának megtekintése

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étel]]lel kezdődött, miszerint egy gráf pontosan akkor [[síkbarajzolható gráf|síkbarajzolható]], ha minorai között nem található meg sem a ''K''<sub>5</sub> [[teljes gráf]], sem a ''K''<sub>3,3</sub> [[teljes páros gráf]].<ref name="w">{{harvtxt|Lovász|2006}}, p.&nbsp;77; {{harvtxt|Wagner|1937a}}.</ref> 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 gráfok szerinti osztályozás|tiltott minorok szerinti karakterizáció]].<ref name="rst">{{harvtxt|Lovász|2006}}, theorem 4, p.&nbsp;78; {{harvtxt|Robertson|Seymour|2004}}.</ref>
Adott ''H'' gráfra [[polinom idő]] alatt tesztelhető, hogy az a bemeneti ''G'' gráf minora-e;<ref name="rs95"/> 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ő.<ref name="fl88"/>

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 (gráfelmélet)|Hadwiger-sejtés]], ami a gráfok színezésének problémáját összeköti a nagyméretű [[teljes gráf]]minorok 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áf]]ot 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 minor]]ok 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áf]]okról van szó); a hurokél összehúzása és az [[elválasztó él]]ek 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 rangja|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.<ref>{{harvtxt|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''<sub>3</sub> háromszöget minorként”, ami csak egyszerű gráfokra igaz.</ref>

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. [[Image:GraphMinorExampleA.png|100px|H gráf]]

G. [[Image:GraphMinorExampleB.svg|200px|G gráf]]

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):

[[Image:GraphMinorExampleC.svg|190px|A G és H közötti transzformáció]]

==Jelentős eredmények és sejtések==
Egyszerűen ellenőrizhető, hogy a minorképzés, mint [[bináris reláció]] [[részbenrendezés]]t alkot az irányítatlan gráfok izomorfizmus-osztályain: [[tranzitív reláció|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 (matematikus)|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''<sub>1</sub>, ''G''<sub>2</sub>... végtelen listáját, mindig létezik két olyan ''i'' < ''j'' index, melyre ''G''<sub>''i''</sub> a ''G''<sub>''j''</sub> minora. Ezzel ekvivalens kijelentés, hogy gráfok tetszőleges halmazának a minorrendezést tekintve csak véges számú [[minimális elem]]e lehet.<ref>{{harvtxt|Diestel|2005}}, Chapter 12: Minors, Trees, and WQO; {{harvtxt|Robertson|Seymour|2004}}.</ref> 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.<ref>{{harvtxt|Lovász|2006}}, p.&nbsp;76.</ref>

A bizonyítás folyamata során Seymour és Robertson a [[gráfminor-tétel]]t 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 művelet|klikkösszegének]] felel meg, melyek korlátos [[nemszám]]ú felületekbe [[gráfbeágyazás|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 [[gráfbeágyazás|topologikus beágyazásai]] közötti alapvető kapcsolatokat.<ref>{{harvtxt|Lovász|2006}}, pp. 80–82; {{harvtxt|Robertson|Seymour|2003}}.</ref>

Bármely ''H'' esetén az egyszerű, ''H''-minor-mentes gráfok [[ritka gráf|ritkák]], tehát éleik száma kisebb a csúcsok valamely konstansszorosánál.<ref>{{harvtxt|Mader|1967}}.</ref> Konkrétabban, ha ''H'' csúcsainak száma ''h'', akkor egy ''n''-csúcsú, egyszerű, ''H''-minormentes gráf éleinek száma legfeljebb <math>\scriptstyle O(nh\sqrt{\log h})</math> lehet, és egyes ''K<sub>h</sub>''-minormentes gráfok rendelkeznek is ennyi éllel.<ref>{{harvtxt|Kostochka|1982}}; {{harvtxt|Kostochka|1984}}; {{harvtxt|Thomason|1984}}; {{harvtxt|Thomason|2001}}.</ref> Így tehát ha ''H'' csúcsainak száma ''h'', akkor a ''H''-minormentes gráfok átlagos fokszáma <math>\scriptstyle O(h \sqrt{\log h})</math>, ezért [[degeneráltság (gráfelmélet)|degeneráltsága]] <math>\scriptstyle O(h \sqrt{\log h})</math>. A ''H''-minormentes gráfok ráadásul rendelkeznek a [[síkba rajzolható gráf]]ok [[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, <math>\scriptstyle O(\sqrt{n})</math> 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 2''n''/3 csúccsal rendelkezik.<ref>{{harvtxt|Alon|Seymour|Thomas|1990}}; {{harvtxt|Plotkin|Rao|Smith|1994}}; {{harvtxt|Reed|Wood|2009}}.</ref> Ennél erősebb állítás, hogy bármely rögzített ''H''-ra, a ''H''-minormentes gráfok [[[favastagság]]a <math>\scriptstyle O(\sqrt{n})</math>.<ref>{{harvtxt|Grohe|2003}}</ref>

A gráfelméleti [[Hadwiger-sejtés (gráfelmélet)|Hadwiger-sejtés]] szerint ha egy ''G'' gráf nem tartalmaz a ''k'' csúcsú [[teljes gráf]]fal izomorf minort, akkor ''G''-nek létezik ''k''&nbsp;&minus;&nbsp;1 színnel történő [[gráfok színezése|jó színezése]].<ref>{{harvtxt|Hadwiger|1943}}.</ref> A ''k''&nbsp;=&nbsp;5 eset éppen a [[négyszíntétel]] újrafogalmazása. Hadwiger fejtését igazolták ''k''&nbsp;≤&nbsp;6-ra,<ref>{{harvtxt|Robertson|Seymour|Thomas|1993}}.</ref> de általános esetben nem tudni, igaz-e. {{harvtxt|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ó él]]mentes [[3-reguláris gráf]], melynek [[élszínezés]]éhez négy színre van szükség, tartalmazza minorként a [[Petersen-gráf]]ot.<ref>{{harvtxt|Thomas|1999}}; {{harvtxt|Pegg|2002}}.</ref>

==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áf]]ot (vagy bármely [[topologikus felület]]be [[gráf beágyazása|beágyazott gráf]]ot) 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 gráfok szerinti osztályozás|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.<ref name="rst"/>

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<sub>5</sub>-öt, sem a K<sub>3,3</sub>-at minorként.<ref name="w"/>

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ég]]gel, ha a tiltott minorai között legalább egy [[fa (gráfelmélet)|erdő]] szerepel,<ref>{{harvtxt|Robertson|Seymour|1983}}.</ref> ''F'' pontosan akkor rendelkezik korlátos [[famélység]]gel, ha tiltott minorai között szerepel [[útgráf]]ok diszjunkt uniója, ''F'' pontosan akkor rendelkezik korlátos [[favastagság]]gal, ha tiltott minorjai között szerepel egy [[síkbarajzolható gráf]],<ref>{{harvtxt|Lovász|2006}}, Theorem 9, p.&nbsp;81; {{harvtxt|Robertson|Seymour|1986}}.</ref> végül ''F'' pontosan akkor rendelkezik korlátos helyi favastagsággal (a gráf [[átmérő (gráfelmélet)|á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ő).<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004}}.</ref> Amennyiben ''H'' lerajzolható a síkba úgy, hogy egyetlen élmetszés jöjjön csak létre (tehát [[Metszési szám (gráfelmélet)|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összeg]]eként.<ref>{{harvtxt|Robertson|Seymour|1993}}; {{harvtxt|Demaine|Hajiaghayi|Thilikos|2002}}.</ref> Például a ''K''<sub>5</sub> és a ''K''<sub>3,3</sub> metszési száma is egy, és ahogy Wagner megmutatta, a ''K''<sub>5</sub>-mentes gráfok éppen síkbarajzolható gráfok és a nyolc csúcsú [[Wagner-gráf]] 3-klikkösszegei, míg a ''K''<sub>3,3</sub>-mentes gráfok éppen a síkbarajzolható gráfok és a&nbsp;''K''<sub>5</sub> 2-klikkösszegei.<ref>{{harvtxt|Wagner|1937a}}; {{harvtxt|Wagner|1937b}}; {{harvtxt|Hall|1943}}.</ref>

==Változatok==
===Topologikus minorok===
Egy ''H'' gráfot a ''G'' gráf '''topologikus minora''', ha ''H'' egy [[Topologikus izomorfia|felosztása]] [[gráfizomorfizmus|izomorf]] ''G'' egy [[részgráf]]jával.<ref>{{Harvnb|Diestel|2005|p=20}}</ref> Könnyen belátható, hogy minden topologikus minor egyben minor is. Fordítva ez nem általánosan igaz (a [[Petersen-gráf]]nak a ''K''<sub>5</sub> [[teljes gráf]] ugyan minora, de nem topologikus minora), de igaz minden gráfra, melynek maximális fokszáma nem nagyobb háromnál.<ref>{{Harvnb|Diestel|2005|p=22}}</ref>

A topologikus minor-reláció a véges gráfok halmazán nem jó előrendezés{{sfnp|Ding|1996}}, 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ó.<!-- However it is straightforward to construct finite forbidden topological minor characterizations from finite forbidden minor characterizations by replacing every branch set with ''k'' outgoing edges by every tree on ''k'' leaves that has down degree at least two.-->

===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íkbarajzolható gráf|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.{{sfnp|Buchheim|Chimani|Gutwenger|Jünger|2014}}

===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ő (gráfelmélet)|á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.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}.</ref> 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áf]]ok.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, pp. 319–321.</ref>

===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 minor]]ok 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.<ref>{{citation
 | last1 = Kawarabayashi | first1 = Ken-ichi | author1-link = Ken-ichi Kawarabayashi
 | last2 = Reed | first2 = Bruce | author2-link = Bruce Reed (mathematician)
 | last3 = Wollan | first3 = Paul
 | contribution = The graph minor algorithm with parity conditions
 | doi = 10.1109/focs.2011.52
 | pages = 27–36
 | publisher = Institute of Electrical and Electronics Engineers
 | title = 52nd Annual IEEE Symposium on Foundations of Computer Science
 | year = 2011}}.</ref> A [[Hadwiger-sejtés (gráfelmélet)|Hadwiger-sejtés]]t, ami szerint a ''k''-kromatikus gráfok mindig tartalmaznak ''k''-csúcsú [[teljes gráf]]minort, szintén tanulmányozták már a páratlan minorok kontextusában.<ref>{{citation
 | last1 = Geelen | first1 = Jim | author1-link = Jim Geelen
 | last2 = Gerards | first2 = Bert
 | last3 = Reed | first3 = Bruce | author3-link = Bruce Reed (mathematician)
 | last4 = Seymour | first4 = Paul | author4-link = Paul Seymour (mathematician)
 | last5 = Vetta | first5 = Adrian
 | doi = 10.1016/j.jctb.2008.03.006
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 2467815
 | pages = 20–29
 | series = Series B
 | title = On the odd-minor variant of Hadwiger's conjecture
 | volume = 99
 | year = 2009}}.</ref>

A gráfminorok koncepciójának további, paritás-alapú kiterjesztése a [[páros minor]], ami [[páros gráf]]ot 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ör]]e 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ó gráf|síkbarajzolható]], ha nem tartalmazza a ''K''<sub>3,3</sub> [[teljes páros gráf]]ot páros minorként.<ref>{{citation
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | last2 = Kalai | first2 = Gil | author2-link = Gil Kalai
 | last3 = Nevo | first3 = Eran
 | last4 = Novik | first4 = Isabella | author4-link = Isabella Novik
 | last5 = Seymour | first5 = Paul | author5-link = Paul Seymour (mathematician)
 | arxiv = 1312.0210
 | doi = 10.1016/j.jctb.2015.08.001
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 3425242
 | pages = 219–228
 | series = Series B
 | title = Bipartite minors
 | volume = 116
 | year = 2016}}.</ref>

==Algoritmusok==
Annak [[eldöntési probléma|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ör]]t. 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''<sup>3</sup>) 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;<ref name="rs95">{{harvtxt|Robertson|Seymour|1995}}.</ref> az eredeti cikk óta az algoritmust ''O''(''n''<sup>2</sup>) időre sikerült feljavítani.<ref name="kkr12">{{harvtxt|Kawarabayashi|Kobayashi|Reed|2012}}.</ref> 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.<ref name="fl88">{{harvtxt|Fellows|Langston|1988}}.</ref> Néhány esetben a tiltott minorok ismertek vagy kiszámíthatóak.<ref>{{Cite journal|last=Bodlaender|first=Hans L.|date=1993|title=A Tourist Guide through Treewidth|url=https://dspace.library.uu.nl/bitstream/handle/1874/2301/1992-12.pdf?sequence=1|journal=Acta Cybernetica|volume=11|pages=1–21|via=}} See end of Section 5.</ref>

Amennyiben ''H'' rögzített [[síkbarajzolható gráf]], akkor lineáris időben tesztelhető, hogy ''H'' minorja-e a bemeneti ''G'' gráfnak.<ref>{{Cite journal|last=Bodlaender|first=Hans L.|date=1993|title=A Tourist Guide through Treewidth|url=https://dspace.library.uu.nl/bitstream/handle/1874/2301/1992-12.pdf?sequence=1|journal=Acta Cybernetica|volume=11|pages=1–21|via=}} First paragraph after Theorem 5.3</ref> Ha ''H'' nem rögzített, akkor is ismert gyorsabb algoritmus, amennyiben ''G''-ről tudjuk, hogy síkba rajzolható.<ref>{{Cite journal|last=Adler|first=Isolde|last2=Dorn|first2=Frederic|last3=Fomin|first3=Fedor V.|last4=Sau|first4=Ignasi|last5=Thilikos|first5=Dimitrios M.|date=2012-09-01|title=Fast Minor Testing in Planar Graphs|url=http://www.lirmm.fr/~sau/Pubs/Minor-planar.pdf|journal=Algorithmica|language=en|volume=64|issue=1|pages=69–84|doi=10.1007/s00453-011-9563-9|issn=0178-4617}}</ref>

==Fordítás==
* {{fordítás|en|Graph minor|oldid=826478544|n=a|4=angol}}

==Jegyzetek==
{{reflist|2}}

{{refbegin|2}}
*{{citation
 | last1 = Alon | first1 = Noga | author1-link = Nógá Álón
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)
 | doi = 10.2307/1990903
 | mr = 1065053
 | journal = [[Journal of the American Mathematical Society]]
 | pages = 801–808
 | title = A separator theorem for nonplanar graphs
 | issue = 4
 | url = http://www.ams.org/journals/jams/1990-03-04/S0894-0347-1990-1065053-0/home.html
 | volume = 3
 | year = 1990
 | jstor = 1990903}}.
*{{citation
 |last1        = Bollobás
 |first1       = B.
 |author1-link = Bollobás Béla (matematikus)
 |last2        = Catlin
 |first2       = P. A.
 |last3        = Erdős
 |first3       = Paul
 |author3-link = Erdős Pál
 |journal      = [[European Journal of Combinatorics]]
 |pages        = 195–199
 |title        = Hadwiger's conjecture is true for almost every graph
 |url          = http://www2.renyi.hu/~p_erdos/1980-10.pdf
 |volume       = 1
 |year         = 1980
 |doi          = 10.1016/s0195-6698(80)80001-1
 |deadurl      = yes
 |archiveurl   = https://web.archive.org/web/20090318165333/http://www2.renyi.hu/~p_erdos/1980-10.pdf
 |archivedate  = 2009-03-18
 |df           = 
 |access-date  = 2018-02-23
}} {{Wayback|url=http://www2.renyi.hu/~p_erdos/1980-10.pdf |date=20090318165333 }}.
*{{citation
 | last1 = Buchheim | first1 = Christoph
 | last2 = Chimani | first2 = Markus
 | last3 = Gutwenger | first3 = Carsten
 | last4 = Jünger | first4 = Michael
 | last5 = Mutzel | first5 = Petra | author5-link = Petra Mutzel
 | editor-last = Tamassia | editor-first = Roberto | editor-link = Roberto Tamassia
 | contribution = Crossings and planarization
 | publisher = CRC Press, Boca Raton, FL
 | series = Discrete Mathematics and its Applications (Boca Raton)
 | title = Handbook of Graph Drawing and Visualization
 | year = 2014}}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | doi = 10.1007/s00453-004-1106-1
 | issue = 3
 | journal = Algorithmica
 | pages = 211–215
 | title = Diameter and treewidth in minor-closed graph families, revisited
 | url = http://erikdemaine.org/papers/DiameterTreewidth_Algorithmica/
 | volume = 40
 | year = 2004}}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | last3 = Thilikos | first3 = Dimitrios M.
 | contribution = 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor
 | doi = 10.1007/3-540-45753-4_8
 | pages = 67–80
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002)
 | volume = 2462
 | year = 2002}}
*{{citation
 | last = Diestel | first = Reinhard
 | edition = 3rd
 | isbn = 978-3-540-26183-4
 | location = Berlin, New York
 | publisher = Springer-Verlag
 | title = Graph Theory
 | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
 | year = 2005}}.
*{{citation
 | last = Ding | first = Guoli
 | doi = 10.1006/jctb.1996.0002
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1368512
 | pages = 11–23
 | series = Series B
 | title = Excluding a long double path minor
 | volume = 66
 | year = 1996}}.
*{{citation
 | last = Eppstein | first = David | authorlink = David Eppstein
 | doi = 10.1007/s004530010020
 | arxiv=math.CO/9907126
 | mr = 1759751
| journal = Algorithmica
 | pages = 275–291
 | title = Diameter and treewidth in minor-closed graph families
 | volume = 27
 | year = 2000}}.
*{{citation
 | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
 | last2 = Langston | first2 = Michael A. | author2-link = Michael Langston
 | doi = 10.1145/44483.44491
 | issue = 3
 | journal = [[Journal of the ACM]]
 | pages = 727–739
 | title = Nonconstructive tools for proving polynomial-time decidability
 | volume = 35
 | year = 1988}}.
*{{citation
 | last = Grohe | first = Martin
 | title = Local tree-width, excluded minors, and approximation algorithms
 | journal = [[Combinatorica]]
 | doi = 10.1007/s00493-003-0037-9
 | volume = 23
 | issue = 4
 | pages = 613–632
 | year = 2003
 | url = http://arxiv.org/abs/math/0001128}}.
*{{citation
 | last = Hadwiger | first = Hugo | author-link = Hugo Hadwiger
 | journal = Vierteljschr. Naturforsch. Ges. Zürich
 | pages = 133–143
 | title = Über eine Klassifikation der Streckenkomplexe
 | volume = 88
 | year = 1943}}.
*{{citation
 | last = Hall | first = Dick Wick
 | doi = 10.1090/S0002-9904-1943-08065-2
 | issue = 12
 | journal = [[Bulletin of the American Mathematical Society]]
 | pages = 935–936
 | title = A note on primitive skew curves
 | volume = 49
 | year = 1943}}.
*{{citation
 | last1 = Kawarabayashi | first1 = Ken-ichi | author1-link = Ken-ichi Kawarabayashi
 | last2 = Kobayashi | first2 = Yusuke
 | last3 = Reed | first3 = Bruce | author3-link = Bruce Reed (mathematician)
 | title = The disjoint paths problem in quadratic time
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | volume = 102
 | issue = 2
 |date=March 2012
 | pages = 424–435
 | doi = 10.1016/j.jctb.2011.07.004}}
*{{citation
 | last = Kostochka | first = Alexandr V.
 | journal = Metody Diskret. Analiz.
 | language = Russian
 | pages = 37–58
 | title = The minimum Hadwiger number for graphs with a given mean degree of vertices
 | volume = 38
 | year = 1982}}.
*{{citation
 | last = Kostochka | first = Alexandr V.
 | doi = 10.1007/BF02579141
 | journal = Combinatorica
 | pages = 307–316
 | title = Lower bound of the Hadwiger number of graphs by their average degree
 | volume = 4
 | year = 1984}}.
*{{citation
 | last = Lovász | first = László | author-link = Lovász László (matematikus)
 | doi = 10.1090/S0273-0979-05-01088-8
 | issue = 1
 | journal = [[Bulletin of the American Mathematical Society]]
 | pages = 75–86
 | title = Graph minor theory
 | volume = 43
 | year = 2006}}.
*{{citation
 | last = Mader | first = Wolfgang
 | doi = 10.1007/BF01364272
 | issue = 4
 | journal = Mathematische Annalen
 | pages = 265–268
 | title = Homomorphieeigenschaften und mittlere Kantendichte von Graphen
 | volume = 174
 | year = 1967}}.
*{{citation
 | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil
 | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez
 | doi = 10.1007/978-3-642-27875-4
 | isbn = 978-3-642-27874-7
 | mr = 2920058
 | pages = 62–65
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Sparsity: Graphs, Structures, and Algorithms
 | volume = 28
 | year = 2012}}.
*{{citation|last=Pegg|first=Ed, Jr.|authorlink=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=http://www.ams.org/notices/200209/rev-pegg.pdf | doi = 10.1109/TED.2002.1003756}}.
*{{citation
 | last1 = Plotkin | first1 = Serge
 | last2 = Rao | first2 = Satish
 | last3 = Smith | first3 = Warren D.
 | contribution = Shallow excluded minors and improved graph decompositions
 | pages = 462–470
 | title = Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994)
 | url = http://www.stanford.edu/~plotkin/lminors.ps
 | year = 1994}}.
*{{citation
 | last1 = Reed | first1 = Bruce | authorlink = Bruce Reed (mathematician)
 | last2 = Wood | first2 = David R.
 | doi = 10.1145/1597036.1597043
 | issue = 4
 | journal = ACM Transactions on Algorithms
 | pages = Article 39
 | title = A linear-time algorithm to find a separator in a graph excluding a minor
 | volume = 5
 | year = 2009}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/0095-8956(83)90079-5
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 39–61
 | title = Graph minors. I. Excluding a forest
 | volume = 35
 | year = 1983}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/0095-8956(86)90030-4
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 92–114
 | title = Graph minors. V. Excluding a planar graph
 | volume = 41
 | year = 1986}}
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | contribution = Excluding a graph with one crossing
 | editor1-last = Robertson | editor1-first = Neil
 | editor2-last = Seymour | editor2-first = Paul
 | pages = 669–675
 | publisher = [[American Mathematical Society]]
 | series = Contemporary Mathematics
 | title = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
 | volume = 147
 | year = 1993}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1006/jctb.1995.1006
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 65–110
 | title = Graph Minors. XIII. The disjoint paths problem
 | volume = 63
 | year = 1995}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/S0095-8956(03)00042-X
 | issue = 1
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 43–76
 | title = Graph Minors. XVI. Excluding a non-planar graph
 | volume = 89
 | year = 2003}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (matematikus)
 | last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
 | doi = 10.1016/j.jctb.2004.08.001
 | issue = 2
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 325–357
 | title = Graph Minors. XX. Wagner's conjecture
 | volume = 92
 | year = 2004}}.
*{{citation
 | last1 = Robertson
 | first1 = Neil
 | author1-link = Neil Robertson (matematikus)
 | last2 = Seymour
 | first2 = Paul
 | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas
 | first3 = Robin
 | author3-link = Robin Thomas (mathematician)
 | doi = 10.1007/BF01202354
 | journal = [[Combinatorica]]
 | pages = 279–361
 | title = Hadwiger's conjecture for ''K''<sub>6</sub>-free graphs
 | url = http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf
 | volume = 13
 | year = 1993
 | accessdate = 2018-02-23
 | archívurl = https://web.archive.org/web/20090410233641/http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf
 | archívdátum = 2009-04-10
 }}.
*{{citation
 | last = Thomas
 | first = Robin
 | authorlink = Robin Thomas (mathematician)
 | contribution = Recent excluded minor theorems for graphs
 | location = Cambridge
 | mr = 1725004
 | pages = 201–222
 | publisher = Cambridge Univ. Press
 | series = London Math. Soc. Lecture Note Ser.
 | title = Surveys in combinatorics, 1999 (Canterbury)
 | url = http://people.math.gatech.edu/~thomas/PAP/bcc.pdf
 | volume = 267
 | year = 1999
 | accessdate = 2018-02-23
 | archívurl = https://web.archive.org/web/20160803200552/http://people.math.gatech.edu/~thomas/PAP/bcc.pdf
 | archívdátum = 2016-08-03
 }}.
*{{citation
 | last = Thomason | first = Andrew
 | doi = 10.1017/S0305004100061521
 | issue = 2
 | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]]
 | pages = 261–265
 | title = An extremal function for contractions of graphs
 | volume = 95
 | year = 1984}}.
*{{citation
 | last = Thomason | first = Andrew
 | doi = 10.1006/jctb.2000.2013
 | issue = 2
 | journal = [[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]
 | pages = 318–338
 | title = The extremal function for complete minors
 | volume = 81
 | year = 2001}}.
*{{citation
 | last = Wagner | first = Klaus | author-link = Klaus Wagner
 | doi = 10.1007/BF01594196
 | journal = Math. Ann.
 | pages = 570–590
 | title = Über eine Eigenschaft der ebenen Komplexe
 | volume = 114
 | year = 1937a}}.
*{{citation
 | last = Wagner | first = Klaus | author-link = Klaus Wagner
 | journal = Deutsche Mathematik
 | pages = 280–285
 | title = Über eine Erweiterung des Satzes von Kuratowski
 | volume = 2
 | year = 1937b}}.
{{refend}}

==További információk==
*{{mathworld|urlname=GraphMinor|title=Graph Minor}}

[[Kategória:Gráfminorok| ]]
[[Kategória:Gráfelméleti objektumok]]