Ušní rozklad - Ear decomposition

Příklad rozkladu ucha grafu obsahujícího 3 uši.

v teorie grafů, an ucho z neorientovaný graf G je cesta P kde se dva koncové body cesty mohou shodovat, ale kde jinak není povoleno opakování hran nebo vrcholů, tak každý vnitřní vrchol P má stupeň dva dovnitř G. An rozklad ucha neorientovaného grafu G je rozdělit jeho sady okrajů do sekvence uší, takže jeden nebo dva koncové body každého ucha patří dřívějším uším v sekvenci a takové, že vnitřní vrcholy každého ucha nepatří žádnému dřívějšímu uchu. Navíc ve většině případů musí být první ucho v sekvenci cyklus. An rozklad otevřeného ucha nebo a správný rozklad uší je ušní rozklad, ve kterém jsou dva koncové body každého ucha po prvním odlišné od sebe.

Ušní dekompozice lze použít k charakterizaci několika důležitých tříd grafů a jako součást efektivního grafové algoritmy. Mohou být také generalizovány z grafů do matroidy.

Charakterizace tříd grafů

Několik důležitých tříd grafů lze charakterizovat jako grafy, které mají určité typy ušních rozkladů.

Připojení grafu

Graf je k-vertex-connected pokud odstranění jakéhokoli (k - 1) vrcholy opouštějí připojený podgraf a k- připojený k okraji pokud odstranění jakéhokoli (k - 1) hrany zanechávají připojený podgraf.

Následující výsledek je způsoben Hassler Whitney (1932 ):

Graf

{ displaystyle G = (V, E)}

s

{ displaystyle | E | geq 2}

je spojen se dvěma vrcholy právě tehdy, má-li rozklad otevřeného ucha.

Následující výsledek je způsoben Herbert Robbins (1939 ):

Graf je spojen dvěma okraji, právě když má ušní rozklad.

V obou případech se počet uší nutně rovná hodnost obvodu daného grafu. Robbins představil ušní rozklad grafů propojených dvěma okraji jako nástroj pro prokázání Robbinsova věta, že se jedná přesně o grafy, kterým lze dát a silně propojený orientace. Kvůli průkopnické práci Whitneyho a Robbinse o rozkladu uší se někdy rozkladu uší říká Syntéza Whitney – Robbins (Gross & Yellen 2006 ).

A nerozdělovací ušní rozklad je rozklad otevřeného ucha takový, že pro každý vrchol proti až na jednu výjimku, proti má souseda, jehož první výskyt v rozkladu je v pozdějším uchu než první výskyt v proti. Tento typ rozkladu uší lze použít ke zobecnění výsledku Whitney:

Graf

{ displaystyle G = (V, E)}

s

{ displaystyle | V | geq 2}

je spojen se 3 vrcholy právě tehdy G má nerozdělovací ušní rozklad.

Pokud takový rozklad existuje, lze jej zvolit s ohledem na konkrétní hranu uv z G takovým způsobem, že u je v prvním uchu, proti je nový vrchol v posledním uchu s více než jednou hranou a uv je ucho s jedním okrajem. Tento výsledek poprvé výslovně uvedl Cheriyan & Maheshwari (1988), ale jako Schmidt (2013b) popisuje, že je ekvivalentní výsledku v roce 1971 Ph.D. práce Lee Mondsheina. Struktury úzce související s nerozdělitelnými ušními rozklady maximálních rovinných grafů, nazývané kanonické uspořádání, jsou také standardním nástrojem v kreslení grafu.

Silná konektivita směrovaných grafů

Výše uvedené definice lze také použít řízené grafy. An ucho by pak byla směrovaná cesta, kde mají všechny vnitřní vrcholy nezávislý a překonat rovná se 1. Orientovaný graf je silně propojený pokud obsahuje směrovanou cestu z každého vrcholu do všech ostatních vrcholů. Pak máme následující větu (Bang-Jensen a Gutin 2007, Věta 7.2.2):

Směrovaný graf je silně spojen právě tehdy, má-li ušní rozklad.

Faktorově kritické grafy

Ušní rozklad je zvláštní pokud každé jeho ucho používá lichý počet hran. A faktorově kritický graf je graf s lichým počtem vrcholů, takovým, že pro každý vrchol proti, pokud proti je odstraněn z grafu, pak zbývající vrcholy mají a perfektní shoda. László Lovász (1972 ) zjistil, že:

