Vizing-tétel

A Vizing-tétel alsó és felső korlátot ad egy egyszerű gráf élkromatikus számára. A tételt Vagyim Georgijevics Vizing 1964-ben bizonyította be.

A tétel szerint egy egyszerű gráf élkromatikus száma legfeljebb eggyel nagyobb a maximális fokszámánál, azaz ha a gráf minden csúcsában k-nál kevesebb él találkozik, akkor ki tudjuk színezni az éleit legfeljebb k színnel. Képlettel:

${\displaystyle \Delta (G)\leq \chi _{e}(G)\leq \Delta (G)+1}$

Az irányítatlan gráfok két osztályba particionálhatók: melyek színezéséhez ${\displaystyle \Delta }$ szín elegendő, azok az „első csoportba” sorolt gráfok (class one), melyekhez ${\displaystyle \Delta +1}$ szín szükséges, azok a „második csoportba” sorolt gráfok (class two).

Bizonyítás

A bizonyításban megmutatjuk, hogy minden esetben ki tudjuk színezni a gráf éleit ${\displaystyle \Delta (G)+1}$ színnel. Kezdjük el színezni a gráfot, és tegyük fel, hogy egy ${\displaystyle x}$ és ${\displaystyle y_{1}}$ pontok közötti élet még nem színeztünk ki. A gráf minden ${\displaystyle v}$ csúcsához rendeljünk egy ${\displaystyle c(v)}$ színt úgy, hogy ${\displaystyle c(v)}$ azt a színt jelölje ami még nem szerepel az egyik ${\displaystyle v}$-ből kiinduló élen sem. Ilyen azért lesz mindig, mert egy csúcsból legfeljebb ${\displaystyle \Delta (G)}$ él indulhat ki. Ha ${\displaystyle c(x)}$ = ${\displaystyle c(y_{1})}$ akkor ezzel a ${\displaystyle c(x)}$ színnel kiszínezhetjük az ${\displaystyle x}$ és ${\displaystyle y_{1}}$ között futó élet.

Tegyük fel, hogy ${\displaystyle c(x)}$ ${\displaystyle \neq }$ ${\displaystyle c(y_{1})}$. Ekkor, ha ${\displaystyle x}$-ből nem indul ki ${\displaystyle c(y_{1})}$ színű él, akkor az ${\displaystyle x}$ és ${\displaystyle y_{1}}$ között futó élet kiszínezhetjük ezzel a színnel. Egyébként, tegyük fel, hogy ${\displaystyle x}$ és ${\displaystyle x}$ egy ${\displaystyle y_{2}}$ szomszédja között futó él színe ${\displaystyle c(y_{1})}$. Most, ha ${\displaystyle x}$-ből nem indul ki ${\displaystyle c(y_{2})}$ színű él, akkor ezzel a színnel színezzük az ${\displaystyle {x,y_{2}}}$ élet, és ekkor már nem indul ki ${\displaystyle x}$-ből ${\displaystyle c(y_{1})}$ színű él. Egyébként feltehetjük, hogy ${\displaystyle x}$ és egy ${\displaystyle y_{3}}$ csúcs közötti él színe ${\displaystyle c(y_{2})}$, és folytatjuk az előző módon az algoritmust az ${\displaystyle y_{4}}$, ${\displaystyle y_{5}}$, stb. pontokkal.

Csak egy esetben nem tudjuk folytatni az algoritmust: ha találunk egy olyan ${\displaystyle n}$-t, hogy az ${\displaystyle x}$ és ${\displaystyle y_{n}}$ közötti él színe ${\displaystyle c(y_{n-1})}$, de egy ${\displaystyle j}$ (1 ${\displaystyle \leq }$ ${\displaystyle j}$ < ${\displaystyle n}$) indexre ${\displaystyle c(y_{n})}$ = ${\displaystyle c(y_{j})}$. Ebben az esetben tekintsük ${\displaystyle G}$-nek azt a részgráfját, melyben pontosan azok az élek szerepelnek, melyek ${\displaystyle G}$-ben ${\displaystyle c(x)}$ vagy ${\displaystyle c(y_{n})}$ színűek. Ebben a gráfban ${\displaystyle \Delta }$ = 2, ${\displaystyle x}$-ből nem indul ki ${\displaystyle c(x)}$ színű él, és ${\displaystyle y_{n}}$ és ${\displaystyle y_{j}}$-ből pedig nem indul ki ${\displaystyle c(y_{n})}$ színű él. Ez azt jelenti, hogy ennek a három pontnak a fokszáma maximum 1, és ${\displaystyle x}$ ${\displaystyle y_{j}}$ vagy ${\displaystyle y_{n}}$-től különböző komponensben van (mivelhogy a gráf izolált pontokból, utakból és körökből állhat a maximális fokszám miatt). Cseréljük fel az élek színét abban a komponensben, melyben ${\displaystyle x}$ nem található, viszont ${\displaystyle y_{j}}$ vagy ${\displaystyle y_{n}}$ igen. Ha például ${\displaystyle y_{j}}$ volt más komponensben, akkor elértük hogy ${\displaystyle c(y_{j})}$ = ${\displaystyle c(x)}$. Most már az ${\displaystyle x}$ és ${\displaystyle y_{j}}$ közötti élet színezhetjük ${\displaystyle c(x)}$-szel, az ${\displaystyle {x,y_{j-1}}}$ él színét ${\displaystyle c(y_{j-1})}$-gyel, és így tovább amíg a végén ${\displaystyle {x,y_{1}}}$-et ${\displaystyle c(y_{1})}$-gyel színezzük. Ezzel egy jó színezést kaptunk, és bebizonyítottuk az állítást.

Hivatkozások

• Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006. p. 85,86.