Základ cyklu

Základem cyklu neorientovaného grafu  je množina jednoduchých cyklů , které tvoří základ prostoru cyklu grafu. Jedná se tedy o minimální sadu cyklů, která umožňuje reprezentovat jakýkoli Eulerův podgraf jako symetrický rozdíl základních cyklů.

Základní základ cyklů lze vytvořit z libovolného kostry kosterního lesa daného grafu výběrem cyklů, které mají právě jednu hranu, která ke stromu nepatří. Také, pokud okrajům grafu přiřadíme kladné váhy, lze základnu minimálního váhového cyklu vytvořit v polynomiálním čase .

V rovinných grafech tvoří množina cyklů ohraničených ploch (tj. cyklů-hranic ohraničených ploch - jedna, vnější, nekonečná plocha) grafu vloženého do roviny základ cyklů. Základ cyklu rovinného grafu s minimální váhou odpovídá Gomory-Hu stromu grafu .

Definice

Kostra daného grafu má stejnou množinu vrcholů jako ona sama , ale možná méně hran. O grafu nebo o jednom z jeho podgrafů se říká, že je Eulerův , pokud má každý z jeho vrcholů sudý stupeň (to znamená počet hran, které vrchol dopadají). Jakýkoli jednoduchý cyklus v grafu je Eulerův podgraf, ale mohou existovat i jiné Eulerovy podgrafy. Prostor cyklu grafu je množina jeho Eulerových podgrafů. Tvoří vektorový prostor nad konečným polem dvou prvků. Vektorové sčítání odpovídá symetrickému rozdílu dvou nebo více podgrafů, který tvoří další podgraf, skládající se z hran, které se v argumentech operace symetrické diference vyskytují lichý počet [1] .

Báze cyklu je základem vektorového prostoru a každý základový vektor odpovídá jednoduchému cyklu. Základ se skládá ze sady cyklů, které lze zkombinovat za účelem získání libovolného Eulerova podgrafu pomocí symetrického rozdílu a tato sada cyklů je minimální sadou, která má specifikovanou vlastnost. Libovolná báze cyklu daného grafu má stejný počet základních prvků a tento počet se rovná rozměru prostoru cyklu. Toto číslo se nazývá řada vrstevnic nebo 'cyklomatické číslo grafu a je rovno , kde  je počet hran grafu,  je počet vrcholů a  je počet spojených komponent [2] .

Speciální základny cyklu

Byly studovány některé speciální typy bází cyklů, mezi nimi základní báze cyklů, slabé báze základních cyklů, řídké (nebo 2-) báze cyklů a celé báze cyklů [3] .

Generované cykly

Každý graf má základ cyklu, ve kterém je každý cyklus generovaným cyklem . 3-vrcholově spojený graf má vždy základ skládající se z periferních cyklů , cyklů, jejichž odstranění nevede k rozdělení na odpojené části [4] [5] . V každém grafu, který není získán přidáním hrany do cyklu, musí být obvodový cyklus generovaným cyklem.

Základní cykly

Pokud  je kostra nebo kostra daného grafu a  hrana nepatřící do , pak základní cyklus definovaný hranou  je jednoduchý cyklus skládající se z , spolu s cestou v , spojující koncové vrcholy . Existuje přesně jeden základní cyklus, přesně jeden pro každou hranu ne v . Každý z nich je lineárně nezávislý na zbytku, protože obsahuje hranu , která nepatří do žádného jiného základního cyklu. Fundamentální cykly tedy tvoří základ prostoru cyklů [2] . Takto konstruovaná báze cyklu se nazývá báze základního cyklu nebo přísně fundamentální báze cyklu [3] .

Je možné definovat základní základ cyklů, aniž bychom se spoléhali na strom, pro který jsou cykly základní. Pokud a pouze tehdy, pokud existuje strom, pro který je daná báze cyklu základní, pokud jakýkoli cyklus obsahuje hranu, která není zahrnuta v žádném jiném základním cyklu. Z toho vyplývá, že množina cyklů je základní bází cyklů právě tehdy, má-li stejnou vlastnost a správný počet cyklů v bázi [6] .

Slabě fundamentální cykly

Báze cyklu je považována za slabě fundamentální , pokud lze její cykly uspořádat tak, že každý cyklus obsahuje hranu, která nepatří žádnému předchozímu cyklu. Fundamentální báze cyklů je automaticky slabě fundamentální (pro jakékoliv řazení cyklů) [7] . Pokud je jakákoli báze cyklu grafu slabě fundamentální, totéž platí pro jakýkoli menší graf . Na základě této vlastnosti lze třídu grafů (a multigrafů ), pro kterou je jakýkoli základní cyklus slabě fundamentální, popsat pomocí pěti zakázaných minoritních skupin - čtvercového pyramidového  grafu , multigrafu vytvořeného zdvojením všech hran cyklu se čtyřmi vrcholy. , dva multigrafy vzniklé zdvojením dvojice hran čtyřstěnu a multigraf vzniklý ztrojnásobením hran trojúhelníku [8] .

