Hrabě menší

Menší v teorii grafů  je graf pro daný graf , který může být tvořen odstraněním hran a vrcholů a smrštěním hran .

Teorie grafových minorů začala Wagnerovým teorémem , který říká, že graf je rovinný právě tehdy, když jeho minority nepatří ani do úplného grafu K 5 , ani do úplného bipartitního grafu K 3,3 [1] [2] . Z Robertsonova-Seymourova teorému vyplývá, že pro jakoukoli vlastnost grafů, která je zachována při odstraňování a zkracování hran [3] [4] , existují analogy zakázané vedlejší charakterizace .

U libovolného grafu H lze zkontrolovat, zda je H vedlejší od vstupního grafu G v polynomiálním čase [5] . Spolu s charakterizací zakázanými nezletilými vyplývá, že jakákoli vlastnost grafu, která je zachována pod delecemi a kontrakcemi, může být rozpoznána v polynomiálním čase [6] .

Mezi další výsledky a domněnky využívající grafové minority patří teorém o grafové struktuře , podle kterého grafy, které neobsahují H jako moll, lze vytvořit slepením jednodušších částí, a Hadwigerův domněnka , která dává do souvislosti nemožnost vybarvování grafu s existencí velkého kompletního grafu jako jeho vedlejší. Důležitými variantami grafových minorů jsou topologické minority a ponořené minority.

Definice

Kontrakce hrany je operace, která odstraní hranu z grafu a sloučí konce hrany do jednoho vrcholu. Neorientovaný graf H je menší než jiný neorientovaný graf G , pokud lze graf izomorfní k H získat z G stažením hran, odstraněním některých hran a odstraněním některých izolovaných vrcholů. Pořadí, ve kterém se kontrakce a delece v G provádějí , neovlivňuje výsledný graf H .

Graph minors jsou často studovány v obecnějším kontextu matroid minors . V této souvislosti se obvykle předpokládá, že grafy jsou propojené, mohou mít smyčky a více hran (tj. za multigrafy se považují , nikoli jednoduché grafy). Vytahování smyčky a odstraňování ostří jsou zakázány. S tímto přístupem, odstranění hrany ponechá hodnost grafu beze změny, zatímco stažení hrany vždy sníží hodnost o jednu.

V jiných kontextech (jako například při studiu pseudolesů ) má smysl umožnit odstranění řezných hran a odpojení grafů, ale také má smysl zakázat multigrafy. V této verzi teorie grafových minorů je graf vždy zjednodušen po jakékoli kontrakci hrany, aby se eliminovaly smyčky a vícenásobné hrany [7]

Příklad

V následujícím příkladu je graf H menší než graf G :

H.

G.

Ilustruje to následující obrázek. Nejprve sestrojíme podgraf G tak, že odstraníme čárkované hrany (a výsledný izolovaný vrchol) a poté stáhneme šedý okraj (spojením dvou vrcholů, které hrana spojuje):

Hlavní výsledky a dohady

Lze snadno ověřit, že relace grafových minorů tvoří částečné pořadí na třídě izomorfismu neorientovaných grafů - relace je tranzitivní (mollol grafu G je sám o sobě moll G ) a grafy G a H mohou být navzájem vlastní. minors, pokud jsou izomorfní, protože jakákoli netriviální operace s minorem odstraňuje hrany nebo vrcholy. Hluboký výsledek Neila Robertsona a Paula Seymoura uvádí, že toto částečné uspořádání je ve skutečnosti zcela kvazi-uspořádané  — vzhledem k nekonečnému seznamu G 1 , G 2 ,… konečných grafů jsou vždy dva indexy i < j , takže G i je minorita grafu G j . Ekvivalentní formulací tvrzení je, že jakákoliv množina grafů může mít pouze konečný počet minimálních prvků vedlejší relací [8] . Tento výsledek dokazuje domněnku dosud známou jako Wagnerova domněnka. Wagner se domníval mnohem dříve, ale zveřejnil to až v roce 1970 [9] .

