Prostor smyčky

Prostor cyklů neorientovaného grafu je lineární prostor nad polem sestávajícím z jeho Eulerových podgrafů. Dimenze tohoto prostoru se nazývá hodnost obrysu grafu. Z hlediska algebraické topologie je cyklický prostor první homologní skupinou grafu. $\mathbb {F} _{2}$

Definice

Teorie grafů

Překlenovací podgraf daného grafu je jeho podgraf takový, že množina vrcholů se shoduje s množinou vrcholů . Každý graf s hranami tedy obsahuje podgrafy, včetně sebe sama a prázdného grafu na množině vrcholů grafu . Rodina všech podgrafů tvořících okrajový prostor daného grafu. Graf se nazývá Euler , jestliže každý z jeho vrcholů je incidentní se sudým počtem hran (jinými slovy, stupeň kteréhokoli vrcholu grafu je sudý). Rodina všech Eulerových podgrafů tvoří cyklický prostor daného grafu [1] [2] . $G$ $S$ $S$ $G$ $m$ $2^{m}$ $G$ $G$ $G$

Algebra

Okrajový prostor libovolného grafu je uzavřený vzhledem k operacím teorie množin, takže tvoří Booleovu algebru [3] . Cyklické prostory mají také algebraickou strukturu: spojení nebo průnik Eulerových podgrafů nemusí být Euler, ale jejich symetrický rozdíl bude [1] . Je to dáno tím, že symetrický rozdíl množin se sudou množinou prvků ( okolí vrcholu v prvním a druhém podgrafu) obsahuje i sudou množinu prvků.

Rodinu množin uzavřenou s ohledem na symetrický rozdíl lze algebraicky popsat vektorovým prostorem nad dvouprvkovým konečným polem [4] . Toto pole se skládá ze dvou prvků, a , a sčítání a násobení odpovídají logickým operacím výlučného „nebo“ a spojky (sčítání a násobení modulo 2 ). V cyklickém prostoru budou vektory Eulerovými podgrafy, jejich sčítání odpovídá symetrickému rozdílu, násobení skalárem je mapa identity a násobení skalárem změní jakýkoli podgraf na prázdný, což odpovídá nulovému vektoru cyklického prostor. $\mathbb {F} _{2}$ $0$ $jeden$ $jeden$ $0$

Okrajový prostor je také vektorový prostor s operací symetrického rozdílu jako sčítání. Cyklický prostor a prostor řezů [5] jsou navzájem ortogonálními doplňky uvnitř prostoru hran. To znamená, že množina hran je řezem tehdy a jen tehdy, když jakýkoli Eulerův podgraf obsahuje sudý počet hran z a naopak množina je Eulerovým podgrafem právě tehdy, když jakýkoli řez obsahuje sudý počet hran z [2] . Přestože jsou tyto prostory navzájem ortogonálními doplňky, mohou mít netriviální průnik. Obecně platí, že graf má neprázdný Eulerův řez tehdy a jen tehdy, když je počet jeho překlenovacích lesů sudý [6] . $\mathbb {F} _{2}$ $S$ $S$ $S$ $S$ $G$

Topologie

Na neorientovaný graf lze pohlížet jako na simpliciální komplex , jehož vrcholy jsou nula-rozměrné simplelice a jehož hrany jsou jednorozměrné simplice [7] . Řetězový komplex takového topologického prostoru se skládá z jeho okrajových a vertexových prostorů spojených hraničním operátorem, který mapuje libovolný podgraf (prvek okrajového prostoru) na jeho množinu vrcholů lichého stupně (prvek vertexového prostoru). Skupina homologie se skládá z prvků okrajového prostoru, které jsou hraničním operátorem přeloženy do nulového prvku vertexového prostoru, tedy z Eulerových podgrafů. V souladu s tím je zde skupinovou operací symetrický rozdíl Eulerových grafů. $H_{1}(G,\mathbb {F} _{2})$

Definici cyklického prostoru lze rozšířit jeho nahrazením libovolným kruhem , přičemž výsledná homologická skupina je modul nad daným kruhem [8] . Konkrétně se skupina homologie nazývá integrální cyklický prostor . Z hlediska teorie grafů lze takový prostor definovat tak, že uvedeme orientaci v grafu a definujeme celočíselný cyklus jako množinu celých čísel přiřazených hranám grafu takovým způsobem, že v libovolném vrcholu je součet přiřazených čísel k hranám vstupujícím se rovná součtu čísel přiřazených hranám, vycházejících z ní. Podle toho se celočíselný cyklický prostor skládá ze všech celočíselných cyklů a sčítání vektorů v tomto prostoru bude odpovídat sčítání čísel přiřazených každé hraně zvlášť [9] . $\mathbb {F} _{2}$ $H_{1}(G,\mathbb {Z} )$

