Vizings teorem

Vizings teorem är ett uttalande om grafteorin , enligt vilket kanterna på vilken enkel oriktad graf som helst kan färgas i ett antal färger, högst en som är större än den maximala graden av grafens hörn. Eftersom det alltid finns tillräckligt med färger, kan alla oriktade grafer delas in i två klasser - grafer av "första klassen", för vilka det finns tillräckligt med färger, och "andra klassen", för vilka färger behövs. $\Delta$ $\Delta +1$ $\Delta$ $\Delta +1$

Resultatet fastställdes av Vadim Vizing 1964 .

Exempel

Om , finns det inga intilliggande kanter i grafen, och kanterna kan färgas i samma färg. Alltså tillhör alla grafer med den första klassen. $\Delta =1$ $G$ $\Delta (G)=1$

Om , måste grafen vara en osammanhängande förening av banor och cykler . Om alla cykler är jämna, kan deras kanter färgas i två färger, byta färger i tur och ordning, passera längs varje cykel. Men om det finns minst en udda cykel kan dess kanter inte vara tvåfärgade. Således tillhör en graf c den första klassen om och endast om den är tvådelad . $\Delta =2$ $G$ $\Delta =2$

För multigrafer , i allmänhet, stämmer inte Vizings teorem. Till exempel har multigrafen som bildas genom att dubbla varje kant av en triangel en maximal grad av fyra, men kanterna på denna graf kan inte färgas med mindre än sex färger.

Klassificering av grafer

Vissa författare har gett ytterligare villkor för att vissa grafer ska tillhöra den första eller andra klassen, men det finns ingen fullständig klassificering. Till exempel, om topparna med maximal grad i grafen bildar en oberoende uppsättning , eller, mer allmänt, om den genererade subgrafen för denna uppsättning av hörn är en skog, kommer den att tillhöra den första klassen [1] . $\Delta$ $G$ $G$

Erdős och Wilson [2] visade att nästan alla grafer tillhör den första klassen. Så, i modellen av slumpmässiga Erdős-Rényi-grafer , där alla grafer med hörn är lika sannolika, låt beteckna sannolikheten att grafen med hörn tillhör den första klassen. Sedan tenderar det till enhet som det tenderar till oändligheten. Senare utvecklade mer subtila uppskattningar av graden av strävan till enhet [3] . $n$ $p(n)$ $n$ $p(n)$ $n$ $p(n)$

Plangrafer

Vizing [4] visade att en plan graf tillhör den första klassen om dess maximala grad är minst åtta. Han märkte dock att det för en maximal grad av två till fem finns andra klassens plana grafer. För grader två är vilken udda cykel som helst en sådan graf, och för grader tre, fyra och fem kan sådana grafer konstrueras från vanliga polytoper genom att ersätta kanter på en bana av par av intilliggande kanter.

Vizings gissning om plana grafer [4] säger att alla enkla plana grafer med maximal grad sex och sju tillhör den första klassen, vilket stänger de återstående möjligheterna. Det fastställdes 2001 [5] att alla plana grafer med maximal grad sju tillhör den första klassen. Det är alltså bara fallet med den maximala effekten på sex som kvarstår i fråga. Denna gissning ger bakgrunden för den totala färgläggningsförmodan .

Plana grafer av den andra klassen, byggda av vanliga polytoper genom att dela kanter, är inte regelbundna - de har både hörn av andra ordningen och hörn av högre ordning. Fyrfärgssatsen om färgningen av hörnen i en plan graf motsvarar påståendet att varje 3-regelbunden brolös graf tillhör den första klassen [6] (detta påstående är sant med tanke på beviset för fyrfärgen sats).

Grafer på icke-plana ytor

