Teorema lui Vizing

Teorema lui Vizing este o afirmație a teoriei grafurilor , conform căreia muchiile oricărui graf simplu nedirecționat pot fi colorate într-un număr de culori, cel mult cu una mai mare decât gradul maxim al vârfurilor grafului. Deoarece există întotdeauna suficiente culori, toate graficele nedirecționate pot fi împărțite în două clase - grafice din „prima clasă”, pentru care există suficiente culori și „a doua clasă”, pentru care sunt necesare culori. $\Delta$ $\Delta +1$ $\Delta$ $\Delta +1$

Rezultatul a fost stabilit de Vadim Vizing în 1964 .

Exemple

Dacă , nu există muchii adiacente în grafic, iar muchiile pot fi colorate în aceeași culoare. Astfel, toate graficele cu aparțin primei clase. $\Delta =1$ $G$ $\Delta (G)=1$

Dacă , graficul trebuie să fie o uniune disjunsă de căi și cicluri . Dacă toate ciclurile sunt pare, marginile lor pot fi colorate în două culori, schimbându-și culorile pe rând, trecând de-a lungul fiecărui ciclu. Cu toate acestea, dacă există cel puțin un ciclu impar, marginile acestuia nu pot fi bicolore. Astfel, un grafic c aparține primei clase dacă și numai dacă este bipartit . $\Delta =2$ $G$ $\Delta =2$

Pentru multigrafe , în general, teorema lui Vizing nu este valabilă. De exemplu, multigraful format prin dublarea fiecărei margini a unui triunghi are un grad maxim de patru, dar marginile acestui grafic nu pot fi colorate cu mai puțin de șase culori.

Clasificarea graficelor

Unii autori au dat condiții suplimentare pentru ca unele grafice să aparțină clasei întâi sau a doua, dar nu există o clasificare completă. De exemplu, dacă vârfurile de grad maxim din grafic formează o mulțime independentă sau, mai general, dacă subgraful generat pentru această mulțime de vârfuri este o pădure, atunci va aparține clasei I [1] . $\Delta$ $G$ $G$

Erdős și Wilson [2] au arătat că aproape toate graficele aparțin primei clase. Deci, în modelul graficelor aleatoare Erdős-Rényi , în care toate graficele cu vârfuri sunt la fel de probabile, să notăm probabilitatea ca graficul cu vârfuri să aparțină primei clase. Apoi tinde spre unitate, așa cum tinde spre infinit. Mai târziu au dezvoltat estimări mai subtile ale ratei eforturilor spre unitate [3] . $n$ $p(n)$ $n$ $p(n)$ $n$ $p(n)$

Grafice plane

Vizing [4] a arătat că un graf plan aparține primei clase dacă gradul său maxim este de cel puțin opt. Cu toate acestea, el a observat că pentru un grad maxim de doi până la cinci, există grafice plane de clasa a doua. Pentru gradele doi, orice ciclu impar este un astfel de grafic, iar pentru gradele trei, patru și cinci, astfel de grafice pot fi construite din politopuri obișnuite prin înlocuirea muchiilor pe o cale de perechi de muchii adiacente.

Conjectura lui Vizing asupra grafurilor plane [4] afirmă că toate grafurile plane simple cu gradul maxim șase și șapte aparțin primei clase, ceea ce închide posibilitățile rămase. Sa stabilit în 2001 [5] că toate graficele plane cu gradul maxim șapte aparțin primei clase. Astfel, rămâne în discuție doar cazul cu puterea maximă de șase. Această presupunere oferă fundalul pentru conjectura totală de colorare .

Graficele plane din clasa a doua, construite din politopuri regulate prin împărțirea muchiilor, nu sunt regulate - au atât vârfuri de ordinul doi, cât și vârfuri de ordin superior. Teorema în patru culori privind colorarea vârfurilor unui graf plan este echivalentă cu afirmația că orice graf fără punte cu 3 regulate aparține primei clase [6] (această afirmație este adevărată având în vedere demonstrația cu patru culori). teorema).