Prvky nebo (cyklického prostoru modulo ) s dodatečnou podmínkou, že všechna přiřazená čísla jsou nenulová, se nazývají toky nikde nula [10] . $H_{1}(G,\mathbb {Z} )$ $H_{1}(G,\mathbb {Z} _{k})$ $k$

Cyklická hodnost

Rozměr prostoru cyklu grafu s vrcholy, hranami a připojenými složkami je [1] [2] [11] . Toto číslo lze topologicky interpretovat jako první Bettiho číslo grafu [7] . V teorii grafů je také známá jako cyklická hodnost a cyklomatické číslo. Protože prostor cyklů je vektorový prostor nad dvouprvkovým polem, vyplývá z toho, že celkový počet prvků v prostoru cyklů je . $n$ $m$ $C$ $m-n+c$ ${\displaystyle 2^{m-n+c))$

Základ cyklů

Báze prostoru cyklu je rodina Eulerových podgrafů, takže jakýkoli Eulerův podgraf může být reprezentován jako symetrický rozdíl nějaké sady základních cyklů. $m-n+c$

Existence

Podle Veblenovy věty [12] lze každý Eulerův podgraf rozložit na součet jednoduchých cyklů — podgrafů, jejichž hrany tvoří jednu souvislou složku, jejichž vrcholy mají stupeň . Vždy tedy existuje základ, jehož všechny prvky jsou jednoduché cykly. Taková báze se nazývá báze cyklu daného grafu. Navíc je vždy možné sestrojit takový základ, že všechny jeho prvky budou generovány cykly (tedy cykly bez tětiv v původním grafu) [13] . $2$

Základní a slabě fundamentální základy

Chcete-li sestavit základ cyklů, můžete sestrojit zaklenutý les z grafu a pak pro každou hranu , která do lesa nepatří, vytvořit cyklus skládající se z cesty v rozprostírajícím se lese spojující konce hrany. Takto vytvořená množina cyklů je lineárně nezávislá (jelikož každý cyklus obsahuje hranu , která do jiných cyklů nepatří) a skládá se z cyklů, takže je zaručeně základem. Takto zkonstruovaná báze se nazývá fundamentální báze cyklů [1] . $E$ ${\displaystyle C_{e))$ $E$ $E$ $m-n+c$

Báze je považována za slabě fundamentální , pokud lze na sadě cyklů vytvořit lineární uspořádání tak, že každý cyklus obsahuje alespoň jednu hranu, která není obsažena v žádném z předchozích cyklů. Jakýkoli fundamentální základ cyklů je slabě fundamentální (pro jakékoli řády), obráceně to neplatí. Existují grafy, z nichž některé báze cyklu nejsou slabě fundamentální [14] .

Nejmenší hmotnostní základ

Nechť je každé hraně grafu přiřazeno reálné číslo, nazývané jeho váha, a váha libovolného podgrafu je definována jako součet vah hran v něm obsažených. Nejmenší váhová základna v prostoru cyklu musí být základem cyklu a může být sestrojena v polynomiálním čase [9] . Navíc takový základ nemusí být slabě fundamentální a problém najít slabě fundamentální bázi s nejmenší váhou je NP-hard [14] .

Rovinné grafy

McLaneovo kritérium rovinnosti

MacLaneovo kritérium rovinnosti charakterizuje rovinné grafy z hlediska prostoru cyklu a báze cyklu. Kritérium říká, že konečný neorientovaný graf je rovinný právě tehdy, pokud má základnu cyklu, ve které je každá hrana grafu obsažena nejvýše ve dvou cyklech. Takovým základem pro rovinný graf jsou hranice ploch v jeho pokládání , protože každá hrana je obsažena pouze v hranicích dvou ploch, které odděluje. Pokud tedy graf má základ cyklu s touto vlastností, pak jeho prvky mohou být použity jako hranice ploch při pokládání grafu [15] [16] .

Dualita

Prostor cyklů rovinného grafu je prostorem řezů jeho duálního grafu a naopak. Základ nejmenší váhy v rovinném grafu se nemusí nutně shodovat se základem hranic jeho ploch, jak je popsáno výše. Rovinný graf má však vždy nejnižší váhovou základnu, ve které se žádné dva základní cykly neprotínají. Z duality prostorů cyklů a řezů vyplývá, že takové bázi cyklů rovinného grafu odpovídá Gomory-Hu strom jeho duálního grafu, který definuje základnu nejmenší váhy ve svém prostoru řezů [17] .

Nikde nula neteče