Obličejové cykly

Pokud je připojený konečný rovinný graf vnořen do roviny, je každá plocha vnoření obklopena cyklem hran. Jedna plocha bude neomezená (obsahuje body libovolně vzdálené od vrcholů grafu), ostatní plochy budou omezené. Podle Eulerova vzorce existují přesně ohraničené plochy.

Symetrický rozdíl libovolné sady cyklů ploch je hranicí odpovídající sady ploch a různé sady ohraničených ploch mají různé hranice, takže stejnou sadu nelze reprezentovat jako symetrický rozdíl cyklů více než jedním způsobem. To znamená, že čelní cykly jsou lineárně nezávislé. Protože tato lineárně nezávislá množina má dostatečně velkou velikost, tvoří nutně základ cyklů [9] . Tato báze je vždy slabě fundamentální cyklickou bází a je fundamentální tehdy a pouze tehdy, když je vnoření grafu vnější rovina .

Pro grafy správně zasazené do jiných ploch tak, že všechny plochy jsou topologicky disky, obecně nemusí nutně existovat základ cyklu sestávající pouze z cyklů ploch. Obličejové cykly těchto vložení poskytují vhodnou podmnožinu všech Eulerových podgrafů. Skupina homologie daného povrchu popisuje Eulerovy podgrafy, které nelze reprezentovat jako hranice množiny ploch. MacLaneovo kritérium rovinnosti využívá tuto myšlenku k popisu rovinných grafů pomocí základen cyklů – konečný neorientovaný graf je rovinný právě tehdy, má-li řídkou základnu cyklu (nebo 2 základny ) [3] , základ, ve kterém každá hrana graf náleží maximálně dvěma základním cyklům. V rovinném grafu je základna cyklů tvořená množinou ohraničených ploch nutně řídká a naopak řídká základna cyklů libovolného grafu nutně tvoří množinu ohraničených ploch rovinného vnoření grafu [9] [ 10] .

Základy celých čísel

Pomocí teorie homologie lze prostor cyklu grafu interpretovat jako homologní skupinu jednoduchého komplexu s bodem pro každý vrchol grafu a úsečkou pro každou hranu grafu. Tato konstrukce může být zobecněna na homologní skupinu na libovolném kruhu . Důležitým speciálním případem je kruh celých čísel , pro který je homologní grupa volná abelovská grupa , podgrupa volné abelovské grupy generovaná (libovolně orientovanými) hranami grafu. Prvky jsou tedy popisky hran grafu čísly s vlastností, že v každém vrcholu je součet popisků příchozích oblouků roven součtu popisků odchozích oblouků. Skupinová operace je přidání vektorů štítků. Celočíselná báze cyklů  je množina jednoduchých cyklů, které generují tuto skupinu [3] .

Minimální hmotnost

Pokud jsou okrajům grafu dány nějaké váhy, lze váhu podgrafu vypočítat jako součet vah hran. Základem prostoru cyklů s nejmenší váhou bude nutně základ cyklů - podle Veblenovy věty [11] lze každý Eulerův podgraf, který sám o sobě není jednoduchým cyklem, rozložit na několik jednoduchých cyklů, které budou mít nutně méně hmotnost.

Podle standardních vlastností vektorových prostorových základen a matroidů základna cyklu o minimální hmotnosti nejen minimalizuje součet vah cyklu základny, ale také minimalizuje jakoukoli jinou monotónní kombinaci vah cyklu. Minimalizuje například váhu nejdelšího základního cyklu [12] .

Polynomiální časové algoritmy

V jakémkoli vektorovém prostoru a obecněji v jakémkoli matroidu lze nalézt základ s minimální váhou pomocí zištného algoritmu , který zvažuje možné prvky základny jeden po druhém v seřazeném pořadí jejich vah a zahrnuje prvek do základu, pokud je lineárně nezávislý na těch vybraných až do tohoto prvku. Test lineární nezávislosti lze provést pomocí Gaussovy eliminace . Neorientovaný graf však může mít exponenciálně mnoho jednoduchých cyklů, takže získání a kontrola všech těchto cyklů se stává nemožným úkolem.

Horton ( 1987 ) navrhl první polynomiální časový algoritmus pro nalezení minimálního váhového základu v grafech, jejichž všechny váhy jsou větší než nula. Jeho algoritmus používá stejný přístup get-and-test, ale počet smyček, na které se dívá, je omezen na malou množinu –  tyto smyčky se nazývají Hortonovy smyčky . Hortonův cyklus je základním cyklem stromu nejkratší cesty daného grafu. Existuje n různých stromů nejkratších cest (jeden pro každý kořenový uzel) a každý strom má nejvýše m základních cyklů, což udává celkový počet Hortonových cyklů. Jak ukázal Horton, každý cyklus na bázi cyklu minimální hmotnosti je Hortonův cyklus [13] .

Pokud použijeme Dijkstrův algoritmus k nalezení každého stromu nejkratší cesty a pak použijeme Gaussovu eliminaci pro testovací kroky základního chamtivého algoritmu, dostaneme polynomiální časový algoritmus pro základ minimálního váhového cyklu.

