Věta o struktuře grafu - Graph structure theorem

v matematika, věta o struktuře grafu je hlavním výsledkem v oblasti teorie grafů. Výsledkem je hluboká a zásadní souvislost mezi teorií nezletilí v grafu a topologické vložení. Věta je uvedena v sedmnáctém ze série 23 článků autorem Neil Robertson a Paul Seymour. Jeho důkaz je velmi dlouhý a zapojený. Kawarabayashi & Mohar (2007) a Lovász (2006) jsou průzkumy přístupné nespecialistům popisující větu a její důsledky.

Nastavení a motivace věty

A Méně důležitý grafu G je libovolný graf H to je izomorfní s grafem, který lze získat z podgrafu G podle uzavírání smluv některé hrany. Li G dělá ne mít graf H jako nezletilý, pak to říkáme G je H-volný, uvolnit. Nechat H být pevným grafem. Intuitivně, pokud G je obrovský H-bezplatný graf, pak by pro to měl existovat „dobrý důvod“. Věta o struktuře grafu poskytuje takový „dobrý důvod“ v podobě hrubého popisu struktury G. V podstatě každý H-bezplatný graf G trpí jedním ze dvou strukturálních nedostatků: buď G je „příliš tenký“ na to, aby měl H jako nezletilý, nebo G lze (téměř) topologicky vložit na povrch, který je příliš jednoduché vložit H na. První důvod platí, pokud H je rovinný graf, a platí oba důvody, pokud H není rovinný. Nejprve si ujasníme tyto pojmy.

Šířka stromu

The šířka stromu grafu G je kladné celé číslo, které určuje "tenkost" G. Například připojený graf G má šířku stromu jednu právě tehdy, je-li to strom, a G má šířku stromu dvě právě tehdy, pokud se jedná o a sériově paralelní graf. Intuitivně obrovský graf G má malou šířku stromu právě tehdy G vezme strukturu obrovského stromu, jehož uzly a hrany byly nahrazeny malými grafy. Přesnou definici šířky stromu uvádíme v podsekci týkající se součtových součtů. Je to věta, že pokud H je nezletilá z G, pak šířka stromu H není větší než G. Proto jeden „dobrý důvod“ pro G být H- zdarma je šířka stromu G není příliš velký. Věta o struktuře grafu naznačuje, že tento důvod platí vždy pro případ H je rovinný.

Dodatek 1. Pro každý rovinný graf H, existuje kladné celé číslo k takové, že každý H-volný graf má šířku stromu menší než k.

Je politováníhodné, že hodnota k v Dodatku 1 je obecně mnohem větší než šířka stromu H (Pozoruhodná výjimka je, když H = K.4, kompletní graf na čtyřech vrcholech, pro který k= 3). To je jeden z důvodů, proč se říká, že věta o struktuře grafu popisuje „hrubou strukturu“ H-bezplatné grafy.

Vkládání povrchů

Zhruba, a povrch je sada bodů s lokální topologickou strukturou disku. Povrchy spadají do dvou nekonečných rodin: orientovatelný povrchy zahrnují koule, torus, dvojitý torus a tak dále; the neorientovatelné povrchy zahrnují skutečná projektivní rovina, Kleinova láhev a tak dále. Graf vloží na ploše, pokud lze graf nakreslit na ploše jako soubor bodů (vrcholů) a oblouků (hran), které se navzájem nekříží nebo se nedotýkají, kromě případů, kdy hrany a vrcholy narážejí nebo sousedí. Graf je rovinný pokud se vloží do koule. Pokud graf G vloží na určitý povrch, pak každý menší z G také se vloží na stejný povrch. Proto „dobrý důvod“ pro G být H- to je zdarma G vloží na povrch, který H nevkládá se.

Když H není rovinný, lze na větu o struktuře grafu pohlížet jako na obrovské zobecnění Kuratowského věty. Verze této věty dokázaná Wagner (1937) uvádí, že pokud graf G je obojí K.5- zdarma a K.3,3- tedy zdarma G je rovinný. Tato věta poskytuje „dobrý důvod“ pro graf G nemít K.5 nebo K.3,3 jako nezletilí; konkrétně G vloží na kouli, zatímco ani jedna K.5 ani K.3,3 vložit na kouli. Bohužel tato představa „dobrého důvodu“ není pro teorém o struktuře grafu dostatečně propracovaná. Jsou požadovány další dva pojmy: kliky-součty a víry.

Kliky-součty

A klika v grafu G je libovolná sada vrcholů, které jsou párově sousedící G. Pro nezáporné celé číslo k, a k-klika-součet dvou grafů G a K. je libovolný graf získaný výběrem nezáporného celého čísla m ≤ k, výběr velikosti kliky m v každém z G a K., identifikující dvě kliky do jediné kliky velikosti m, poté odstraníte nulu nebo více okrajů, které spojují vrcholy v nové klice.

Li G1, G2, ..., Gn je seznam grafů, pak můžeme vytvořit nový graf připojením se k seznamu grafů prostřednictvím součtů k-clique. To znamená, že si vezmeme k-klika-součet G1 a G2, pak vezměte k-klika-součet G3 s výsledným grafem atd. Graf má maximální šířka stromu k pokud to lze získat prostřednictvím k-kliky-součty ze seznamu grafů, kde každý graf v seznamu má maximálně k + 1 vrcholy.

