Slingutrymme

Cykelutrymmet för en oriktad graf är ett linjärt utrymme över ett fält som består av dess Euler -subgrafer. Dimensionen på detta utrymme kallas grafens konturrang . Ur synvinkel av algebraisk topologi är ett cykliskt utrymme den första homologigruppen i en graf. $\mathbb {F} _{2}$

Definitioner

Grafteori

En spännande subgraf av en given graf är dess subgraf så att uppsättningen av hörn sammanfaller med uppsättningen av hörn . Således har alla grafer med kanter spännande subgrafer, inklusive sig själv och den tomma grafen på uppsättningen av hörn av grafen . Familjen av alla övergripande subgrafer bildar kantutrymmet för den givna grafen. En graf kallas Euler om vart och ett av dess hörn infaller med ett jämnt antal kanter (med andra ord, graden av någon vertex i grafen är jämn). Familjen av alla Euler-spännande subgrafer bildar det cykliska utrymmet för den givna grafen [1] [2] . $G$ $S$ $S$ $G$ $m$ $2^{m}$ $G$ $G$ $G$

Algebra

Kantutrymmet för en graf är stängt med avseende på mängdteoretiska operationer, så det bildar en boolesk algebra [3] . Cykliska rum har också en algebraisk struktur: unionen eller skärningspunkten mellan Euler-subgrafer kanske inte är Euler, men deras symmetriska skillnad kommer att vara [1] . Detta beror på det faktum att den symmetriska skillnaden av mängder med en jämn uppsättning element ( område av hörnet i de första och andra subgraferna) också innehåller en jämn uppsättning element.

En familj av mängder slutna med avseende på en symmetrisk skillnad kan beskrivas algebraiskt av ett vektorrum över ett ändligt fält med två element [4] . Detta fält består av två element, och , och addition och multiplikation motsvarar de logiska operationerna av exklusiva "eller" och konjunktion (addition och multiplikation modulo 2 ). I ett cykliskt utrymme kommer vektorer att vara Euler-subgrafer, deras addition motsvarar en symmetrisk skillnad, multiplikation med en skalär är identitetskartan och multiplikation med en skalär förvandlar vilken subgraf som helst till en tom, vilket motsvarar nollvektorn för den cykliska Plats. $\mathbb {F} _{2}$ $0$ $ett$ $ett$ $0$

Kantutrymmet är också ett vektorrum över med den symmetriska skillnadsoperationen som addition. Det cykliska utrymmet och utrymmet för skärningar [5] är ortogonala komplement till varandra inuti kantutrymmet. Detta betyder att en kantuppsättning är en klippning om och endast om någon Euler-subgraf innehåller ett jämnt antal kanter från och omvänt, en uppsättning är en Euler-undergraf om och endast om något snitt innehåller ett jämnt antal kanter från [2] . Även om dessa utrymmen är ortogonala komplement till varandra, kan de ha en icke-trivial skärningspunkt. I allmänhet har en graf ett icke-tomt Eulersnitt om och endast om antalet av dess spännande skogar är jämnt [6] . $\mathbb {F} _{2}$ $S$ $S$ $S$ $S$ $G$

Topologi

En oriktad graf kan ses som ett enkelt komplex vars hörn är nolldimensionella förenklingar och vars kanter är endimensionella förenklingar [7] . Kedjekomplexet i ett sådant topologiskt utrymme består av dess kant- och vertexutrymmen sammankopplade med en gränsoperator som mappar vilken som helst spännande subgraf (ett element i kantrymden) till dess uppsättning av hörn av udda grad (ett element i vertexutrymmet). Homologigruppen består av element i kantutrymmet, som översätts av gränsoperatorn till nollelementet i vertexutrymmet, det vill säga från Euler-subgrafer. Följaktligen är gruppoperationen här den symmetriska skillnaden mellan Euler-grafer. $H_{1}(G,\mathbb {F} _{2})$

Definitionen av ett cykliskt utrymme kan utökas genom att ersätta det med en godtycklig ring , den resulterande homologigruppen är en modul över den givna ringen [8] . I synnerhet kallas homologigruppen för ett integrerat cykliskt utrymme . I grafteoretiska termer kan ett sådant utrymme definieras genom att ge en orientering på grafen och definiera en heltalscykel som en uppsättning heltal som tilldelas grafens kanter på ett sådant sätt att summan av de tilldelade talen vid varje hörn till kanterna som kommer in är det lika med summan av talen som tilldelats kanterna, som kommer från henne. Följaktligen består ett heltalscykliskt utrymme av alla heltalscykler, och tillägget av vektorer i detta utrymme kommer att motsvara tillägget av talen som tilldelats varje kant separat [9] . $\mathbb {F} _{2}$ $H_{1}(G,\mathbb {Z} )$

