Rozklad ucha

V teorii grafů je ucho neorientovaného grafu G cesta P , jejíž dva koncové body se mohou shodovat, ale jinak není povoleno žádné opakování vrcholů nebo hran, takže jakýkoli vnitřní bod P má na cestě stupeň dva. Ušní rozklad neorientovaného grafu G je rozdělení jeho okraje do posloupnosti uší tak, že koncové body každého ucha patří k dříve vybraným uším v posloupnosti, zatímco vnitřní vrcholy každého ucha nepatří do předchozího. uši. Ve většině případů by také první ucho v sekvenci mělo být smyčkou. Otevřený nebo vlastní rozklad ucha je rozklad ucha, ve kterém jsou dva koncové body každého ucha odlišné od prvního.

Ušní rozklad lze použít k popisu některých důležitých tříd grafů a jako součást efektivních grafových algoritmů . Rozklad ucha lze zobecnit na matroidy .

Popis tříd grafů

Některé důležité třídy grafů lze popsat určitými typy ušních rozkladů.

Konektivita grafu

Graf je vertex-k-spojený , pokud odstraněním pouze ( k  − 1) vrcholů zůstane podgraf připojen, a k-edge-connected , pokud odstranění jakýchkoli ( k  − 1) hran ponechá podgraf připojený.

Následující výsledek je způsoben Hasler Whitney [1] :

Graf s vrcholem je 2-souvislý právě tehdy, když má otevřený ušní rozklad.

Následující výsledek je zásluhou Herberta Robinsona [2] :

Graf je 2-hranný, právě když má ušní rozklad.

V obou případech se počet uší musí rovnat obrysové hodnosti grafu. Robbins použil ušní rozklad 2-hranově spojených grafů jako prostředek k prokázání Robbinsova teorému , že jde přesně o grafy, kterým lze dát silně souvislou orientaci. Vzhledem k tomu, že Whitney a Robinson jako první prozkoumali ušní rozklad, je někdy označován jako Whitney-Robinsonova syntéza [3] .

Neoddělující se klasový rozklad je otevřený klasový rozklad takový, že pro každý vrchol v kromě jednoho má v sousední vrchol, který se objeví později než v při rozkladu . Tento typ rozkladu lze použít ke zobecnění Whitneyho výsledku:

Graf c je 3-vrcholově propojený právě tehdy, když G má neoddělující ušní rozklad.

Pokud takový rozklad existuje, může být zvolen s ohledem na hranu uv G tak , že u patří do prvního ucha, v je nový vrchol v posledním uchu s více než jednou hranou a uv je ucho skládající se z jednoho ucha. okraj. Tento výsledek poprvé výslovně uvedli Cheryan a Maheshwari [4] , ale jak píše Schmidt [5] , je ekvivalentní výsledku Ph.D. 1971 disertační práce Lee Mondshein. Struktury úzce související s neoddělujícími se ušními rozklady maximálních rovinných grafů, nazývané kanonická uspořádání, jsou také standardním vizualizérem grafů .

Silná konektivita orientovaných grafů

Výše uvedené definice lze také rozšířit na orientované grafy . Ucho je pak nasměrovaná cesta, ve které mají všechny vnitřní vrcholy indegree a outdegree rovné 1. Orientovaný graf je silně propojený , pokud obsahuje nasměrovanou cestu z libovolného vrcholu do kteréhokoli jiného vrcholu. Pak platí následující věta:

Orientovaný graf je silně propojený právě tehdy, když má ušní rozklad.

Podobně je orientovaný graf dvojitě propojen , pokud pro libovolné dva vrcholy existuje jednoduchý cyklus obsahující oba vrcholy. Pak

Orientovaný graf je dvojitě propojený právě tehdy, když má otevřený ušní rozklad.

Faktorově kritické grafy

Rozklad ucha je lichý , pokud má každé ucho lichý počet hran. Faktorově kritický graf je graf s lichým počtem vrcholů, takže když je z grafu odstraněn jakýkoli vrchol v , zbývající vrcholy mají dokonalou shodu . Laszlo Lovas [6] zjistil, že:

Graf G je faktorově kritický graf právě tehdy, když má G lichý ušní rozklad.

Obecněji řečeno, Frankův výsledek [7] umožňuje najít pro libovolný graf G klasový rozklad s nejmenším počtem sudých uší.

Paralelně-sekvenční grafy

