Ei missään nollavirtausta

Nowhere-nolla-virta graafiteoriassa on  erityinen verkkovirta , joka liittyy (kaksoisuudella) tasograafien värjäämiseen .

Määritelmä

Olkoon G = (V,E)  suunnattu graafi  ja olkoon M Abelin ryhmä . Kuvausta φ: E → M kutsutaan virtaukseksi tai M - virtaukseksi , jos jollekin kärjelle v ∈ V ,

missä δ + (v) tarkoittaa v :stä lähtevien reunojen joukkoa ja δ - (v) on v :stä  tulevien reunojen joukko . Joskus tätä tilaa pidetään Kirchhoffin sääntönä . Jos φ(e) ≠ 0 mille tahansa kärjelle e ∈ E , puhumme φ: stä nolla-ei-nolla- virtauksena. Jos M = Z  on yhteenlaskettuna kokonaislukujen ryhmä ja k  on positiivinen luku siten, että -k < φ(e) < k mille tahansa reunalle e , niin M - virtaa φ kutsutaan myös k -virtaukseksi .

Olkoon G = (V,E)  suuntaamaton graafi. Kaarien suuntausta E :ssä kutsutaan modulaariseksi k - virtaukseksi , jos

kaikille pisteille v ∈ V .

Ominaisuudet

Muuta kaavion G ei-nolla-virtausta φ valitsemalla kaari e , muuttamalla kaaren suuntaa ja korvaamalla φ(e) arvolla -φ(e) . Tällaisten muutosten jälkeen virta ei pysy missään nollassa. Lisäksi, jos φ oli alun perin k -virtaus, niin tuloksena oleva virtaus pysyy sellaisena. Siten nowhere-nolla M - virtauksen tai k -virran olemassaolo ei riipu graafin kaarien suunnista. Voidaan sanoa, että suuntaamattomalla graafilla G on nollasta poikkeava M - virtaus tai k -virtaus, jos jollakin (ja siten missä tahansa) G :n kaarien orientaatiossa on tällainen virtaus.

Vielä yllättävämpää on se, että jos M on äärellinen Abelin ryhmä, jonka koko on k , niin ei-nolla- M -virtojen määrä joissakin graafisissa ei riipu M :n rakenteesta , vaan vain k :stä, M :n koosta . Lisäksi M - virran olemassaolo on sama kuin k - virran olemassaolo. Tatt todisti nämä kaksi tulosta vuonna 1953 [1] .

Virtojen ja värien kaksinaisuus

Olkoon G = (V,E)  suunnattu graafi ilman siltoja , jotka on piirretty tasolle, ja oletetaan, että alueet (pinnat) on värjätty oikein k värillä {0, 1, 2, .., k  - 1}. Muodostetaan kuvaus φ: E(G) → {-( k  - 1), …, −1, 0, 1, …, k  - 1} seuraavan säännön mukaisesti: jos kaarella e on väri x vasemmalla ja väri y oikealla, asetamme φ (e) = x  - y . On helppo tarkistaa, että φ on k - virtaus. Lisäksi, jos alueet on väritetty oikein, φ ei ​​ole missään nolla k - virtaa. Tämä seuraa konstruktiosta, koska jos G ja G* ovat tasomaisia ​​kaksoisgraafia ja G*  on k -väritettävä, niin G :llä ei ole minkäänlaista k -virtausta. Tutt osoitti, että tämän väitteen käänteinen on myös totta. Siten tasokaavioissa nollan nolla-virrat ovat kaksoisvärjäyksen kanssa. Koska ei missään nolla-virrat eivät ole järkeviä mielivaltaisille kaavioille (ei vain sellaisille, jotka voidaan piirtää tasoon), niiden tutkimusta voidaan pitää väritysteorian laajentamisena ei-tasomaisiin graafisiin.

Teoria

Ratkaisemattomat matematiikan ongelmat : Onko mielivaltaisella graafilla ilman siltoja nollan 5-virtaus? Onko mielivaltaisella graafilla ilman siltoja ja ilman Petersenin graafia molempina nollan 4-virtaus?

Koska yhdelläkään silmukalla olevalla graafilla ei ole säännöllistä väritystä, millään silloitetulla graafilla ei voi olla nollasta poikkeavaa virtausta missään (missä tahansa ryhmässä). On helppo osoittaa, että millä tahansa siltaattomalla graafilla on ei-nolla- Z - virtaus ( Robbinsin lauseesta ), mutta mielenkiintoinen kysymys herää, kun yritetään löytää ei-nolla- k - virtaus pienille k :n arvoille . Kaksi tyylikästä lausetta tähän suuntaan ovat Jaegerin 4-virtauslause (millä tahansa 4 reunaan yhdistetyllä graafilla ei ole nollan 4-virtausta) [2] ja Seymourin 6-virtauksen lause (millä tahansa graafilla, jossa ei ole siltoja, on nowhere-6-virtaus) [3] .

Tutt arveli, että millä tahansa sillattomalla graafilla ei ole nollan 5-virtaa [4] ja että jokaisella siltaattomalla graafilla, joka ei sisällä Petersenin graafia sivuaineena , on nowhere-4-virtaus [5] . Kuutiograafisille , jotka eivät sisällä Petersen-molli, 4-virtauksen olemassaolo seuraa snark-lauseesta , mutta mielivaltaisten graafien tapauksessa arvelu jää avoimeksi .

Katso myös

Muistiinpanot

  1. ↑ William Thomas Tutte. Panos kromaattisten polynomien teoriaan. – 1953.
  2. ↑ F. Jaeger, Flows and generalised coloring theoreems in graphs, J. Comb. teoriasarja. 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 conjecture Arkistoitu 8. helmikuuta 2012 at the Wayback Machine , Open Problem Garden.
  5. ↑ 4-flow conjecture Arkistoitu 8. helmikuuta 2012 at the Wayback Machine , Open Problem Garden.

Linkit