V průběhu důkazu Seymour a Robertson také dokázali větu o struktuře grafu , ve které určili pro jakýkoli pevný graf H hrubou strukturu jakéhokoli grafu, který neobsahuje H jako moll. Výrok věty je dlouhý a spletitý, ale stručně řečeno věta říká, že takový graf musí mít strukturu součtu nad klikami menších grafů, které se získají mírnou úpravou grafů vložených do ploch ohraničeného rodu . Jejich teorie tedy zakládá zásadní spojení mezi grafy minors a topologickým vnořením grafů [10] [11] .

Pro jakýkoli graf H musí být jednoduché grafy bez H- minorových řídkých , což znamená, že počet hran je menší než nějaké konstanty krát počet vrcholů [12] . Přesněji řečeno, má -li H h vrcholů, pak jednoduchý n -vrcholový H -minor -prostý graf může mít nejvíce hran a některé Kh -bez- minorové grafy mají alespoň tento počet hran [13] . Pokud tedy H má h vrcholů, pak H -minor-free grafy mají průměrný stupeň a navíc degeneraci . Kromě toho mají grafy bez H -minororů rozdělovací teorém podobný teorému o rozdělování rovinných grafů – pro jakýkoli pevný H a každý n -vrcholový H -bez- minorový graf G lze najít podmnožinu vrcholů o velikosti , jejichž odstranění rozdělí graf G na dva (případně nespojené) podgrafy s nejvýše 2 n /3 vrcholy v každém [14] . Ještě přísněji platí, že pro jakýkoli pevný H , H -minororní grafy mají šířku stromu [15] .

Hadwigerova domněnka vychází z předpokladu, že pokud graf G neobsahuje menší izomorfii ke kompletnímu grafu s k vrcholy, pak má graf G pravidelné zabarvení v k  − 1 barvách [16] . Případ k  =5 je přeformulováním problému čtyř barev . Hadwigerova domněnka byla prokázána pro k  ≤ 6 [17] , ale ne obecně. Bolobas, Katlin a Erdős [18] označili problém za „jeden z nejhlubších nevyřešených problémů v teorii grafů“. Dalším výsledkem vztahujícím se k teorému o čtyřech barvách s menšími grafy je teorém snark , který oznámili Robertson, Sanders, Seymour a Thomas [19] . Věta je posílením teorému o čtyřech barvách a byla předložena (jako domněnka) Tuttem a uvádí, že jakýkoli 3-běžný bezmůstkový graf , který vyžaduje čtyři barvy, aby byly obarveny čárami, musí obsahovat Petersenův graf jako vedlejší [20 ] [21] .

Rodiny grafů uzavřené u nezletilých

Mnoho rodin grafů má tu vlastnost, že jakákoli menší část grafu v F je také v F . V tomto případě se o třídě grafů říká, že je vedlejší uzavřená . Například pro jakýkoli rovinný graf nebo vložení grafu do pevného topologického povrchu nemůže ani odstranění hran, ani stažení hran zvýšit rod vložení. Rovinné grafy a grafy, které lze vložit do libovolné pevné plochy, tedy tvoří méně uzavřené rodiny.

Je-li F minoritně uzavřená rodina, pak (kvůli vlastnosti zcela kvazi-uspořádání nezletilých) mezi grafy nepatřícími do F existuje konečná množina X minoritních minimálních grafů. Tyto grafy jsou pro F zakázány jako nezletilé  — graf patří do F právě tehdy, když neobsahuje žádný graf z X jako minors . Jakoukoli minoritní uzavřenou rodinu F lze tedy charakterizovat jako rodinu grafů bez mollů z X pro nějakou konečnou množinu X zakázaných minorů [3] [4] .

Známým příkladem tohoto typu charakterizace je Wagnerův teorém , který charakterizuje rovinné grafy jako grafy, které nemají ani K 5 ani K 3,3 jako vedlejší [1] [2] .