Grafice pe suprafețe neplane

În 1969 , Branko Grünbaum a presupus că orice graf cu 3 regulate care are o încorporare poliedrică în orice varietate orientată bidimensional , cum ar fi un tor , trebuie să aparțină primei clase. În acest context, o încorporare politopică înseamnă o încorporare a graficului astfel încât orice față a graficului rezultată este echivalentă topologic cu un disc și astfel încât graficul dual să fie simplu, fără bucle sau adiacente multiple. Dacă acest lucru ar fi adevărat, ar fi o generalizare a teoremei celor patru culori, care, așa cum a arătat Tate, este echivalentă cu a spune că orice graf cu 3 regulate pentru care există un politop încorporat în sferă este în prima clasă. Totuși, în 2009 [7] s-a demonstrat că conjectura nu este adevărată prin găsirea de snark -uri care au o înglobare sub formă de poliedre în suprafețe orientate de gen înalt . Pe baza acestei construcții, el a arătat, de asemenea, că determinarea dacă un graf cu încorporare politopică aparține primei clase este o problemă NP-completă [8] .

Algoritmi

În 1992, [9] a descris un algoritm pentru colorarea în timp polinomial a oricărui grafic folosind culori, unde este gradul maxim al graficului. Astfel, algoritmul folosește numărul optim de culori pentru graficele din clasa a doua și folosește cel mult o culoare suplimentară pentru toate graficele. Algoritmul folosește aceeași strategie ca și demonstrația originală a teoremei lui Vizing - algoritmul începe cu un grafic incolor și caută secvențial căi de colorare, astfel încât încă o muchie să fie inclusă în colorare. $\Delta +1$ $\Delta$

Descrierea algoritmului folosește termenii „ventilator”, „rotație ventilator” și „ -path”, introduși de autorii algoritmului [10] , precum și următoarea convenție: o culoare este liberă la un vârf dacă există fără margini colorate incidente la vârf . Algoritmul efectuează următorii pași: $cd$ $d$ $w$ $d$ $w$

Pentru fiecare margine necolorată dintr-un grafic parțial colorat, se construiește o secvență - ventilatorul maxim. $UV$ $\left\langle v,...,l\right\rangle$
- Pentru fiecare pereche de culori , unde este culoarea liberă la vârf și este culoarea liberă la , sunt desenate culorile căii. $c, d$ $c$ $u$ $d$ $l$ $cd$
- Un vârf este ales astfel încât să fie un subșir și să nu fie folosit în . $w$ $\left\langle v,...,w\right\rangle$ $\left\langle v,...,l\right\rangle$ $d$ $w$
- Ventilatorul „se învârte”, este vopsit în culoare . $\left\langle v,...,w\right\rangle$ $ww$ $d$

Un evantai este o succesiune de vârfuri cu următoarele proprietăți: $\left\langle v_{0},...,v_{r}\right\rangle$

toate vârfurile sunt vecine cu vârful și $u$ $v_{0}=v$
marginea este vopsită într-o culoare care nu a fost folosită în vârfuri $u\,v_{k+1}$ $d_{k}$ $\left\langle v_{0},\ldots ,v_{k}\right\rangle$

Ventilatorul poate fi rotit , adică culorile marginilor pot fi înlocuite cu culorile marginilor , iar această permutare a culorilor nu încalcă colorarea graficului. $uv_{k)$ $uv_{k+1}$

$cd$ -calea este succesiunea maximă de muchii care încep la , iar fiecare muchie este colorată la sau . Inversarea culorilor acestui lanț înseamnă înlocuirea cu și cu . $u$ $c$ $d$ $c$ $d$ $d$ $c$

Toate operațiunile utilizate în algoritm nu distrug colorarea graficului, iar după inversarea culorilor căii -, sublanțul descris în algoritm există. $cd$

Folosind o structură de date simplă pentru a stoca culorile utilizate la un vârf, întregul pas al algoritmului poate fi finalizat în timp , unde este numărul de vârfuri din grafic. Deoarece fiecare pas trebuie repetat pentru toate arcurile, timpul total va fi . $Pe)$ $n$ $m$ $O(mn)$