Následné studie přinesly vylepšené algoritmy pro tento problém [14] [15] [16] [17] , snižující časovou složitost v nejhorším případě pro nalezení základny cyklů s minimální váhou na , kde  je počet hran grafu a  je počet vrcholů [18] .

NP-obtížnost

Hledání základního základu minimální možné váhy úzce souvisí s problémem nalezení kostry, která minimalizuje průměrné párové vzdálenosti – oba problémy jsou NP-těžké [19] . Hledání slabé fundamentální báze s minimální váhou je také NP -hard [7] a aproximace je MAXSNP-hard [20] . Pokud jsou povoleny záporné váhy a cykly se zápornou váhou, pak je nalezení základny cyklu s minimální váhou (bez omezení) také NP-obtížné, protože ji lze použít k nalezení hamiltonovského cyklu  - pokud je graf hamiltonovský, a nastavit vše hrany na váhu −1, bude báze cyklů o minimální hmotnosti obsahovat alespoň jeden hamiltonovský cyklus.

V rovinných grafech

Základ minimálních váhových cyklů pro rovinný graf se nemusí nutně shodovat se základnou tvořenou hranicemi ploch – může obsahovat cykly, které plochám neodpovídají, a také některé plochy mohou jako cykly chybět v základně s minimální hmotnost. Existuje však minimální základ cyklu hmotnosti, ve kterém se žádné dva cykly vzájemně neprotínají – pro jakékoli dva cykly v této základně buď cykly uzavírají nesouvislé podmnožiny ploch, nebo jeden ze dvou cyklů uzavírá druhý. Tato množina cyklů odpovídá v duálním grafu daného rovinného grafu množině řezů , které tvoří Gomory–Hy strom duálního grafu, minimální váhový základ prostoru řezů [21] . Na základě této duality lze sestrojit explicitní vyjádření minimálního váhového cyklu pro rovinný graf v čase [22] .

Aplikace

Cyklistické základny se používají k řešení pravidelných problémů s plánováním, jako je problém plánování pro systémy veřejné dopravy. V tomto problému základní cykly odpovídají celočíselným programovacím proměnným použitým k řešení problému [23] .

V teoriích strukturální tuhosti a kinematice se základy cyklů používají ke konstrukci systému neredundantního systému rovnic, který lze řešit za účelem kontroly tuhosti konstrukce. V tomto problému vede základ cyklů minimální nebo blízké minimální hmotnosti k jednodušším soustavám rovnic [24] .

V distribuovaných výpočtech se k analýze počtu kroků požadovaných pro stabilizaci algoritmu používají báze smyček [25] .

V bioinformatice se k určení haplotypových informací z genotypových dat používají báze cyklu [26] . Základ cyklu se také používá k analýze terciární struktury RNA [27] .

K rekonstrukci povrchu lze použít základ cyklu minimální váhy grafu nejbližších sousedů bodů odebraných z trojrozměrného povrchu [28] .

Poznámky

  1. ↑ Diestel, 2012 .
  2. ↑ 1 2 Gross, Yellen, 2005 .
  3. ↑ 1 2 3 4 Liebchen, Rizzi, 2007 .
  4. ↑ Diestel, 2012 , str. 32, 65.
  5. ↑ Tutte, 1963 . Viz zejména věta 2.5.
  6. ↑ Cribb, Ringeisen, Shier, 1981 .
  7. ↑ 12. Rizzi , 2009 .
  8. ↑ Hartvigsen, Zemel, 1989 .
  9. ↑ 1 2 Diestel, 2012 , s. 105-106.
  10. ↑ Mac Lane, 1937 .
  11. ↑ Veblen, 1912 .
  12. ↑ Chickering, Geiger, Heckerman, 1995 .
  13. ↑ Horton, 1987 .
  14. ↑ Berger, Gritzmann, de Vries, 2004 .
  15. ↑ Mehlhorn, Michail, 2006 .
  16. ↑ Kavitha, Mehlhorn, Michail, Paluch, 2008 .
  17. ↑ Kavitha, Liebchen, Mehlhorn, Michail, Rizzi, Ueckerdt, Zweig, 2009 .
  18. ↑ Amaldi, Iuliano, Rizzi, 2010 .
  19. ↑ Deo, Prabhu, Krishnamoorthy, 1982 .
  20. ↑ Galbiati, Amaldi, 2004 .
  21. ↑ Hartvigsen, Mardon, 1994 .
  22. ↑ Borradaile, Sankowski, Wulff-Nilsen, 2010 .
  23. ↑ Liebchen, 2007 .
  24. ↑ Cassell, De Henderson, Kaveh, 1974 .
  25. ↑ Boulinier, Petit, padouch, 2004 .
  26. ↑ Aguiar, Istrail, 2012 .
  27. ↑ Lemieux, major, 2006 .
  28. ↑ Gotsman, Kaligosi, Mehlhorn, Michail, Pyrga, 2007 .

Literatura