Ingen steder nul flow

Et nowhere-zero flow i grafteori  er en speciel form for netværksflow, der er relateret (ved dualitet) til farvning af plane grafer .

Definition

Lad G = (V,E)  være en rettet graf og lad M  være en Abelsk gruppe . En afbildning φ: E → M kaldes et flow eller et M - flow, hvis for et hvilket som helst toppunkt v ∈ V ,

hvor δ + (v) angiver det sæt af kanter, der udgår fra v , og δ - (v)  er sættet af kanter, der går ind i v . Nogle gange behandles denne tilstand som Kirchhoffs regel . Hvis φ(e) ≠ 0 for et hvilket som helst toppunkt e ∈ E , taler vi om φ som en ingensteds-nul- strøm. Hvis M = Z  er gruppen af ​​heltal ved addition, og k  er et positivt tal, således at - k < φ(e) < k for enhver kant e , så kaldes M -flowet φ også k -flow .

Lad G = (V,E)  være en urettet graf. En orientering af buer i E kaldes et modulært k - flow if

for alle hjørner v ∈ V .

Egenskaber

Ændre ingensteds-nul flowet φ på grafen G ved at vælge en bue e , ændre buens retning og erstatte φ(e) med -φ(e) . Efter sådanne ændringer forbliver strømmen intetsteds nul. Yderligere, hvis φ oprindeligt var en k -strøm, så vil den resulterende strøm forblive sådan. Således afhænger eksistensen af ​​et ingensteds-nul M - flow eller k -flow ikke af retningerne af grafbuerne. Vi kan sige, at en urettet graf G har en ikke-nul M - flow eller en k -flow, hvis nogen (og dermed enhver) orientering af buerne af G har en sådan flow.

Endnu mere overraskende er det, at hvis M er en endelig Abelsk gruppe af størrelse k , så afhænger antallet af ingensteds-nul M - strømme på nogle grafer ikke af strukturen af ​​M , men kun af k , størrelsen af ​​M . Ydermere falder eksistensen af ​​et M -flow sammen med eksistensen af ​​et k -flow. Disse to resultater blev bevist af Tatt i 1953 [1] .

Dualitet af flows og farvestoffer

Lad G = (V,E)  være en rettet graf uden broer tegnet på planet, og antag, at områderne (ansigterne) er korrekt farvet med k farver {0, 1, 2, .., k  - 1}. Lad os konstruere en afbildning φ: E(G) → {-( k  - 1), …, −1, 0, 1, …, k  - 1} i henhold til følgende regel: hvis buen e har farven x på venstre og farve y til højre, sætter vi φ (e) = x  - y . Det er let at kontrollere, at φ er et k -flow. Desuden, hvis områderne er korrekt farvet, er φ ingen steder nul k -flow. Dette følger af konstruktionen, da hvis G og G* er plane dobbelte grafer, og G*  er k -farverbar, så har G ingensteds nul k -flow. Tutt beviste, at det modsatte af dette udsagn også er sandt. For plane grafer er ingensteds-nul-flows således dobbelte til farvning. Da nowhere-zero flows giver mening for vilkårlige grafer (ikke kun dem, der kan tegnes i planet), kan deres undersøgelse ses som en udvidelse af farveteori til ikke-planære grafer.

Teori

Uløste problemer i matematik : Har en vilkårlig graf uden broer et nul 5-flow? Har en vilkårlig graf uden broer og uden Petersen-grafer som biord et ingensteds nul 4-flow?

Da ingen sløjfede grafer har en regelmæssig farve, kan ingen broformet graf have et flow, der ikke er nul hvor som helst (i nogen gruppe). Det er nemt at vise, at enhver broløs graf ikke har en nul-nul Z - flow (fra Robbins' sætning ), men et interessant spørgsmål opstår, når man forsøger at finde en intetsteds-nul k - flow for små værdier af k . To elegante sætninger i denne retning er Jaegers 4-flow-sætning (enhver 4-kant-forbundet graf har et intetsteds nul 4-flow) [2] og Seymours 6-flow-sætning (enhver graf uden broer har et ingensteds nul 6-flow) [3] .

Tutt formodede, at enhver broløs graf har et intetsteds nul 5-flow [4] , og at enhver broløs graf, der ikke indeholder Petersen-grafen som en mindre , har et intetsteds nul 4-flow [5] . For kubiske grafer , der ikke indeholder Petersen-mol, følger eksistensen af ​​en 4-flow af snark-sætningen , men for vilkårlige grafer forbliver formodningen åben.

Se også

Noter

  1. ↑ William Thomas Tutte. Et bidrag til teorien om kromatiske polynomier. - 1953.
  2. ↑ F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. teorisæt. B, 26 (1979), 205-216.
  3. ↑ P.D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130-135.
  4. ↑ 5-flow formodning Arkiveret 8. februar 2012 på Wayback Machine , Open Problem Garden.
  5. ↑ 4-flow formodning Arkiveret 8. februar 2012 på Wayback Machine , Open Problem Garden.

Links