Într-o lucrare nepublicată din 1985 [11] , se afirma că este posibil să se găsească o colorare în timp . $O(m{\sqrt n}\log n)$

Istorie

Se crede [12] [13] că lucrarea lui Vizing a fost inspirată de teorema lui Shannon [14] , care arată că multigrafele pot fi colorate folosind cel mult culori. Există, de asemenea, o opinie că Vizing a avut probleme cu publicarea rezultatului (publicat pentru prima dată în revista „Analiza discretă”, publicată înainte de 1991 de Institutul de Matematică al Filialei Siberiei a Academiei de Științe a URSS , pe care autorii occidentali o numesc „ puțin cunoscut” [12] ). ${\tfrac {3}{2}}\Delta$

Vezi și

Teorema lui Brooks , raportând colorarea vârfurilor la gradul maxim.

Note

↑ 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 .
↑ Descrierea algoritmului preluată dintr-un articol de Joachim Breitner. Demonstrarea teoremei lui Vizing cu Rodin. — 2011.
↑ Gabow și colab., 1985 .
↑ 12 Gutin, Toft, 2000 .
↑ Soifer, 2008 .
↑ Shannon, 1949 .

Literatură

K. Appel, W. Haken. Fiecare hartă plană are patru culori // Buletinul Societății Americane de Matematică. - 1976. - T. 82 , nr. 5 . — S. 711–712 . - doi : 10.1090/S0002-9904-1976-14122-5 .
Paul Erdős, Robin J. Wilson. Notă despre indicele cromatic al aproape tuturor graficelor // 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. Grafice aleatoare pentru colorarea marginilor // 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. Algoritmi pentru graficele de colorare a muchiilor. - Universitatea Tohoku, 1985. - (Raport tehnic TRECIS-8501).
Gregory Gutin, Bjarne Toft. Interviu cu Vadim G. Vizing // Buletin informativ al Societății Europene de Matematică. - 2000. - T. 38 , nr. decembrie . — P. 22–23.
Martin Kochol. Proceedings of the American Mathematical Society. - 2009. - T. 137. - S. 1613-1619.
Martin Kochol. Complexitatea colorării cu 3 muchii în clasa graficelor cubice cu încastrare poliedrică într-o suprafață orientabilă // Matematică aplicată discretă. - 2010. - T. 158 , nr. 16 . - S. 1856-1860 . - doi : 10.1016/j.dam.2010.06.019 .
O dovadă constructivă a teoremei lui Vizing // Litere de procesare a informațiilor . - 1992. - T. 41 , nr. 3 . — S. 131–133 . - doi : 10.1016/0020-0190(92)90041-S .
Daniel P. Sanders, Yue Zhao. Graficele plane de gradul maxim șapte sunt clasa I // Journal of Combinatorial Theory . - 2001. - T. 83 , nr. 2 . — S. 201–212 . - doi : 10.1006/jctb.2001.2047 .
Claude Shannon. O teoremă privind colorarea liniilor unei rețele // J. Math. Fizică. - 1949. - T. 28 . — S. 148–151 .
Alexandru Soifer. Cartea de colorat matematic. - 2008. - S. 136-137 . — ISBN 978-0-387-74640-1 .
PG Tait. Observații asupra colorațiilor hărților // Proc. R. Soc. Edinburgh. - 1880. - T. 10 . - S. 729 .
V. G. Vizing. Despre estimarea clasei cromatice a unui p-graf // Sat. Analiză discretă. - Novosibirsk: Institutul de Matematică al Filialei Siberiei a Academiei de Științe a URSS, 1964. - T. 3 . — S. 25–30 .
V. G. Vizing. Grafice critice cu o clasă cromatică dată // Sat. Analiză discretă. - Novosibirsk: Institutul de Matematică al Filialei Siberiei a Academiei de Științe a URSS, 1965. - V. 5 . — P. 9–17 .

Link -uri

Dovada teoremei lui Vizing la PlanetMath .