Hloubka stromu (teorie grafů)

V teorii grafů je hloubka stromu spojeného neorientovaného grafu G numerickým invariantem G , minimální výška Tremauxova stromu pro supergraf G . Tento invariantní a související pojmy se v literatuře vyskytují pod různými názvy, včetně pořadového čísla vrcholu, uspořádaného chromatického čísla a minimální výšky eliminace stromu. Tento koncept je také blízký takovým konceptům, jako je cyklická hodnost orientovaných grafů a iterační výška jazyka regulárních jazyků [1] [2] ; [3] . Intuitivně, pokud je šířka stromugraf měří, jak daleko je graf od stromu, hloubka stromu měří, jak daleko je graf od hvězdy.

Definice

Hloubku stromu grafu G lze definovat jako minimální výšku lesa F s tou vlastností, že libovolná hrana G spojuje dvojici vrcholů spojených vztahem rodič-dítě v F [4] . Pokud je G připojeno, tato doménová struktura musí být jeden strom. Les nemusí být podgrafem G , ale pokud ano, pak je to Tremauxův strom pro G .

Množina párů rodič-dítě v F tvoří triviálně dokonalý graf a výška F je velikost největší kliky tohoto grafu. Hloubku stromu lze tedy alternativně definovat jako velikost největší kliky v triviálně dokonalém supergrafu G , což je zrcadlový obraz šířky stromu , což je o jednu menší než velikost největší kliky v akordickém supergrafu G [ 5]

Další definice je následující:

kde V je množina vrcholů grafu G a jsou souvislé složky grafu G [6] . Tato definice odráží cyklickou hodnostní definici orientovaných grafů, která používá silnou konektivitu a silně propojené komponenty namísto neorientované konektivity a propojených komponent.

Hloubku stromu lze určit pomocí zbarvení grafu . Vystředěné zbarvení grafu je zbarvení vrcholů, které má tu vlastnost, že jakýkoli připojený vygenerovaný podgraf má barvu, která se vyskytuje právě jednou. Hloubka stromu je pak minimální velikost barev potřebná pro vystředěné vybarvení grafu. Jestliže F je les výšky d , který má tu vlastnost, že jakákoli hrana G spojuje předka a potomka ve stromu, pak lze získat vycentrované zbarvení G s d barvami obarvením každého vrcholu číslem barvy rovným vzdálenost od kořene v F [7] .

Konečně to můžeme definovat jako žetonovou hru . Přesněji přesně jako hra "policajti-lupiči" . Představte si následující hru na neorientovaném grafu. Jsou zde dva hráči, lupič a policista. Lupič má jeden dílek, který posouvá po okrajích grafu. Policista má neomezený počet čipů, ale chce minimalizovat počet použitých čipů. Policista nemůže pohybovat svými figurkami umístěnými na grafu. Hra probíhá takto. Lupič umístí svou figurku, poté policista řekne, kam chce umístit další figurku a lupič pak může svou figurku posouvat po okrajích, ale ne přes obsazené vrcholy. Hra končí, když policista položí další figurku na figurku lupiče. Hloubka stromu daného grafu určuje minimální počet žetonů potřebných pro zaručenou výhru [8] [9] . Pro hvězdy stačí dva žetony - umístěte první žeton do středu hvězdy, čímž lupiče donutíte přesunout se do nějakého paprsku, a poté položte druhý žeton na žeton lupiče. Pro cestu s vrcholy používá policista strategii binárního vyhledávání , která zaručuje, že nebudou použity žádné další tokeny.

Příklady

Hloubka stromu úplného grafu se rovná počtu jeho vrcholů, v takovém případě je jediným možným lesem F , pro který musí být jakýkoli pár vrcholů ve vztahu předek-dítě, jediná cesta. Podobně hloubka stromu kompletního bipartitního grafu K x , y je min( x , y ) + 1 a ať už vrcholy umístíme jakkoli, listy lesa F musí mít v F alespoň min( x , y ) předků. . Les, na kterém je dosaženo min( x , y ) + 1, lze sestrojit tak, že z vrcholů menší části grafu vytvoříme cestu a vrcholy větší části tvoří listy stromu F spojené s nižší vrchol cesty.