Důsledek 1 nám to naznačuje k-kliky-součty malých grafů popisují hrubou strukturu H-bezplatné grafy, když H je rovinný. Když H je neplanární, musíme také zvážit k-klika-součty seznamu grafů, z nichž každý je vložen na plochu. Následující příklad s H = K.5 ilustruje tento bod. Graf K.5 vloží se na každý povrch kromě koule. Nicméně existují K.5-bezplatné grafy, které nejsou ani zdaleka rovinné. Zejména výsledkem 3 kliků jakéhokoli seznamu rovinných grafů je a K.5-bezplatný graf. Wagner (1937) určil přesnou strukturu K.5-bezplatné grafy, jako součást shluku výsledků známých jako Wagnerova věta:

Věta 2. Li G je K.5- tedy zdarma G lze získat pomocí součtů se 3 klikami ze seznamu rovinných grafů a kopií jednoho speciálního nerovinného grafu s 8 vrcholy.

Poukazujeme na to, že Věta 2 je věta o přesné struktuře protože přesná struktura K.5- určují se bezplatné grafy. Takové výsledky jsou v teorii grafů vzácné. Věta o struktuře grafu není v tomto smyslu přesná, protože pro většinu grafů H, strukturální popis H-free graphs includes some graphs that are ne H-volný, uvolnit.

Víry (hrubý popis)

Dalo by se zlákat k domněnce, že analogie věty 2 platí pro grafy H jiný než K.5. Možná je pravda, že: pro jakýkoli nerovinný graf H existuje kladné celé číslo k takové, že každý graf bez H lze získat pomocí k-clique-sums ze seznamu grafů, z nichž každý má buď n maximálně k vrcholů, nebo je vložen na nějaký povrch na které se H nevkládá. Bohužel toto tvrzení ještě není dostatečně propracované, aby to byla pravda. Musíme povolit každý vložený graf Gi „podvádět“ dvěma omezenými způsoby. Nejprve musíme povolit omezený počet míst na povrchu, na které můžeme přidat nějaké nové vrcholy a hrany, které se mohou navzájem křížit způsobem omezeného složitost. Taková místa se nazývají víry. "Složitost" víru je omezena parametrem zvaným jeho hloubka, úzce souvisí s šířka cesty. Čtenář může upřednostnit odložení čtení následujícího přesného popisu víru hloubky k. Zadruhé musíme umožnit omezenému počtu nových vrcholů přidat do každého z vložených grafů víry.

Víry (přesná definice)

A tvář vloženého grafu je otevřená 2 buňka v povrchu, která je disjunktní od grafu, ale jejíž hranicí je sjednocení některých okrajů vloženého grafu. Nechat F být tváří vloženého grafu G a nechte proti0, proti1, ..., protin−1,protin = proti0 být vrcholy ležící na hranici F (v tomto kruhovém pořadí). A kruhový interval pro F je množina vrcholů formy {protiA, protiA+1, ..., protiA+s} kde A a s jsou celá čísla a kde indexy jsou redukovány modulon. Nechť Λ je konečný seznam kruhových intervalů pro F. Vytvoříme nový graf následujícím způsobem. Pro každý kruhový interval L v Λ přidáme nový vrchol protiL který se připojí k nule nebo více vrcholům v L. Nakonec pro každý pár {L, M} intervalů v Λ, můžeme přidat spojení hran protiL na protiM pokud L a M mít neprázdnou křižovatku. Výsledný graf je údajně získán z G podle přidání víru hloubky nanejvýš k(do tvářeF) za předpokladu, že žádný vrchol na hranici F se objeví ve více než k intervalů v Λ.

Výrok věty o struktuře grafu

Věta o struktuře grafu. Pro jakýkoli graf H existuje kladné celé číslo k takové, že každý graf bez H lze získat takto:

  1. Začneme seznamem grafů, kde každý graf v seznamu je vložen na povrch, na který H není vložen
  2. ke každému vloženému grafu v seznamu přidáme nanejvýš k vírů, kde každý vír má hloubku nanejvýš k
  3. ke každému výslednému grafu přidáme nanejvýš k nových vrcholů (tzv vrcholy ) a přidejte libovolný počet hran, z nichž každá má alespoň jeden ze svých koncových bodů mezi vrcholy.
  4. nakonec se spojíme pomocí k-clique-sumarizuje výsledný seznam grafů.

Všimněte si, že kroky 1. a 2. mají za následek prázdný graf, pokud H je rovinný, ale omezený počet vrcholů přidaných v kroku 3. činí prohlášení konzistentním s důsledkem 1.

Vylepšení

V závislosti na množině jsou možné posílené verze věty o struktuře grafu H zakázaných nezletilých. Například když jeden z grafů v H je rovinný, pak každý H-minor-free graph has a rozklad stromů ohraničené šířky; ekvivalentně to může být reprezentováno jako a klika-součet grafů konstantní velikosti[1] Když je jeden z grafů v H lze kreslit v rovině pouze jednou přechod, pak H-nebezplatné grafy připouštějí rozklad jako klikový součet grafů konstantní velikosti a grafů ohraničeného rodu bez vírů.[2]Jiné zesílení je také známé, když je jeden z grafů v H je vrcholový graf.[3]

Viz také

Poznámky

  1. ^ Graf nezletilí V.
  2. ^ Robertson & Seymour (1993); Demaine, Hajiaghayi & Thilikos (2002) ).
  3. ^ Demaine, Hajiaghayi & Kawarabayashi (2009).

Reference