Element av eller (av ett cykliskt utrymme modulo ) med det ytterligare villkoret att alla tilldelade nummer är icke-noll kallas nowhere-noll-strömmar [10] . $H_{1}(G,\mathbb {Z} )$ $H_{1}(G,\mathbb {Z} _{k})$ $k$

Cyklisk rang

Dimensionen på cykelrymden för en graf med hörn, kanter och anslutna komponenter är [1] [2] [11] . Detta nummer kan topologiskt tolkas som det första Betti-talet i grafen [7] . I grafteori är det också känt som cyklisk rang och cyklomatiskt tal. Eftersom utrymmet av cykler är ett vektorutrymme över ett tvåelementsfält, följer det att det totala antalet element i kretsloppsrummet är . $n$ $m$ $c$ $m-n+c$ ${\displaystyle 2^{m-n+c))$

Grund för cykler

En cykelrymdsbas är en familj av Euler-subgrafer så att vilken Euler-subgraf som helst kan representeras som en symmetrisk skillnad mellan någon uppsättning bascykler. $m-n+c$

Existens

Enligt Veblen-satsen [12] kan vilken Euler-subgraf som helst delas upp i en summa av enkla cykler - subgrafer, vars alla kanter bildar en ansluten komponent, vars alla hörn har grad . Det finns alltså alltid en grund vars alla element är enkla cykler. En sådan bas kallas cykelbasen för den givna grafen. Dessutom är det alltid möjligt att konstruera en sådan bas att alla dess element kommer att genereras cykler (det vill säga cykler utan ackord i den ursprungliga grafen) [13] . $2$

Grundläggande och svagt grundläggande baser

För att bygga en bas av cykler kan du konstruera en spännande skog av grafen, och sedan för varje kant som inte hör till skogen, bilda en cykel bestående av tillsammans med en stig i den spännande skogen som förbinder kantens ändar. Uppsättningen av cykler som bildas på detta sätt är linjärt oberoende (eftersom varje cykel innehåller en kant som inte tillhör andra cykler) och består av cykler, så det är garanterat en grund. Grunden konstruerad på detta sätt kallas för cyklernas fundamentala grund [1] . $e$ ${\displaystyle C_{e))$ $e$ $e$ $m-n+c$

En bas sägs vara svagt fundamental om en linjär ordning kan etableras på uppsättningen av cykler så att varje cykel innehåller åtminstone en kant som inte ingår i någon av de föregående cyklerna. Varje grundläggande grund för cykler är svagt fundamental (för alla beställningar), det omvända är inte sant. Det finns grafer vars cykelbaser inte är svagt fundamentala [14] .

Lägsta viktbasis

Låt varje kant av grafen tilldelas ett reellt tal, kallat dess vikt, och vikten av en subgraf definieras som summan av vikterna av kanterna som ingår i den. Den minsta viktbasen i cykelutrymmet måste vara en cykelbas och kan konstrueras i polynomtid [9] . En sådan bas behöver dessutom inte vara svagt fundamental, och problemet med att hitta en svagt fundamental bas med minst vikt är NP-hårt [14] .

Plana grafer

McLanes planaritetskriterium

MacLanes planaritetskriterium karakteriserar plana grafer i termer av cykelutrymme och cykelbas. Kriteriet anger att en ändlig oriktad graf är plan om och endast om den har en cykelbas där varje grafkant ingår i högst två cykler. En sådan grund för en plan graf är gränserna för ytorna i dess läggning , eftersom varje kant endast finns i gränserna för de två ytorna som den separerar. Följaktligen, om grafen har en cykelbas med denna egenskap, kan dess element användas som gränser för ytorna vid läggningen av grafen [15] [16] .

Dualitet

Cykelutrymmet för en plan graf är utrymmet för snitt av dess dubbla graf, och vice versa. Grunden för den minsta vikten i en plan graf sammanfaller inte nödvändigtvis med grunden för gränserna för dess ytor, som beskrivs ovan. En plan graf har dock alltid en minsta viktbasis där inga två bascykler skär varandra. Av dualiteten av utrymmen av cykler och snitt, följer det att en sådan bas av cykler i en plan graf motsvarar Gomory-Hu-trädet i dess dubbla graf, som definierar grunden för den minsta vikten i dess utrymme för snitt [17] .

Ingenstans flyter noll