V některých případech mohou vlastnosti grafů v menšinově uzavřené rodině úzce souviset s vlastnostmi vyloučených nezletilých. Například vedlejší uzavřená rodina grafů F má ohraničenou cestu tehdy a jen tehdy, když zakázaná rodina rodiny zahrnuje les [22] , F má ohraničenou hloubku stromu tehdy a jen tehdy, když zakázané menší skupiny obsahují oddělené spojení cest , F má omezenou šířku stromu tehdy a jen tehdy, když jeho zakázané vedlejší položky obsahují rovinný graf [23] , a F má omezenou místní šířku stromu (funkční vztah mezi průměrem a šířkou stromu) právě tehdy, když jeho zakázané vedlejší položky obsahují vrcholový graf (a graf, který se stává rovinným, když je jeden vrchol) [24] [25] . Pokud lze H nakreslit na rovině s jediným průsečíkem (tj. počet průsečíků grafu je roven jedné), pak pro grafy bez H -moll platí věta o zjednodušené struktuře, podle níž jsou takové grafy klikový součet rovinných grafů a grafů s ohraničenou šířkou stromu [26] [27] . Například K 5 i K 3,3 mají průsečík číslo jedna, a jak ukázal Wagner, grafy bez K 5 jsou přesně 3 klikové součty rovinných grafů a osmivrcholového Wagnerova grafu , zatímco ty bez K 3,3 grafy jsou přesně 2-klikové součty rovinných grafů a K 5 [28] .

Variace

Topologické minory

Graf H se nazývá topologická moll grafu G , pokud je graf dělení H izomorfní k podgrafu G [ 29] . Je snadné vidět, že každý topologický moll je moll (v obvyklém smyslu). Opak však obecně neplatí (např. úplný graf K 5 v Petersenově grafu je moll, ale není topologický moll), ale platí pro graf s maximálním stupněm nepřesahujícím tři [30] .

Vztah topologických minorů není zcela kvazi-uspořádaný na množině konečných grafů [31] , a proto je výsledek Robertsona a Seymoura pro topologické minory nepoužitelný. Je však snadné zkonstruovat charakterizace konečnými zakázanými topologickými minors z charakterizace konečnými zakázanými minors.

Ponořený moll

Operace grafu, nazývaná lifting , je ústředním konceptem v konceptu ponoření . Zvedání je operace na sousedních hranách. Jsou-li dány tři vrcholy v , u a w , kde (v, u) a (u, w)  jsou hrany grafu, zvedání vuw nebo ekvivalentně (v, u), (u, w)  je operace, která odstraní dvě hrany (v , u) a (u, w) a přidá hranu (v, w) . V případě, že hrana (v, w) je již přítomna, budou v a w spojeny další hranou, takže operace je v podstatě multigrafová operace.

V případě, že graf H lze získat z grafu G posloupností zdvihacích operací (přes G ) a následným nalezením izomorfního podgrafu, říkáme, že H je vnořená moll grafu G .

Existuje další způsob, jak definovat ponořené nezletilé, což je ekvivalentní operaci zvedání. Říkáme, že H je vnořená moll grafu G , pokud existuje injektivní zobrazení z vrcholů H do vrcholů G takové, že obrazy sousedních prvků H jsou v G spojeny cestami, které nemají společné hrany.

Vztah ponořených nezletilých je zcela kvazi-uspořádaný na množině konečných grafů, a proto jsou výsledky Roebrtsona a Seymoura použitelné i na ponořené nezletilé. Navíc to znamená, že každá rodina uzavřená v ponořených nezletilých je charakterizována omezenou rodinou zakázaných vnořených nezletilých.

Ve vizualizaci grafů se ponořené minory objevují jako planarizace nerovinných grafů  — z nakreslení grafu na rovině s průsečíky lze vytvořit ponořenou minoritu nahrazením každého průsečíku novým vrcholem a rozdělením každé překřížené hrany do cesty. To umožňuje rozšířit metody kreslení pro rovinné grafy na nerovinné grafy [32] .

Mělké nezletilé

Mělký moll grafu G  je moll, ve kterém okraje grafu G , stažené tak, aby získaly moll, tvoří nesouvislé podgrafy o malém průměru . Mělké nezletilé tvoří jakýsi most mezi grafovými menšími a podgrafy v tom smyslu, že mělké nezletilé s vysokou hloubkou jsou stejné jako obvyklé typy nezletilých, zatímco mělké nezletilé s nulovou hloubkou jsou přesně podgrafy [33] . Umožňují také rozšířit teorii grafových minorů na třídy grafů, jako jsou 1-rovinné grafy , které nejsou uzavřeny v braní minorů [34] .