1969 antog Branko Grünbaum att varje 3-regelbunden graf som har en polyedrisk inbäddning i ett tvådimensionellt orienterat grenrör , såsom en torus , måste tillhöra den första klassen. I detta sammanhang betyder en polytopinbäddning en grafinbäddning så att varje resulterande grafyta är topologiskt ekvivalent med en skiva, och så att den dubbla grafen är enkel, utan slingor eller flera angränsningar. Om detta vore sant, skulle det vara en generalisering av fyrfärgssatsen, vilket, som Tate visade, motsvarar att säga att varje 3-regelbunden graf för vilken det finns en polytopinbäddning i sfären är i första klassen. Men 2009 [7] visades det att gissningen inte är sann genom att hitta snarkar som har en inbäddning i form av polyedrar i orienterade ytor av högt släkte . Utifrån denna konstruktion visade han också att avgöra om en graf med en polytopinbäddning tillhör den första klassen är ett NP-komplett problem [8] .

Algoritmer

År 1992 [9] beskrev en algoritm för polynomisk tidsfärgning av vilken graf som helst med hjälp av färger, där är den maximala graden av grafen. Algoritmen använder således det optimala antalet färger för grafer av den andra klassen, och använder som mest en extra färg för alla grafer. Algoritmen använder samma strategi som det ursprungliga beviset för Vizings teorem – algoritmen börjar med en färglös graf och söker i följd efter färgläggningsbanor så att ytterligare en kant ingår i färgläggningen. $\Delta +1$ $\Delta$

Beskrivningen av algoritmen använder termerna "fläkt", "fläktrotation" och " -path", introducerade av författarna till algoritmen [10] , samt följande konvention: en färg är fri vid en vertex om det finns inga färgfärgade kanter som träffar vertexen . Algoritmen utför följande steg: $cd$ $d$ $w$ $d$ $w$

För varje ofärgad kant i en delvis färgad graf konstrueras en sekvens - den maximala fläkten. $UV$ $\vänster\langle v,...,l\höger\rangle$
- För varje färgpar , där är färgen fri vid spetsen och är färgen fri vid , ritas färgerna på -banan. $CD$ $c$ $u$ $d$ $l$ $cd$
- En vertex väljs så att den är en delsträng och inte används i . $w$ $\left\langle v,...,w\right\rangle$ $\vänster\langle v,...,l\höger\rangle$ $d$ $w$
- Fläkten "roterar", är målad i färg . $\left\langle v,...,w\right\rangle$ $ww$ $d$

En fläkt är en sekvens av hörn med följande egenskaper: $\left\langle v_{0},...,v_{r}\right\rangle$

alla hörn är grannar till vertex och $u$ $v_{0}=v$
kanten är målad i en färg som inte användes i hörnen $u\,v_{k+1}$ $d_{k}$ $\left\langle v_{0},\ldots ,v_{k}\right\rangle$

Fläkten kan roteras , det vill säga färgerna på kanterna kan ersättas med färgerna på kanterna , och denna permutation av färger bryter inte mot färgningen av grafen. ${\displaystyle uv_{k))$ $uv_{k+1}$

$cd$ -path är den maximala sekvensen av kanter som börjar på , och varje kant är färgad på eller . Att vända om färgerna på denna kedja innebär att byta ut med och med . $u$ $c$ $d$ $c$ $d$ $d$ $c$

Alla operationer som används i algoritmen förstör inte färgen på grafen, och efter att ha vänt om färgerna på -vägen finns underkedjan som beskrivs i algoritmen. $cd$

Genom att använda en enkel datastruktur för att lagra färgerna som används vid en vertex, kan hela steget i algoritmen slutföras i tid , där är antalet hörn i grafen. Eftersom varje steg måste upprepas för alla bågar, blir den totala tiden . $På)$ $n$ $m$ $O(mn)$

I en opublicerad tidning 1985 [11] konstaterades att det är möjligt att hitta en färgläggning i tid . $O(m{\sqrt n}\log n)$

Historik

Man tror [12] [13] att Vizings arbete inspirerades av Shannons teorem [14] , som visar att multigrafer kan färgas med de flesta färger. Det finns också en åsikt att Vizing hade problem med publiceringen av resultatet (först publicerad i tidskriften "Discrete Analysis", publicerad före 1991 av Institute of Mathematics of the Siberian Branch of the USSR Academy of Sciences , som västerländska författare kallar " lite känd" [12] ). ${\tfrac {3}{2}}\Delta$