Graf G je faktorově kritický právě tehdy G má zvláštní rozklad ucha.

Obecněji řečeno, výsledek Frank (1993) umožňuje najít v jakémkoli grafu G rozklad uší s nejméně rovnoměrnými ušima.

Sériově paralelní grafy

A strom rozklad ucha je správný rozklad ucha, při kterém je první ucho jedním okrajem a pro každé následující ucho ${ displaystyle P_ {i}}$ , je tam jediné ucho ${ displaystyle P_ {j}}$ , ${ displaystyle i> j}$ , takže oba koncové body ${ displaystyle P_ {i}}$ ležet na ${ displaystyle P_ {j}}$ (Khuller 1989 ). A vnořené ušní rozklad je stromový ušní rozklad tak, že v každém uchu ${ displaystyle P_ {j}}$ , sada párů koncových bodů jiných uší ${ displaystyle P_ {i}}$ které leží uvnitř ${ displaystyle P_ {j}}$ tvoří soubor vnořených intervalů. A sériově paralelní graf je graf se dvěma určenými terminály s a t které lze rekurzivně vytvořit kombinací menších sériově paralelních grafů jedním ze dvou způsobů: složení řady (identifikace jedné svorky z jednoho menšího grafu s jednou svorkou z druhého menšího grafu a ponechání dalších dvou svorek jako svorek kombinovaného grafu ) a paralelní složení (identifikace obou párů terminálů ze dvou menších grafů).

Následující výsledek je způsoben David Eppstein (1992 ):

Graf propojený se 2 vrcholy je sériově paralelní právě tehdy, pokud má vnořený rozklad ucha.

Kromě toho musí být vnořený jakýkoli otevřený ucho rozkladu sériově paralelního grafu připojeného ke 2 vrcholům. Výsledek lze rozšířit na sériově paralelní grafy, které nejsou spojeny se dvěma vrcholy, pomocí dekompozic otevřeného ucha, které začínají cestou mezi dvěma terminály.

Matroidy

Koncept rozkladu uší lze rozšířit z grafů na matroidy. Dekompozice ucha matroidu je definována jako posloupnost obvodů matroidu se dvěma vlastnostmi:

každý obvod v sekvenci má neprázdnou křižovatku s předchozími obvody a
každý obvod v sekvenci zůstává okruhem, i když jsou všechny předchozí okruhy v sekvenci uzavřeny.

Při aplikaci na grafický matroid grafu G, tato definice rozkladu uší se shoduje s definicí správného rozkladu uší G: nesprávné rozklady jsou vyloučeny požadavkem, aby každý obvod obsahoval alespoň jednu hranu, která také patří k předchozím obvodům. Pomocí této definice lze matroid definovat jako faktorově kritický, pokud má rozklad ucha, ve kterém má každý obvod v sekvenci lichý počet nových prvků (Szegedy & Szegedy 2006 ).

Algoritmy

Na klasických počítačích lze ušní dekompozice grafů připojených ke dvěma hranám a otevřené ušní dekompozice grafů připojených ke dvěma vrcholům najít chamtivé algoritmy které najdou každé ucho po druhém. Jednoduchý chamtivý přístup, který současně počítá dekompozice ucha, dekompozice otevřeného ucha, číslování a orientace v lineárním čase (pokud existují), je uveden v Schmidt (2013a). Tento přístup je založen na výpočtu zvláštního pojmenovaného rozkladu uší řetězový rozklad jedním pravidlem generujícím cestu. Schmidt (2013b) ukazuje, že nerozdělovací ušní dekompozice mohou být také konstruovány v lineárním čase.

Lovász (1985), Maon, Schieber & Vishkin (1986), a Miller & Ramachandran (1986) za předpokladu, efektivní paralelní algoritmy pro konstrukci ušních rozkladů různých typů. Chcete-li například najít ušní rozklad grafu spojeného se dvěma okraji, algoritmus Maon, Schieber & Vishkin (1986) postupuje podle následujících kroků:

Najdi kostra daného grafu a vyberte kořen stromu.
Určete pro každou hranu uv to není část stromu, vzdálenost mezi kořenem a nejnižší společný předek z u a proti.
Pro každou hranu uv který je součástí stromu, najděte odpovídající „hlavní hranu“, nestromovou hranu šx tak, že cyklus vznikl sčítáním šx ke stromu prochází uv a takové, že mezi takovými okraji w a X mít nejnižšího společného předka, který je co nejblíže kořenu (s vazbami přerušenými identifikátory hran).
Vytvořte ucho pro každý okraj, který není stromem, skládající se z něj a okrajů stromu, pro které je pánem, a uspořádejte uši podle vzdálenosti jejich hlavních okrajů od kořene (se stejným pravidlem pro rozbíjení kravat).