Dekompozice stromového ucha je vlastní klasová dekompozice, ve které je první ucho jednou hranou a pro každé následující ucho existuje jedinečné ucho , , ve kterém oba koncové body leží na [8] . Dekompozice vnořeného ucha je dekompozice stromového ucha tak, že v každém uchu sada párů koncových bodů jiných uší ležících uvnitř tvoří sadu vnořených intervalů. Paralelně sériový graf je graf se dvěma odlišnými konci s a t , který lze vytvořit rekurzivně kombinací menších paralelně sériových grafů jedním ze dvou způsobů – sériovým zapojením (jeden konec jednoho z grafů identifikujeme s jedním koncem druhý graf a druhý dva konce obou grafů se stanou konci sjednocení) a paralelní spojení (identifikujeme obě dvojice vývodů obou menších grafů).

Následující výsledek je zásluhou Davida Epsteina [9] :

Vrcholový-2-spojený graf je paralelní-sériový graf právě tehdy, když má vnořený klasový rozklad.

Kromě toho musí být vnořen jakýkoli rozklad 2-vrcholového paralelně sériového grafu s otevřeným uchem. Výsledek lze zobecnit na paralelně sekvenční grafy, které nejsou spojeny se 2 vrcholy pomocí rozkladu otevřeného ucha, který začíná na cestě mezi dvěma konci.

Matroidy

Pojem rozklad ucha lze zobecnit z grafů na matroidy . Ušní rozklad matroidu je definován jako sekvence matroidních cyklů, která má dvě vlastnosti:

Při aplikaci na matroid grafu grafu G je tato definice ušního rozkladu stejná jako definice správného rozkladu G – nesprávné rozklady jsou vyloučeny požadavkem, aby každý cyklus zahrnoval alespoň jednu hranu patřící na předchozí cykly. Pomocí této definice lze matroid definovat jako kvocientově kritický, pokud má ušní rozklad, ve kterém má každý cyklus v sekvenci lichý počet nových prvků [10] .

Algoritmy

Ušní rozklad grafů spojených 2 hranami a otevřený rozklad grafů spojených 2 vrcholy lze nalézt pomocí zištných algoritmů , které najdou každé ucho jedno po druhém. Schmidt [11] navrhl jednoduchý chamtivý algoritmus, který současně počítá expanzi ucha, expanzi otevřeného ucha, číslování st a orientaci st v lineárním čase (pokud existují) . Tento přístup je založen na výpočtu speciálního druhu ušního rozkladu, řetězového rozkladu s pravidlem generování jedné cesty. Schmidt ukázal [5] , že v lineárním čase lze vybudovat neseparační ušní rozklad.

Lovas [12] , Maon, Shiber a Vyshkin [13] a Miller a Ramachandran [14] poskytli účinné paralelní algoritmy pro konstrukci různých typů ušních rozkladů. Například pro nalezení ušního rozkladu 2-hranného grafu prochází algoritmus Maona, Schiebera a Wyshkina [13] následujícími kroky:

  1. Najde se kostra daného grafu a vybere se kořen stromu.
  2. Pro každou hranu uv , která není součástí stromu, určete vzdálenost mezi kořenem a nejmenším společným předkem uav .
  3. Pro každou hranu uv , která je součástí stromu, najděte odpovídající "hlavní hranu", hranu wx , která není ze stromu, takže cyklus vytvořený přidáním wx do stromu prochází uv a takovou, že mezi všemi hranami w a x má nejnižšího předka co nejblíže kořenu.
  4. Pro každou mimostromovou hranu tvoříme ucho, skládající se z této hrany a hran stromu, pro které je tato hrana hlavní. Uši uspořádáme podle vzdáleností hlavního okraje od kořene.

Tento algoritmus lze použít jako postup pro jiné problémy, včetně kontroly konektivity, rozpoznávání sérioparalelních grafů a konstrukce st -číslování grafů (důležitý postup pro kontrolu planarity ).

Ušní rozklad matroidu s dalším omezením, že každé ucho obsahuje stejný pevný počet matroidních prvků, lze nalézt v polynomiálním čase , pokud pro matroid existuje orákulum nezávislosti [15] .

Poznámky

  1. ↑ Whitney, 1932 .
  2. ↑ Robbins, 1939 .
  3. ↑ Gross, Yellen, 2006 .
  4. ↑ Cheriyan, Maheshwari, 1988 .
  5. ↑ 12 Schmidt, 2013b .
  6. ↑ Lovász, 1972 .
  7. ↑ Frank, 1993 .
  8. ↑ Huller, 1989 .
  9. ↑ Eppstein, 1992 .
  10. ↑ Szegedy, Szegedy, 2006 .
  11. ↑ Schmidt, 2013a .
  12. ↑ Lovász, 1985 .
  13. ↑ 1 2 Maon, Schieber, Vishkin, 1986 .
  14. ↑ Miller, Ramachandran, 1986 .
  15. ↑ Collard, Hellerstein, 1996 .

Literatura