V rovinných grafech jsou zbarvení s odlišnými barvami duální až nulové toky přes modulo pole zbytků . Rozdíl mezi čísly barev sousedních ploch v dané dualitě je reprezentován hodnotou toku tekoucího podél hrany, která tyto plochy odděluje. Zejména existence nulového 4-toku v libovolném rovinném grafu je ekvivalentní teorému o čtyřech barvách . Snarkův teorém tento výsledek zobecňuje na nerovinné grafy [18] . $k$ ${\displaystyle \mathbb {Z} _{k))$ $k$

Poznámky

↑ 1 2 3 4 Gross, Jonathan L. & Yellen, Jay (2005), 4.6 Grafy a vektorové prostory , Teorie grafů a její aplikace (2. vydání), CRC Press, str. 197–207, ISBN 9781584885054 , < https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197 > Archivováno 2. května 2019 na Wayback Machine .
↑ 1 2 3 Diestel, Reinhard (2012), 1.9 Some linear algebra , Graph Theory , sv. 173, Absolventské texty z matematiky, Springer, str. 23–28 , < https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23 > Archivováno 2. května 2019 ve Wayback Machine .
↑ Joshi, KD (1997), Applied Discrete Structures , New Age International, s. 172, ISBN 9788122408263 , < https://books.google.com/books?id=lxIgGGJXacoC&pg=PA172 > .
↑ Wallis, W. D. (2010), Průvodce pro začátečníky teorií grafů , Springer, s. 66, ISBN 9780817645809 , < https://books.google.com/books?id=240QO32GJOcC&pg=PA66 > .
↑ Řez grafu zde znamená množinu hran tak, že množinu vrcholů lze rozdělit na dvě neprotínající se podmnožiny a , takové, že . $G=(V,E)$ $S$ $PROTI$ $A$ $B$ $S=E\cap (A\times B)$
↑ Eppstein, David (1996), On the Parity of Graph Spanning Tree Numbers , Technical Report 96-14, Department of Information and Computer Science, University of California, Irvine , < http://www.ics.uci.edu/~ eppstein/pubs/Epp-TR-96-14.pdf > Archivováno 5. října 2020 na Wayback Machine
↑ 1 2 Serre, Jean-Pierre (2003), Stromy , Springerovy monografie v matematice, Springer, str. 23, ISBN 9783540442370 , < https://books.google.com/books?id=MOAqeoYlBMQC&pg=PA23 >
↑ Biggs, Norman (1993), Algebraic Graph Theory , Cambridge Mathematical Library, Cambridge University Press, s. 154, ISBN 9780521458979 , < https://books.google.com/books?id=6TasRmIFOxQC&pg=PA154 >
↑ 1 2 Berger, Franziska; Gritzmann, Peter & de Vries, Sven (2009), Základy minimálního cyklu a jejich aplikace , Algoritmika velkých a komplexních sítí , sv. 5515, Poznámky k přednáškám z informatiky, s. 34–49, ISBN 978-3-642-02093-3
↑ Seymour, PD (1995), Toky nikde nula, Handbook of combinatorics, Vol. 1, 2 , Amsterdam: Elsevier, str. 289–299
↑ Berge, Claude (2001), Cyclomatic number , The Theory of Graphs , Courier Dover Publications, str. 27–30, ISBN 9780486419756 , < https://books.google.com/books?id=h5BjnaoKyOwC&pg=PA27 >
↑ Veblen, Oswald (1912), Aplikace modulárních rovnic na místě analýzy , Annals of Mathematics , Second Series vol. 14 (1): 86–94 , DOI 10.2307/1967604
↑ Diestel (2012 ), str. 32, 65.
↑ 1 2 Rizzi, Romeo (2009), Minimální slabě fundamentální báze cyklu je těžké najít , Algorithmica vol. 53 (3): 402–424 , DOI 10.1007/s00453-007-9112-8
↑ Diestel (2012 ), str. 105-106.
↑ Mac Lane, S. (1937), A combinatorial condition for planar graphs , Fundamenta Mathematicae T. 28: 22–32 , < http://matwbn.icm.edu.pl/ksiazki/fm/fm28/fm2814.pdf > Archivováno 20. ledna 2022 na Wayback Machine
↑ Hartvigsen, David & Mardon, Russell (1994), The all-pairs min cut problem and the minimum cycle basis problem on planar graphs , SIAM Journal on Discrete Mathematics vol. 7 (3): 403–418 , DOI 10.1137/S08954704290
↑ Thomas, Robin (1999), Recent Excluded Minor Theorems for Graphs , Surveys in Combinatorics, 1999 , Cambridge University Press, s. 201–222 , < http://people.math.gatech.edu/~thomas/PAP/bcc.pdf > Archivováno 3. srpna 2016 na Wayback Machine