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.
Rezultatul a fost stabilit de Vadim Vizing în 1964 .
Dacă , nu există muchii adiacente în grafic, iar muchiile pot fi colorate în aceeași culoare. Astfel, toate graficele cu aparțin primei clase.
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 .
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.
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] .
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] .
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).
Î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] .
Î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.
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:
Un evantai este o succesiune de vârfuri cu următoarele proprietăți:
Ventilatorul poate fi rotit , adică culorile marginilor pot fi înlocuite cu culorile marginilor , iar această permutare a culorilor nu încalcă colorarea graficului.
-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 .
Toate operațiunile utilizate în algoritm nu distrug colorarea graficului, iar după inversarea culorilor căii -, sublanțul descris în algoritm există.
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 .
Într-o lucrare nepublicată din 1985 [11] , se afirma că este posibil să se găsească o colorare în timp .
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] ).