Věta o struktuře grafu je základním výsledkem teorie grafů . Výsledek zakládá hluboké spojení mezi teorií grafové minority a topologickým vnořením . Tento teorém byl formulován v sedmnácti článcích v sérii 23 článků Neila Robertsona a Paula Seymoura . Důkaz věty je velmi dlouhý a matoucí. Kawarabayashi a Mohar [1] a Lowash [2] přezkoumali větu ve formě dostupné pro laiky, popisující větu a její důsledky.
Menší část grafu G je jakýkoli graf H izomorfní ke grafu, který lze získat z podgrafu G stažením některých hran. Pokud G nemá graf H jako vedlejší, pak říkáme, že G je bez H . Nechť H je pevný graf. Intuitivně, pokud je G velký graf bez H , pak k tomu musí existovat nějaký „dobrý důvod“. Věta o struktuře grafu takový „dobrý důvod“ poskytuje v podobě hrubého popisu struktury grafu G . Každý graf G bez H má v podstatě jednu nebo dvě strukturální vady – buď je G „příliš tenký“ na to, aby obsahoval H jako vedlejší H, nebo může být G (téměř) topologicky vnořen do povrchu, který je příliš snadné vložit vedlejší H. . První příčina nastane, když H je rovinná , a obě příčiny nastanou , když je H nerovinná . Nejprve si ujasněme tyto pojmy.
Šířka stromu G je kladné celé číslo, které definuje „tenkost “ G . Například souvislý graf G má šířku stromu jedna tehdy a jen tehdy, když se jedná o strom, a G má šířku stromu dvě tehdy a jen tehdy, když se jedná o paralelně sériový graf . Je intuitivně jasné, že velký graf G má malou stromovou šířku právě tehdy, když G převezme strukturu velkého stromu, ve kterém jsou uzly a hrany nahrazeny malými grafy. V podsekci uvedeme přesnou definici šířky stromu vzhledem k součtům kliknutí. Existuje teorém, že pokud je H moll grafu G , pak šířka stromu H nepřesahuje šířku stromu G. „Dobrým důvodem“ pro to, aby byl G bez H , je to, že šířka stromu G není příliš velká . Věta o struktuře grafu má důsledek, že tento důvod platí vždy, když je H rovinné .
Důsledek 1. Pro jakýkoli rovinný graf H existuje kladné celé číslo k takové, že každý graf bez H má šířku stromu menší než k .
Hodnota k v Důsledku 1 je obvykle mnohem větší než šířka stromu H (existuje výrazná výjimka, když H = K 4 , to znamená, že H se rovná úplnému čtyřvrcholovému grafu, pro který k = 3). To je jeden z důvodů, proč se o strukturní větě říká, že popisuje "hrubou strukturu" H - volných grafů.
Zhruba řečeno, povrch je množina bodů s lokální topologickou strukturou ve formě disku. Plochy spadají do dvou nekonečných rodin – orientovatelné plochy zahrnují koule , torus , dvojitý torus atd. Mezi neorientovatelné povrchy patří skutečná projektivní rovina , Kleinova láhev a podobně . Graf je vnořen do plochy, pokud jej lze na plochu nakreslit jako množinu bodů (vrcholů) a oblouků (hran) tak, že se vzájemně neprotínají ani nedotýkají, s výjimkou případů, kdy jsou vrcholy a hrany incidentní nebo sousedící. Graf je rovinný , pokud jej lze vložit do koule. Je-li graf G vnořen do určité plochy, pak jakákoli menší část grafu G je rovněž vnořená do stejné plochy. "Dobrým důvodem" pro to, aby byl graf G bez H , je tedy možnost vložit G do povrchu, do kterého H nelze vložit.
Jestliže H není rovinný, teorém strukturního grafu může být viděn jako silné zobecnění Pontryagin-Kuratovsky teorém . Verze této věty dokázaná Wagnerem [3] uvádí, že je-li graf G bez K 5 i K 3,3 - volný, pak je G rovinný. Tato věta dává „dobrý důvod“ pro to, aby G neměl K 5 nebo K 3,3 jako vedlejší. Přesněji řečeno, G je vnořen do koule, zatímco ani K 5 ani K 3,3 nemohou být vložené do koule. Pojem „dobrý důvod“ pro větu o strukturálním grafu nestačí. Jsou vyžadovány další dva koncepty – součty za kliknutí a víry .
Klika v grafu G je libovolná množina vrcholů, které spolu sousedí v G . Pro nezáporné celé číslo k je součet k -klik dvou grafů G a K libovolný graf získaný výběrem klik G a K v grafech o velikosti m ≤ k pro nějaké nezáporné m , přičemž tyto dvě kliky identifikujeme v jedné klikě. (o velikosti m ) a odstranění nějakého (možná nulového) počtu hran v této nové klikě.
Pokud je G 1 , G 2 , ..., G n seznam grafů, můžete získat nový graf kombinací grafů ze seznamu pomocí součtů k-click . To znamená, že vytvoříme k -klikový součet grafu G 1 a G 2 , poté vytvoříme k -klikový součet grafu G 3 s předchozím výsledným grafem a tak dále. Graf má stromovou šířku nejvýše k , pokud jej lze získat jako součet k -kliknutí nějakého seznamu grafů, ve kterém má každý graf nejvýše k + 1 vrcholů.
Důsledek 1 nám ukazuje, že k -klikové součty malých grafů popisují hrubou strukturu H- free grafů v případě rovinnosti H . Je-li H nerovinné, jsme nuceni uvažovat i k -klikové součty grafů, z nichž každý vkládáme do plochy. Následující příklad s H = K 5 ilustruje tento bod. Graf K 5 lze vložit do libovolného povrchu kromě koule. Existují však grafy bez K5 , které zdaleka nejsou rovinné. Konkrétně součet 3 klik jakéhokoli seznamu rovinných grafů dává graf bez K5. Wagner [3] definoval přesnou strukturu grafů bez K5 jako součást skupiny výsledků známé jako Wagnerova věta :
Věta 2. Jestliže G je bez K 5 , pak G lze získat jako 3-klikové součty seznamu rovinných grafů a kopií nějakého konkrétního nerovinného grafu s 8 vrcholy.
Všimněte si, že věta 2 je věta o přesné struktuře, protože přesně definuje strukturu grafů bez K5. Takové výsledky jsou v teorii grafů vzácné. Věta o strukturálním grafu není přesná v tom smyslu, že pro většinu H grafů zahrnuje strukturální popis H- free grafů některé grafy, které H- free nejsou .
Existuje pokušení předpokládat, že analogie věty 2 platí pro grafy H jiné než K 5 . Možná by to znělo takto: Pro každý nerovinný graf H existuje kladné číslo k takové, že každý graf bez H lze získat jako k-klikový součet seznamu grafů, z nichž každý má nejvýše k vertices, nebo embeds v nějakém povrchu, do kterého H nelze vložit . Toto tvrzení je příliš jednoduché na to, aby bylo pravdivé. Musíme dovolit každému vnořeném grafu G i „podvádět“ dvěma omezenými způsoby. Nejprve musíme na omezeném počtu míst na povrchu povolit přidání některých nových vrcholů a hran, které se smí protínat v určité omezené složitosti . Taková místa se nazývají víry . "Složitost" víru je omezena parametrem zvaným jeho hloubka , který úzce souvisí s šířkou cesty grafu . Čtenář může přeskočit čtení přesné definice hloubky k eddy v další části. Za druhé, musíme umožnit přidání omezeného počtu nových vrcholů pro vnořené vírové grafy.
Hrana vnořeného grafu je otevřená 2-buňka povrchu, která neprotíná graf, ale jejíž hranice jsou spojením některých hran vnořeného grafu. Nechť F je plocha vnořeného grafu G a nechť v 0 , v 1 , ..., v n −1 , v n = v 0 jsou vrcholy ležící na hranici F (v pořadí cyklů). Cyklický interval pro F je množina vrcholů ve tvaru { v a , v a +1 , ..., v a + s }, kde a a s jsou celá čísla a kde index je vzat modulo n . Nechť Λ je konečný seznam intervalů cyklů pro F . Vytvoříme nový graf následovně. Pro každý interval cyklu L z Λ přidáme nový vrchol v L spojený s nějakým počtem (možná nula) vrcholů z L . Ke každé dvojici { L , M } intervalů v Λ můžeme přidat hranu spojující v L s v M , pokud L a M mají neprázdný průsečík. Výsledný graf je prý získán z G přidáním víru o hloubce nejvýše k (k ploše F ), pokud se žádný vrchol na F neobjeví ve více než k intervalech od Λ.
Věta o strukturním grafu . Pro jakýkoli graf H existuje kladné celé číslo k, takže jakýkoli graf bez H lze získat následovně:
Všimněte si, že kroky 1 a 2 poskytují prázdné grafy, pokud je H rovinné, ale omezený počet vrcholů přidaných v kroku 3 činí tvrzení kompatibilní s důsledkem 1.
Silnější verze věty o strukturálním grafu jsou možné v závislosti na množině H zakázaných nezletilých. Pokud je například jeden z grafů v H rovinný , pak každý graf bez H má stromový rozklad s omezenou šířkou. Ekvivalentně jej lze reprezentovat jako součet nad klikou grafů konstantní velikosti [4] . Pokud lze jeden z grafů H nakreslit v rovině s jedním průsečíkem , pak grafy bez H -minor umožňují klikový součet grafů konstantní velikosti a grafů ohraničeného rodu (bez použití vírů) [5] [6] ). Různá zesílení jsou také známa, pokud jeden z grafů H je vrcholový graf [7] .