Vedlejší (teorie grafů)

Pojem minor grafu je koncept teorie grafů . To bylo definováno a studováno Robertsonem a Seymourem v sérii článků s názvem Graph minors (I to XXIII), publikovaných v časopise Journal of Combinatorial Theory v letech 1983 až 2011.

Definice

Graf je menší konečných a neřízené grafu , pokud je lze získat prostřednictvím smluvních okrajů subgrafu části . Jinými slovy lze získat provedením libovolného počtu následujících operací: H{\ displaystyle H}G{\ displaystyle G}G{\ displaystyle G}H{\ displaystyle H}G{\ displaystyle G}

• odstranění izolovaného vrcholu  : vrchol je odstraněn z grafu;X{\ displaystyle x}X{\ displaystyle x}
• odstranění hrany  : hranu odstraníme , ale její konce zůstanou nezměněny;Xy{\ displaystyle xy}Xy{\ displaystyle xy}
• kontrakce hrany  : odstraníme hranu , dva vrcholy a spojíme je do vrcholu . Jakákoli hrana nebo je nahrazena novou hranou . Stejná hrana se nepřidá dvakrát (jedna nevytvoří rovnoběžné hrany).Xy{\ displaystyle xy}Xy{\ displaystyle xy}X{\ displaystyle x}y{\ displaystyle}z{\ displaystyle z}tX{\ displaystyle tx}ty{\ displaystyle ty}tz{\ displaystyle tz}

Tuto definici uvádí László Lovász . V literatuře lze najít různé, ale ekvivalentní definice.

• Graf . G{\ displaystyle G}

• Menší z . H{\ displaystyle H}G{\ displaystyle G}

• Průchod z do . G{\ displaystyle G}H{\ displaystyle H}

Ve výše uvedeném příkladu přejdeme z grafu na jeho vedlejší část odstraněním tří hran (v tečkovaných čarách), odstraněním izolovaného vrcholu a smrštěním hrany (šedě).

Užitečnost

Jednou z pomůcek koncepce menšího je charakterizace konkrétních tříd grafů tak, že mají (nebo nemají) určitý graf jako menší. Například rovinný graf neobsahuje ani ( úplný graf řádu 5) ani ( úplný bipartitní graf řádu 3) jako vedlejší . Tyto Robertson, Seymour věta ukazuje, že tak můžeme charakterizovat všechny grafy, které lze čerpat na daném povrchu, jako funkce skupiny vyloučených dětí a mladistvých. Pojem moll také umožňuje vyjádřit jen některé věty nebo domněnky, jako je například Hadwiger domněnky podle nichž se jakákoli grafu , jehož úplný graf s vrcholů není nezletilý colorable s barvami. K.5{\ displaystyle K_ {5}}K.3,3{\ displaystyle K_ {3,3}}G{\ displaystyle G}k{\ displaystyle k}k-1{\ displaystyle k-1}

Teorie grafických horníků je také spojena s konceptem rozkladu stromů .

Poznámky

1. Lovász 2005  ; tuto definici naleznete na straně 2 online dokumentu.

Reference

• (en) László Lovász , „  Graph Minor Theory  “ , Bull. Hořký. Matematika. Soc. (New Series) , sv.  43, n o  1,2005, str.  75–86 ( číst online ) [PDF]
• (in) Neil Robertson a Paul Seymour , „  Graph Minors. I. Vyloučení lesa  “ , Journal of Combinatorial Theory , Series B , sv.  35, n o  1,1983, str.  39–61 ( DOI  10.1016 / 0095-8956 (83) 90079-5 ).První ze třiadvaceti článků ze série Graph Minors s názvem Mineurs: exclusion d'une forêt .

Související články

• Věta Robertson-Seymour
• Snarkova věta

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">