Algoritmy

Problém rozhodnutelnosti , zda je graf H obsažen v grafu G jako vedlejší, je obecně NP-úplný. Například, jestliže H je cyklus se stejným počtem vrcholů jako G , pak H je menší z G právě tehdy, když G obsahuje hamiltonovský graf . Pokud je však G vstup a H je pevné, lze problém vyřešit v polynomiálním čase. Přesněji řečeno, průběžná doba kontroly, zda je H menší než G , je v tomto případě O ( n 3 ), kde n  je počet vrcholů v G a O velké skrývá konstantu, která superexponenciálně závisí na H [5] . Díky výsledku na grafu minors se tento algoritmus zlepšuje na O ( n 2 ) [35] . Při použití polynomiálního-časového algoritmu ke kontrole, zda daný graf obsahuje některého ze zakázaných nezletilých osob, je tedy možné rozpoznat členy jakékoli uzavřené rodiny v polynomiálním čase . Pro konstruktivní aplikaci tohoto výsledku je však nutné znát zakázané minory z rodiny grafů [6] .

Poznámky

  1. ↑ 12 Lovász , 2006 , str. 77.
  2. ↑ 12 Wagner, 1937a .
  3. ↑ 1 2 Lovász, 2006 , svazek 4, s. 78.
  4. ↑ 12 Robertson , Seymour, 2004 .
  5. ↑ 12 Robertson , Seymour, 1995 .
  6. ↑ 12 Fellows , Langston, 1988 .
  7. ↑ Lovász (2006 ) si protiřečí. Na straně 76 píše, že „rovnoběžné hrany a smyčky jsou povoleny“, ale na straně 77 uvádí, že „graf je les právě tehdy, když neobsahuje trojúhelník K 3 jako vedlejší“, což platí pouze pro jednoduché grafy .
  8. ↑ Diestel (2005 ), Kapitola 12: Nezletilí, stromy a WQO; Robertson, Seymour (2004 ).
  9. ↑ Lovász, 2006 , str. 76.
  10. ↑ Lovász, 2006 , str. 80-82.
  11. ↑ Robertson, Seymour, 2003 .
  12. ↑ Mader, 1967 .
  13. ↑ Kostochka, 1984 ; Thomason, 1984 ; Thomason, 2001 .
  14. ↑ Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Rákos, dřevo, 2009 .
  15. ↑ Grohe, 2003 .
  16. ↑ Hadwiger, 1943 .
  17. ↑ Robertson, Seymour, Thomas, 1993 .
  18. ↑ Bollobás, Catlin, Erdős, 1980 .
  19. ↑ Od roku 2012 však důkaz ještě nebyl zveřejněn.
  20. ↑ Thomas, 1999 .
  21. ↑ Pegg, 2002 .
  22. ↑ Robertson, Seymour, 1983 .
  23. ↑ Lovász (2006 ), Věta 9, str. 81; Robertson, Seymour (1986 ).
  24. ↑ Eppstein, 2000 .
  25. ↑ Demaine, Hajiaghayi, 2004 .
  26. ↑ Robertson, Seymour, 1993 .
  27. ↑ Demaine, Hajiaghayi, Thilikos, 2002 .
  28. ↑ Wagner, 1937a ; Hall, 1943 .
  29. ↑ Diestel, 2005 , str. dvacet.
  30. ↑ Diestel, 2005 , str. 22.
  31. ↑ Ding, 1996 .
  32. ↑ Buchheim, Chimani, Gutwenger, Jünger, Mutzel, 2014 .
  33. ↑ Nešetřil, de Mendez, 2012 .
  34. ↑ Nešetřil, de Mendez, 2012 , str. 319-321.
  35. ↑ Kawarabayashi, Kobayashi, Reed, 2012 .

Literatura

Odkazy