Hloubka stromu cesty s n vrcholy je přesně . Les F reprezentující tuto cestu s touto hloubkou lze vytvořit umístěním kořene do středu cesty F a pokračováním rekurze ve dvou menších cestách po obou stranách kořene [10] .

Hloubka stromů a vztah k šířce stromu

Každý les s n vrcholy má hloubku stromu O(log  n ). U lesa lze vždy najít konstantní počet vrcholů, jejichž odstraněním vznikne les, který lze rozdělit na dva menší podlesy, každý s maximálně 2 n /3 vrcholy. Rekurzivním dělením těchto dvou podrostů lze snadno dosáhnout logaritmické horní hranice hloubky stromu. Stejná technika aplikovaná na dekompozici stromu grafů ukazuje, že pokud je šířka stromu n - vrcholového grafu G t , pak hloubka stromu G je O( t  log  n ) . [11] [12] Protože vnější rovinné grafy , paralelně sekvenční grafy a Halinovy ​​grafy mají omezenou šířku stromu, mají všechny také maximální logaritmickou hloubku stromu.

V opačném směru šířka stromu grafu nepřesahuje jeho hloubku stromu. Přesněji řečeno, šířka stromu nepřesahuje šířku cesty grafu , která je maximálně o jednu menší než hloubka jeho stromu [11] [13] .

Počítat nezletilé

Menší část grafu G je další graf vytvořený z podgrafu G stažením některých hran. Hloubka stromu je u minorů monotónní — každý moll grafu G má hloubku stromu, která nepřesahuje hloubku stromu samotného grafu G [14] . Podle Robertsonova-Seymourova teorému má tedy množina grafů s hloubkou stromu nepřesahující d konečný počet zakázaných minorů pro jakékoli pevné d .

Je-li C třída grafů uzavřená pod formací minor, pak grafy v C mají hloubku stromu právě tehdy, když C nezahrnuje všechny cesty [15] .

Vygenerované podgrafy

Hloubka stromu má úzký vztah k teorii generovaných podgrafů grafu. Ve třídě grafů s hloubkou stromu nejvýše d (pro jakékoli pevné přirozené d ) je vlastnost generovaného podgrafu dobře kvazi-uspořádaná [16] . Hlavní myšlenkou důkazu, že toto spojení je zcela kvazi-uspořádané, je použití indukce na d . Lesy o výšce d lze interpretovat jako posloupnost lesů o výšce d  − 1 (vzniklé vyvrácením stromů o výšce d ) a Higmanovo lemma lze použít k prokázání, že tyto sekvence jsou kvazi-uspořádané.

Z dobře kvazi-uspořádání vyplývá, že jakákoliv vlastnost grafu, která je v generovaných podgrafech monotónní, má konečný počet zakázaných generovaných podgrafů, a proto ji lze kontrolovat v polynomiálním čase na grafech s ohraničenou hloubkou stromu. Grafy s hloubkou stromu nejvýše d mají samy o sobě konečný počet zakázaných podgrafů. Nexetril a Ossona de Mendez [17] ukázali 14 zakázaných podgrafů pro grafy se šířkou stromu tři nebo menší (s odkazem na dizertační práce Zdeňka Dvořáka z roku 2007).

Je-li C třídou grafů s ohraničenou degenerací , mají grafy v C omezenou šířku stromu právě tehdy, když existuje cesta, která se nemůže objevit jako vygenerovaný podgraf v C [15] .

Obtížnost

