Ingenstans-noll flöde

I grafteorin är ett nollflöde eller NZ-flöde ett nätverksflöde som inte är noll. Det är intimt kopplat (genom dualitet) till att färglägga plana grafer .

Definitioner

Låt G = ( V , E ) vara en digraf och låt M vara en abelsk grupp . En karta φ : E → M är en M -cirkulation om för varje vertex v ∈ V

\sum _{e\in \delta ^{+}(v)}\phi (e )=\summa _{e\in \delta ^{-}(v)}\phi (e),

där δ ⁺ ( v ) betecknar uppsättningen kanter ut ur v och δ ⁻ ( v ) betecknar uppsättningen av kanter till v . Ibland kallas detta tillstånd för Kirchhoffs lag .

Om φ ( e ) ≠ 0 för varje e ∈ E , kallar vi φ för ett nollflöde, ett M -flöde eller ett NZ-flöde. Om k är ett heltal och 0 < | φ ( e )| < k då är φ ett k -flöde.

Andra föreställningar

Låt G = ( V , E ) vara en oriktad graf . En orientering av E är ett modulärt k - flöde om vi för varje vertex v ∈ V har:

|\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\bmod {k}}.

Egenskaper

Mängden M -flöden bildar inte nödvändigtvis en grupp eftersom summan av två flöden på en kant kan adderas till 0. (

Tutte 1950) En graf G har ett M -flöde om och bara om den har en | M |-flöde. Som en konsekvens existerar ett ${\displaystyle \mathbb {Z} _{k}}-$ flöde om och endast om ett k -flöde existerar. Som en konsekvens av detta, om G släpper in ett k -flöde så släpper det in ett h -flöde där $h\geq k$ .

Orienteringsoberoende. Modifiera ett nollflöde φ på en graf G genom att välja en kant e , vända den och sedan ersätta φ ( e ) med − φ ( e ). Efter denna justering φ fortfarande ett nollflöde. Dessutom, om φ ursprungligen var ett k -flöde, så är det resulterande φ också ett k -flöde. Således är förekomsten av ett ingenstans-noll M -flöde eller ett ingenstans-noll k -flöde oberoende av orienteringen av grafen. Således sägs en oriktad graf G ha ett ingenstans-noll M -flöde eller ingenstans-noll k -flöde om någon (och därmed varje) orientering av G har ett sådant flöde.

Flödespolynom

Låt $N_{M}(G)$ vara antalet M -flöden på G . Det uppfyller deletion-kontraktionsformeln :

N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).

Genom att kombinera detta med induktion kan vi visa $N_{M}(G)$ är ett polynom i $|M|-1$ där $|M|$ är ordningen för gruppen M . Vi kallar $\displaystyle N_{M}(G)}$ { flödespolynomet för G och abelsk grupp M .

Ovanstående innebär att två grupper av lika ordning har lika många NZ-flöden. Ordningen är den enda gruppparametern som spelar roll, inte strukturen för M . Speciellt $N_{M_{1}}(G)=N_{M_{2}}(G)$ om $|M_{1}|=|M_{2}|.$

Ovanstående resultat bevisades av Tutte 1953 när han studerade Tutte-polynomet , en generalisering av flödespolynomet.

Dualitet med flödesfärg

Brolösa plana grafer

Det finns en dualitet mellan k - ytfärgningar och k -flöden för brygglösa plana grafer . För att se detta, låt G vara en riktad brygglös plan graf med en riktig k -ansiktsfärgning med färgerna $\{0,1,\ldots ,k-1\}.$ Konstruera en karta

\phi :E(G)\to \{-(k-1), \ldots ,-1,0,1,\ldots ,k-1\}

enligt följande regel: om kanten e har en yta med färgen x till vänster och en yta med färgen y till höger, låt φ ( e ) = x – y . Då φ ett (NZ) k -flöde eftersom x och y måste ha olika färg.

Så om G och G* är plana dubbla grafer och G* är k -färgbar (det finns en färgning av ytorna på G ), så har G ett NZ k -flöde. Använder induktion på | E ( G )| Tutte bevisade att det omvända också är sant. Detta kan uttryckas kortfattat som:

\chi (G^{*})=\phi (G),

där RHS är flödestalet , det minsta k för vilket G tillåter ett k -flöde.

Allmänna grafer

Dualiteten gäller även för allmänna M -flöden:

Låt $c$ vara ansiktsfärgningsfunktionen med värden i M .

Definiera $\phi _{c}(e)=c(r_{1})-c(r_{2})$ där r ₁ är ansiktet till vänster om e och r ₂ är till höger.

För varje M -cirkulation $\phi$ finns en färgningsfunktion c så att $\phi =\phi _{c}$ (bevisat genom induktion).

c är en | E ( G )|-ansiktsfärgning om och endast om $\phi _{c}$ är ett NZ M -flöde (raktframåt).

Dualiteten följer genom att kombinera de två sista punkterna. Vi kan specialisera oss på $M=\mathbb {Z} _{k}$ för att få liknande resultat för k -flöden som diskuterats ovan. Med tanke på denna dualitet mellan NZ-flöden och färger, och eftersom vi kan definiera NZ-flöden för godtyckliga grafer (inte bara plana), kan vi använda detta för att utöka ansiktsfärgningar till icke-plana grafer.

Ansökningar

G är 2-face-färgbar om och endast om varje vertex har jämn grad (tänk på NZ 2-flöden).

Låt $K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}$ vara Klein-4-gruppen . Då har en kubikgraf ett K -flöde om och bara om det är 3- kantsfärgbart . Som en följd av detta är en kubisk graf som är färgbar med tre kanter färgbar med fyra sidor.

