Vizings teorem

Vizings sætning er en erklæring om grafteori , ifølge hvilken kanterne af enhver simpel urettet graf kan farves i et antal farver, højst én større end den maksimale grad af grafens hjørner. Da der altid er farver nok, kan alle urettede grafer opdeles i to klasser - grafer af "første klasse", som der er nok farver til, og "anden klasse", for hvilke farver er nødvendige. $\Delta$ $\Delta +1$ $\Delta$ $\Delta +1$

Resultatet blev etableret af Vadim Vizing i 1964 .

Eksempler

Hvis , er der ingen tilstødende kanter i grafen, og kanterne kan farves i samme farve. Alle grafer med tilhører således den første klasse. $\Delta =1$ $G$ $\Delta (G)=1$

Hvis , skal grafen være en usammenhængende forening af stier og cyklusser . Hvis alle cyklusser er lige, kan deres kanter farves i to farver, skiftende farver på skift og passere langs hver cyklus. Men hvis der er mindst én ulige cyklus, kan dens kanter ikke være 2-farvede. En graf c hører således til den første klasse, hvis og kun hvis den er todelt . $\Delta =2$ $G$ $\Delta =2$

For multigrafer holder Vizings teorem generelt ikke. For eksempel har multigrafen dannet ved at fordoble hver kant af en trekant en maksimal grad på fire, men kanterne på denne graf kan ikke farves med mindre end seks farver.

Klassifikation af grafer

Nogle forfattere har givet yderligere betingelser for, at nogle grafer hører til den første eller anden klasse, men der er ingen fuldstændig klassificering. For eksempel, hvis toppunkterne med maksimal grad i grafen danner et uafhængigt sæt , eller mere generelt, hvis den genererede subgraf for dette sæt toppunkter er en skov, så vil den tilhøre den første klasse [1] . $\Delta$ $G$ $G$

Erdős og Wilson [2] viste, at næsten alle grafer tilhører den første klasse. Så lad i modellen af tilfældige Erdős-Rényi grafer , hvor alle grafer med toppunkter er lige sandsynlige, angive sandsynligheden for, at grafen med toppunkter tilhører den første klasse. Derefter tenderer mod enhed, som den tenderer mod uendelighed. Senere udviklede mere subtile skøn over hastigheden af stræben efter enhed [3] . $n$ $p(n)$ $n$ $p(n)$ $n$ $p(n)$

Plane grafer

Vizing [4] viste, at en plan graf tilhører den første klasse, hvis dens maksimale grad er mindst otte. Han bemærkede dog, at der for en maksimal grad på to til fem er andenklasses plane grafer. For grader to er enhver ulige cyklus sådan en graf, og for grader tre, fire og fem kan sådanne grafer konstrueres ud fra regulære polytoper ved at erstatte kanter på en bane af par af tilstødende kanter.

Vizings formodning om plane grafer [4] siger, at alle simple plane grafer med maksimal grad seks og syv tilhører den første klasse, hvilket lukker de resterende muligheder. Det blev fastslået i 2001 [5] at alle plane grafer med maksimal grad syv tilhører den første klasse. Det er således kun sagen med den maksimale effekt på seks, der er tilbage i tvivl. Denne formodning giver baggrunden for den samlede farveformodning .

Plane grafer af anden klasse, bygget af regulære polytoper ved at spalte kanter, er ikke regelmæssige - de har både toppunkter af anden orden og toppunkter af højere orden. Firefarvesætningen om farvning af hjørnerne af en plan graf svarer til udsagnet om, at enhver 3-regulær broløs graf tilhører den første klasse [6] (denne udsagn er sand i lyset af beviset for firefarvet teorem).

Grafer på ikke-plane overflader

I 1969 formodede Branko Grünbaum , at enhver 3-regulær graf, der har en polyhedral indlejring i en hvilken som helst todimensional orienteret manifold , såsom en torus , skal tilhøre den første klasse. I denne sammenhæng betyder en polytopindlejring en grafindlejring , således at enhver resulterende grafflade er topologisk ækvivalent med en disk, og sådan at den dobbelte graf er enkel, uden sløjfer eller flere adjacens. Hvis dette var sandt, ville det være en generalisering af firefarvesætningen, der, som Tate viste, svarer til at sige, at enhver 3-regulær graf, for hvilken der er en polytopindlejring i kuglen, er i første klasse. Men i 2009 [7] blev det vist, at formodningen ikke er sand, ved at finde snarks , der har en indlejring i form af polyedre i orienterede overflader af høj slægt . Ud fra denne konstruktion viste han også, at det er et NP-komplet problem at afgøre, om en graf med en polytopindlejring hører til den første klasse [8] .

Algoritmer

I 1992 [9] beskrev en algoritme til polynomisk tidsfarvning af enhver graf ved hjælp af farver, hvor er den maksimale grad af grafen. Algoritmen bruger således det optimale antal farver til grafer af anden klasse, og bruger højst én ekstra farve til alle grafer. Algoritmen bruger den samme strategi som det originale bevis for Vizings sætning – algoritmen starter med en farveløs graf og søger sekventielt efter farvelægningsbaner, så en kant mere er inkluderet i farvelægningen. $\Delta +1$ $\Delta$

Beskrivelsen af algoritmen bruger udtrykkene "fan", "fan rotation" og " -path", introduceret af forfatterne af algoritmen [10] , samt følgende konvention: en farve er fri ved et toppunkt , hvis der er ingen farvefarvede kanter , der falder ind i toppunktet . Algoritmen udfører følgende trin: $cd$ $d$ $w$ $d$ $w$