Tyto algoritmy lze použít jako podprogramy pro další problémy, včetně testování připojení, rozpoznávání sériově paralelních grafů a konstrukce Svatý- číslování grafů (důležitý podprogram v testování rovinnosti ).

Dekompozice ucha daného matroidu s dodatečným omezením, že každé ucho obsahuje stejný fixní prvek matroidu, lze nalézt v polynomiální čas umožněn přístup k věštba nezávislosti pro matroid (Coullard & Hellerstein 1996 ).

Reference

Bang-Jensen, Jørgen; Gutin, Gregory (2007), „7.2 Ušní dekompozice“, Digrafy: Teorie, algoritmy a aplikace, Springer-Verlag, str. 349–352
Cheriyan, J .; Maheshwari, S. N. (1988), „Hledání neoddělujících se indukovaných cyklů a nezávislých stromů ve třech grafech“, Journal of Algorithms, 9 (4): 507–537, doi:10.1016/0196-6774(88)90015-6, PAN 0970192.
Coullard, Collette R.; Hellerstein, Lisa (1996), „Nezávislost a hlavní věty pro matroidy, s aplikací na teorii výpočetního učení“, Combinatorica, 16 (2): 189–208, doi:10.1007 / BF01844845, PAN 1401892.
Eppstein, D. (1992), "Paralelní rozpoznávání sériově paralelních grafů" (PDF), Informace a výpočet, 98 (1): 41–55, doi:10.1016 / 0890-5401 (92) 90041-D, PAN 1161075.
Frank, András (1993), „Konzervativní vážení a ušní rozklady grafů“, Combinatorica, 13 (1): 65–81, doi:10.1007 / BF01202790, PAN 1221177.
Gross, Jonathan L .; Yellen, Jay (2006), „Charakterizace silně orientovatelných grafů“, Teorie grafů a její aplikace, Diskrétní matematika a její aplikace (Boca Raton) (2. vydání), Chapman & Hall / CRC, Boca Raton, FL, str. 498–499, ISBN 978-1-58488-505-4, PAN 2181153.
Khuller, Samir (1989), „Ušní dekompozice“ (PDF), Novinky SIGACT, 20 (1): 128.
Lovász, László (1972), „Poznámka o faktorově kritických grafech“, Studia Sci. Matematika. Visel., 7: 279–280, PAN 0335371.
Lovász, László (1985), „Výpočet uší a větvení paralelně“, 26. výroční sympozium o základech informatiky, str. 464–467, doi:10.1109 / SFCS.1985.16.
Maon, Y .; Schieber, B .; Vishkin, U. (1986), „Parallel ear decomposition search (EDS) and ST-numbering in graphs“, Teoretická informatika, 47 (3): 277–298, doi:10.1016/0304-3975(86)90153-2, PAN 0882357.
Miller, G.; Ramachandran, V. (1986), Efektivní paralelní rozklad uší s aplikacemiNepublikovaný rukopis.
Robbins, H. E. (1939), „Věta o grafech s aplikací na problém řízení dopravy“ (PDF), Americký matematický měsíčník, 46: 281–283, doi:10.2307/2303897.
Schmidt, Jens M. (2013a), „Simple Test on 2-Vertex- and 2-Edge-Connectivity“, Dopisy o zpracování informací, 113 (7): 241–244, arXiv:1209.0700, doi:10.1016 / j.ipl.2013.01.016.
Schmidt, Jens M. (2013b), Sekvence Mondshein, arXiv:1311.0750, Bibcode:2013arXiv1311.0750S.
Schrijver, Alexander (2003), Kombinatorická optimalizace. Mnohostěn a účinnost. Sv. A, Springer-Verlag, ISBN 978-3-540-44389-6.
Szegedy, Balázs; Szegedy, Christian (2006), „Symplectic spaces and ear-decomposition of matroids“, Combinatorica, 26 (3): 353–377, doi:10.1007 / s00493-006-0020-3, PAN 2246153.
Whitney, H. (1932), „Nerozdělitelné a rovinné grafy“, Transakce Americké matematické společnosti, 34: 339–362, doi:10.1090 / S0002-9947-1932-1501641-2, JSTOR 1989545.