En graf är färgbar med fyra sidor om och endast om den tillåter ett NZ 4-flöde (se Fyrfärgssatsen ) . Petersen -grafen har inget NZ 4-flöde, och detta ledde till 4-flödesförmodan (se nedan).

Om G är en triangulering så är G 3-(vertex) färgbar om och endast om varje vertex har en jämn grad. Vid den första kulan är den dubbla grafen G * 2-färgbar och därmed tvådelad och plan kubisk. Så G * har ett NZ 3-flöde och är således färgbart med 3 sidor, vilket gör G 3-vertex färgbar.

Precis som ingen graf med en slingkant har en korrekt vertexfärgning, kan ingen graf med en brygga ha ett NZ M -flöde för någon grupp M . Omvänt har varje brygglös graf ett NZ $\mathbb {Z}$ -flöde (en form av Robbins sats ) .

Förekomst av k -flöden

Olöst problem i matematik :

Har varje brygglös graf ett noll-5-flöde? Har varje brolös graf som inte har Petersen-grafen som moll ett ingenstans noll 4-flöde?

(fler olösta problem i matematik)

Intressanta frågor uppstår när man försöker hitta ingenstans-noll k -flöden för små värden på k . Följande har bevisats:

Jaegers 4-flödessats. Varje 4- kantsansluten graf har ett 4-flöde.

Seymours 6-flödessats. Varje brygglös graf har ett 6-flöde.

3-flödes-, 4-flödes- och 5-flödesgissningar

Från och med 2019 är följande för närvarande olösta (på grund av Tutte ):

3-flödesförmodan. Varje 4-kants ansluten graf har ett noll 3-flöde.

4-flödesförmodan. Varje brygglös graf som inte har Petersen-grafen som en moll har ett noll-4-flöde.

5-flödesförmodan. Varje brygglös graf har ett ingenstans-noll 5-flöde.

Motsatsen till 4-flödesförmodan håller inte eftersom hela grafen K ₁₁ innehåller en Petersen-graf och en 4-flödesdiagram. För brolösa kubiska grafer utan Petersen-moll existerar 4-flöden av snarksatsen (Seymour, et al 1998, ännu inte publicerad). Fyrfärgssatsen motsvarar påståendet att ingen snark är plan .

Se även

Vidare läsning

Zhang, Cun-Quan (1997). Heltalsflöden och cykelomslag för grafer . Chapman & Hall/CRC Pure and Applied Mathematics Series. Marcel Dekker, Inc. ISBN 9780824797904 . LCCN 96037152 .
Zhang, Cun-Quan (2012). Circuit dubbel täckning av grafer . Cambridge University Press. ISBN 978-0-5212-8235-2 .
Jensen, TR; Toft, B. (1995). "13 orienteringar och flöden". Graffärgningsproblem . Wiley-Interscience Serires i diskret matematik och optimering. s. 209 –219. ISBN 9780471028659 .
Jacobsen, Jesper Lykke; Salas, Jesús (2013). "Är femflödesgissningen nästan falsk?". Journal of Combinatorial Theory . Serie B. 103 (4): 532–565. arXiv : 1009.4062 . doi : 10.1016/j.jctb.2013.06.001 . MR 3071381 . S2CID 41483928 .