For hver ufarvet kant i en delvist farvet graf konstrueres en sekvens - den maksimale vifte. $UV$ $\venstre\langle v,...,l\højre\range$
- For hvert farvepar , hvor er farven fri ved toppunktet og er farven fri ved , tegnes farverne på -stien. $c, d$ $c$ $u$ $d$ $l$ $cd$
- Et vertex er valgt , så det er en delstreng og ikke bruges i . $w$ $\venstre\langle v,...,w\højre\rangle$ $\venstre\langle v,...,l\højre\range$ $d$ $w$
- Ventilatoren "drejer", er malet i farve . $\venstre\langle v,...,w\højre\rangle$ $ww$ $d$

En vifte er en sekvens af hjørner med følgende egenskaber: $\left\langle v_{0},...,v_{r}\right\rangle$

alle toppunkter er naboer til toppunktet og $u$ $v_{0}=v$
kanten er malet i en farve , der ikke blev brugt i hjørnerne $u\,v_{k+1}$ $d_{k}$ $\left\langle v_{0},\ldots ,v_{k}\right\rangle$

Ventilatoren kan drejes , dvs. kanternes farver kan erstattes med kanternes farver , og denne permutation af farver krænker ikke farven af grafen. ${\displaystyle uv_{k))$ $uv_{k+1}$

$cd$ -sti er den maksimale sekvens af kanter, der starter ved , og hver kant er farvet ved eller . At vende farverne på denne kæde betyder udskiftning med og med . $u$ $c$ $d$ $c$ $d$ $d$ $c$

Alle operationer, der bruges i algoritmen, ødelægger ikke farven på grafen, og efter at have vendt farverne på -stien, eksisterer den underkæde, der er beskrevet i algoritmen. $cd$

Ved at bruge en simpel datastruktur til at gemme farverne, der bruges ved et toppunkt, kan hele trin i algoritmen fuldføres i tid , hvor er antallet af hjørner i grafen. Da hvert trin skal gentages for alle buer, vil den samlede tid være . $På)$ $n$ $m$ $O(mn)$

I et upubliceret blad i 1985 [11] hed det, at det er muligt at finde en farvelægning i tide . $O(m{\sqrt n}\log n)$

Historie

Det menes [12] [13] at Vizings arbejde var inspireret af Shannons sætning [14] , som viser, at multigrafer kan farves ved brug af de fleste farver. Der er også en opfattelse af, at Vizing havde problemer med offentliggørelsen af resultatet (først offentliggjort i tidsskriftet "Discrete Analysis", udgivet før 1991 af Institut for Matematik fra den sibiriske afdeling af USSR Academy of Sciences , som vestlige forfattere kalder " lidt kendt" [12] ). ${\tfrac {3}{2}}\Delta$

Se også

Brooks' sætning , der relaterer vertexfarvning til maksimal grad.

Noter

↑ 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 .
↑ Algoritmebeskrivelse taget fra en artikel af Joachim Breitner. Beviser Vizings sætning med Rodin. – 2011.
↑ Gabow et al., 1985 .
↑ 12 Gutin, Toft, 2000 .
↑ Soifer, 2008 .
↑ Shannon, 1949 .

Litteratur

K. Appel, W. Haken. Hvert plan kort er fire farverigt // Bulletin of the American Mathematical Society. - 1976. - T. 82 , no. 5 . — S. 711–712 . - doi : 10.1090/S0002-9904-1976-14122-5 .
Paul Erdős, Robin J. Wilson. Bemærk om det kromatiske indeks for næsten alle grafer // Journal of Combinatorial Theory . - 1977. - T. 23 , no. 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. Kantfarve tilfældige grafer // Journal of Combinatorial Theory . - 1988. - T. 45 , no. 2 . — S. 135–149 . - doi : 10.1016/0095-8956(88)90065-2 .
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algoritmer til grafer til kantfarvning. - Tohoku University, 1985. - (Teknisk rapport TRECIS-8501).
Gregory Gutin, Bjarne Toft. Interview med Vadim G. Vizing // European Mathematical Society Newsletter. - 2000. - T. 38 , no. december . — S. 22–23.
Martin Kochol. Proceedings fra American Mathematical Society. - 2009. - T. 137. - S. 1613-1619.
Martin Kochol. Kompleksiteten af 3-kantsfarvning i klassen af kubiske grafer med en polyedrisk indlejring i en orienterbar overflade // Diskret anvendt matematik. - 2010. - T. 158 , no. 16 . - S. 1856-1860 . - doi : 10.1016/j.dam.2010.06.019 .
Et konstruktivt bevis på Vizings sætning // Information Processing Letters . - 1992. - T. 41 , no. 3 . — S. 131–133 . - doi : 10.1016/0020-0190(92)90041-S .
Daniel P. Sanders, Yue Zhao. Plane grafer med maksimal grad syv er klasse I // Journal of Combinatorial Theory . - 2001. - T. 83 , no. 2 . — S. 201–212 . - doi : 10.1006/jctb.2001.2047 .
Claude Shannon. En sætning om farvning af linjerne i et netværk // J. Math. Fysik. - 1949. - T. 28 . — S. 148–151 .
Alexander Soifer. Den matematiske malebog. - 2008. - S. 136-137 . — ISBN 978-0-387-74640-1 .
PG Tait. Bemærkninger til farvelægninger af kort // Proc. R. Soc. Edinburgh. - 1880. - T. 10 . - S. 729 .
V. G. Vizing. På estimat af den kromatiske klasse af en p-graf // Lør. Diskret analyse. - Novosibirsk: Institut for Matematik i den sibiriske gren af USSR Academy of Sciences, 1964. - T. 3 . — S. 25–30 .
V. G. Vizing. Kritiske grafer med en given kromatisk klasse // Lør. Diskret analyse. - Novosibirsk: Institut for Matematik i den sibiriske gren af USSR Academy of Sciences, 1965. - V. 5 . — S. 9–17 .