Se även

Brooks' teorem , som relaterar vertexfärgning till maximal grad.

Anteckningar

↑ Fournier, 1973 .
↑ Erdős, Wilson, 1977 .
↑ Frieze, Jackson, McDiarmid, Reed, 1988 .
↑ 1 2 Vizing, 1965 .
↑ Sanders, Zhao, 2001 .
↑ Tait, 1880 .
↑ Kochol, 2009 .
↑ Kochol, 2010 .
↑ Misra, Gries, 1992 .
↑ Algoritmbeskrivning hämtad från en artikel av Joachim Breitner. Bevisar Vizings teorem med Rodin. — 2011.
↑ Gabow et al., 1985 .
↑ 12 Gutin, Toft, 2000 .
↑ Soifer, 2008 .
↑ Shannon, 1949 .

Litteratur

K. Appel, W. Haken. Varje plan karta är fyra färgbar // Bulletin of the American Mathematical Society. - 1976. - T. 82 , nr. 5 . — S. 711–712 . - doi : 10.1090/S0002-9904-1976-14122-5 .
Paul Erdős, Robin J. Wilson. Notera om det kromatiska indexet för nästan alla grafer // Journal of Combinatorial Theory . - 1977. - T. 23 , nr. 2–3 . — S. 255–257 . - doi : 10.1016/0095-8956(77)90039-9 .
Jean-Claude Fournier. Colorations des arêtes d'un graphe // Cahiers du Centre d'Études de Recherche Opérationnelle. - 1973. - T. 15 . — S. 311–314 .
Alan M. Frieze, B. Jackson, CJH McDiarmid, B. Reed. Kantfärgade slumpmässiga grafer // Journal of Combinatorial Theory . - 1988. - T. 45 , nr. 2 . — S. 135–149 . - doi : 10.1016/0095-8956(88)90065-2 .
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algoritmer för grafer för kantfärgning. - Tohoku University, 1985. - (Teknisk rapport TRECIS-8501).
Gregory Gutin, Bjarne Toft. Intervju med Vadim G. Vizing // European Mathematical Society Newsletter. - 2000. - T. 38 , nr. december . — S. 22–23.
Martin Kochol. Proceedings of the American Mathematical Society. - 2009. - T. 137. - S. 1613-1619.
Martin Kochol. Komplexitet av 3-kantsfärgning i klassen av kubiska grafer med en polyedrisk inbäddning i en orienterbar yta // Diskret tillämpad matematik. - 2010. - T. 158 , nr. 16 . - S. 1856-1860 . - doi : 10.1016/j.dam.2010.06.019 .
Ett konstruktivt bevis på Vizings sats // Information Processing Letters . - 1992. - T. 41 , nr. 3 . — S. 131–133 . - doi : 10.1016/0020-0190(92)90041-S .
Daniel P. Sanders, Yue Zhao. Plana grafer av maximal grad sju är klass I // Journal of Combinatorial Theory . - 2001. - T. 83 , nr. 2 . — S. 201–212 . - doi : 10.1006/jctb.2001.2047 .
Claude Shannon. Ett teorem om färgläggning av linjerna i ett nätverk // J. Math. Fysik. - 1949. - T. 28 . — S. 148–151 .
Alexander Soifer. Den matematiska målarboken. - 2008. - S. 136-137 . — ISBN 978-0-387-74640-1 .
PG Tait. Anmärkningar om kartornas färgsättning // Proc. R. Soc. Edinburgh. - 1880. - T. 10 . - S. 729 .
V. G. Vizing. På uppskattningen av den kromatiska klassen för en p-graf // lör. Diskret analys. - Novosibirsk: Matematikinstitutet vid den sibiriska grenen av USSR Academy of Sciences, 1964. - T. 3 . — S. 25–30 .
V. G. Vizing. Kritiska grafer med en given kromatisk klass // lör. Diskret analys. - Novosibirsk: Institutet för matematik vid den sibiriska grenen av USSR Academy of Sciences, 1965. - V. 5 . — S. 9–17 .

Länkar

Bevis för Vizings teorem vid PlanetMath .