I plana grafer är färger med distinkta färger dubbla till ingenstans-noll flöden över modulofältet av rester . Skillnaden mellan färgnumren för närliggande ytor i en given dualitet representeras av värdet på flödet som flödar längs kanten som skiljer dessa ytor åt. I synnerhet är förekomsten av ett noll-noll 4-flöde i någon plan graf ekvivalent med fyrfärgssatsen . Snarksatsen generaliserar detta resultat till icke-planära grafer [18] . $k$ ${\displaystyle \mathbb {Z} _{k))$ $k$

Anteckningar

↑ 1 2 3 4 Gross, Jonathan L. & Yellen, Jay (2005), 4.6 Graphs and Vector Spaces , Graph Theory and Its Applications (2nd ed.), CRC Press, sid. 197–207, ISBN 9781584885054 , < https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197 > Arkiverad 2 maj 2019 på Wayback Machine .
↑ 1 2 3 Diestel, Reinhard (2012), 1.9 Some linear algebra , Graph Theory , vol. 173, Graduate Texts in Mathematics, Springer, sid. 23–28 , < https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23 > Arkiverad 2 maj 2019 på Wayback Machine .
↑ Joshi, KD (1997), Tillämpade diskreta strukturer , New Age International, sid. 172, ISBN 9788122408263 , < https://books.google.com/books?id=lxIgGGJXacoC&pg=PA172 > .
↑ Wallis, W.D. (2010), A Beginners Guide to Graph Theory , Springer, s. 66, ISBN 9780817645809 , < https://books.google.com/books?id=240QO32GJOcC&pg=PA66 > .
↑ Här betyder ett snitt av en graf en uppsättning kanter så att uppsättningen av hörn kan delas upp i två icke-korsande delmängder och , så att . $G=(V,E)$ $S$ $V$ $A$ $B$ $S=E\cap (A\times B)$
↑ Eppstein, David (1996), On the Parity of Graph Spanning Tree Numbers , Teknisk rapport 96-14, Institutionen för information och datavetenskap, University of California, Irvine , < http://www.ics.uci.edu/~ eppstein/pubs/Epp-TR-96-14.pdf > Arkiverad 5 oktober 2020 på Wayback Machine
↑ 1 2 Serre, Jean-Pierre (2003), Trees , Springer Monographs in Mathematics, Springer, sid. 23, ISBN 9783540442370 , < https://books.google.com/books?id=MOAqeoYlBMQC&pg=PA23 >
↑ Biggs, Norman (1993), Algebraic Graph Theory , Cambridge Mathematical Library, Cambridge University Press, sid. 154, ISBN 9780521458979 , < https://books.google.com/books?id=6TasRmIFOxQC&pg=PA154 >
↑ 1 2 Berger, Franziska; Gritzmann, Peter & de Vries, Sven (2009), Minimicykelbaser och deras tillämpningar , Algorithmics of Large and Complex Networks , vol. 5515, Lecture Notes in Computer Science, sid. 34–49, ISBN 978-3-642-02093-3
↑ Seymour, PD (1995), Nowhere-zero flows, Handbook of combinatorics, Vol. 1, 2 , Amsterdam: Elsevier, sid. 289–299
↑ Berge, Claude (2001), Cyclomatic nummer , The Theory of Graphs , Courier Dover Publications, s. 27–30, ISBN 9780486419756 , < https://books.google.com/books?id=h5BjnaoKyOwC&pg=PA27 >
↑ Veblen, Oswald (1912), An application of modular equations in analysis situs , Annals of Mathematics , Second Series vol. 14 (1): 86–94 , DOI 10.2307/1967604
↑ Diestel (2012 ), s. 32, 65.
↑ 1 2 Rizzi, Romeo (2009), Minimum svagt grundläggande cykelbaser är svåra att hitta , Algorithmica vol. 53 (3): 402–424 , DOI 10.1007/s00453-007-9112-8
↑ Diestel (2012 ), s. 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 > Arkiverad 20 januari 2022 på Wayback Machine
↑ Hartvigsen, David & Mardon, Russell (1994), The all-pairs min cut problem and the minimum cycle bas problem on planar graphs , SIAM Journal on Discrete Mathematics vol. 7 (3): 403–418 , DOI 10.1137/S08951770420
↑ Thomas, Robin (1999), Recent Excluded Minor Theorems for Graphs , Surveys in Combinatorics, 1999 , Cambridge University Press, sid. 201–222 , < http://people.math.gatech.edu/~thomas/PAP/bcc.pdf > Arkiverad 3 augusti 2016 på Wayback Machine