Určení hloubky stromu je složitý výpočetní problém - odpovídající rozpoznávací problém je NP-úplný [18] . Problém zůstává NP-úplný pro bipartitní grafy [1] , stejně jako pro akordické grafy [19] .

Pozitivní je, že hloubku stromu lze vypočítat v polynomiálním čase pro intervalové grafy [20] , stejně jako pro permutační grafy, lichoběžníkové grafy, kruhové obloukové grafy, cyklické permutační grafy a kosrovnatelné grafy ohraničených rozměrů [21 ] . U neorientovaných stromů lze hloubku stromu vypočítat v lineárním čase [22] [23] .

Bodlender, Gilbert, Hufsteinsson a Klox [11] navrhli aproximační algoritmus pro nalezení hloubky stromu s aproximačním koeficientem . Algoritmus je založen na skutečnosti, že hloubka stromu logaritmicky závisí na šířce stromu grafu.

Vzhledem k tomu, že hloubka stromu je monotónní v menších částech grafu, problém jejího nalezení je pevně-parametricky řešitelný — existuje algoritmus pro výpočet hloubky stromu, který pracuje v čase , kde d je hloubka daného grafu a n je počet vrcholů. Pro jakoukoli pevnou hodnotu d lze tedy problém kontroly, zda je hloubka stromu větší než d , vyřešit v polynomiálním čase . Přesněji řečeno, závislost na n v tomto algoritmu může být lineární následujícím způsobem: vytvoříme hloubkový vyhledávací strom a zkontrolujeme, zda je hloubka stromu větší než 2 d nebo ne. Pokud je více, hloubka stromu je větší než d a problém je vyřešen. Pokud tomu tak není, lze k rozložení stromu použít mělké vytváření vyhledávacího stromu a pro výpočet hloubky v lineárním čase lze použít standardní techniku ​​dynamického programování pro ohraničené grafy šířky stromu [24] . Dřívější Bodlander, Deogan, Jensen a Klox [1] navrhli sofistikovanější algoritmus řešení v lineárním čase založený na planaritě eliminovaných nezletilých v hloubkovém vyhledávání . Pro vylepšený parametrický algoritmus viz Reidl, Rossmanite, Villamil a Sikdar [25] .

Je možné přesně vypočítat hloubku stromu pro grafy, jejichž hodnota hloubky může být velká v čase O ( c n ) s konstantou c o něco menší než 2. [26]

Poznámky

  1. ↑ 1 2 3 Bodlaender et al, 1998 .
  2. ↑ Rossman, 2008 .
  3. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 116.
  4. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 115, definice 6.1.
  5. ↑ David Eppstein. Parametry grafu a kliky v supergrafech. — 2012 (15. listopadu). Archivováno z originálu 9. ledna 2014. .
  6. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 117, Lemma 6.1.
  7. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 125–128, oddíl 6.5, "Vycentrované barvy".
  8. ↑ Gruber a Holzer 2008 , str. Věta 5.
  9. ↑ Hunter, 2011 , Hlavní věta.
  10. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 117, Formule 6.2.
  11. ↑ 1 2 3 Bodlaender et al, 1995 .
  12. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 124, důsledek 6.1.
  13. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 123.
  14. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 117, Lemma 6.2.
  15. ↑ 1 2 Nešetřil, Ossona de Mendez, 2012 , str. 122, Návrh 6.4.
  16. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 137, Lemma 6.13.
  17. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 138. Obrázek 6.6 na str. 139.
  18. ↑ Pothen, 1988 .
  19. ↑ Dereniowski, Nadolski, 2006 .
  20. ↑ Aspvall, Heggernes, 1994 .
  21. ↑ Deogun et al, 1999 .
  22. ↑ Iyer a kol., 1988 .
  23. ↑ Schaffer, 1989 .
  24. ↑ Nešetřil, Ossona de Mendez, 2012 , str. 138.
  25. ↑ Reidl et al, 2014 .
  26. ↑ Fomin et al, 2013 .

Literatura