Sehol nulla áramlás

A gráfelméletben a sehol nulla áramlás a hálózati áramlás  egy speciális fajtája , amely (kettős) kapcsolatban áll a síkgráfok színezésével .

Definíció

Legyen G = (V,E)  egy irányított gráf , és legyen M  egy Abel-csoport . Egy φ: E → M leképezést áramlásnak vagy M - folyamnak nevezünk , ha bármely v ∈ V csúcsra ,

ahol δ + (v) a v - ből kilépő élek halmazát , δ - (v) pedig a v  -be belépő élek halmazát . Néha ezt az állapotot Kirchhoff-szabályként kezelik . Ha φ(e) ≠ 0 bármely e ∈ E csúcsra, akkor φ-ről sehol-nulla áramlásként beszélünk . Ha M = Z  az összeadásból származó egész számok csoportja, és k  olyan pozitív szám, hogy -k < φ(e) < k bármely e élre , akkor a φ M -folyamot k -folyamnak is nevezzük .

Legyen G = (V,E)  egy irányítatlan gráf. Az ívek E -beli orientációját moduláris k - áramlásnak nevezzük, ha

minden v ∈ V csúcsra .

Tulajdonságok

Módosítsa a sehol-nulla φ áramlást a G grafikonon egy e ív kiválasztásával, az ív irányának megváltoztatásával, és a φ(e) helyére -φ(e) -vel . Az ilyen változtatások után a folyam sehol sem marad nulla. Továbbá, ha φ eredetileg k -áramlás volt, akkor a kapott áramlás az is marad. Így a sehol nulla M - áramlás vagy k -áramlás megléte nem függ a gráfívek irányaitól. Azt mondhatjuk, hogy egy irányítatlan G gráfnak nem nulla M -áramlása vagy k -folyama van, ha G íveinek bármely (és így bármely) orientációja rendelkezik ilyen áramlással.

Ennél is meglepőbb, hogy ha M egy k méretű véges Abel-csoport, akkor egyes gráfokon a sehol nulla M -folyamok száma nem M szerkezetétől , hanem csak k -tól, M méretétől függ . Sőt, egy M -folyam létezése egybeesik egy k -folyam létezésével. Ezt a két eredményt Tatt 1953-ban bizonyította [1] .

Az áramlások és színezések kettőssége

Legyen G = (V,E)  egy irányított gráf hidak nélkül a síkon, és tegyük fel, hogy a régiók (lapok) helyesen vannak színezve k színnel {0, 1, 2, .., k  - 1}. Szerkesszünk φ leképezést: E(G) → {-( k  - 1), …, −1, 0, 1, …, k  - 1} a következő szabály szerint: ha az e ívnek x színe van a balra és jobbra színezzük az y -t , beállítjuk, hogy φ (e) = x  - y . Könnyen ellenőrizhető, hogy φ k - folyam. Sőt, ha a régiók helyesen vannak színezve, φ sehol sem nulla k -áramlás. Ez a konstrukcióból következik, hiszen ha G és G* síkbeli duális gráfok és G* k -színezhető, akkor G -nek sehol nulla k -folyama  van . Tutt bebizonyította, hogy ennek az állításnak a fordítottja is igaz. Így a sík gráfok esetében a sehol nulla áramlások kettősek a színezéssel. Mivel a sehol-nulla áramlásoknak nincs értelme tetszőleges gráfokhoz (nem csak a síkban rajzolhatókhoz), vizsgálatuk a színezéselmélet kiterjesztéseként fogható fel nem síkbeli gráfokra.

Elmélet

Megoldatlan problémák a matematikában : Van egy tetszőleges, hidak nélküli gráfnak sehol nulla 5-ös áramlása? Van-e egy tetszőleges gráf hidak és Petersen-gráfok nélkül egy sehol nulla 4-es áramlása?

Mivel egyetlen hurkolt gráfnak sincs szabályos színezése, egyetlen áthidalt gráfnak sem lehet nullától eltérő áramlása bárhol (bármely csoportban). Könnyű kimutatni, hogy bármely híd nélküli gráfnak van sehol nulla Z - áramlása ( Robbins tételéből ), de érdekes kérdés merül fel, amikor kis k értékeihez próbálunk sehol nulla k -folyamot találni . Két elegáns tétel ebben az irányban a Jaeger-féle 4 áramlási tétel (bármely 4 élhez kapcsolódó gráfnak nincs sehol nulla 4 áramlása) [2] és Seymour 6 áramlási tétele (bármely gráf hidak nélkül sehol nulla 6 áramlással rendelkezik) [3] .

Tutt úgy sejtette, hogy minden híd nélküli gráfnak van sehol nulla 5-ös áramlása [4] , és minden híd nélküli gráfnak, amely nem tartalmazza a Petersen-gráfot mellékként , van sehol nulla 4-folyama [5] . A Petersen-mollt nem tartalmazó köbös gráfok esetében a snark-tételből következik a 4-es áramlás , de tetszőleges gráfok esetében a sejtés nyitott marad.

Lásd még

Jegyzetek

  1. ↑ William Thomas Tutte. Hozzájárulás a kromatikus polinomok elméletéhez. – 1953.
  2. ↑ F. Jaeger, Folyamatok és általánosított színezési tételek gráfokban, J. Comb. elméleti halmaz. 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 sejtés Archiválva : 2012. február 8., a Wayback Machine , Open Problem Garden.
  5. ↑ 4-flow sejtés Archiválva : 2012. február 8., a Wayback Machine , Open Problem Garden.

Linkek