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:

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

BizonyításSzerkesztés

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

Tegyük fel, hogy      . Ekkor, ha  -ből nem indul ki   színű él, akkor az   és   között futó élet kiszínezhetjük ezzel a színnel. Egyébként, tegyük fel, hogy   és   egy   szomszédja között futó él színe  . Most, ha  -ből nem indul ki   színű él, akkor ezzel a színnel színezzük az   élet, és ekkor már nem indul ki  -ből   színű él. Egyébként feltehetjük, hogy   és egy   csúcs közötti él színe  , és folytatjuk az előző módon az algoritmust az  ,  , stb. pontokkal.

Csak egy esetben nem tudjuk folytatni az algoritmust: ha találunk egy olyan  -t, hogy az   és   közötti él színe  , de egy   (1     <  ) indexre   =  . Ebben az esetben tekintsük  -nek azt a részgráfját, melyben pontosan azok az élek szerepelnek, melyek  -ben   vagy   színűek. Ebben a gráfban   = 2,  -ből nem indul ki   színű él, és   és  -ből pedig nem indul ki   színű él. Ez azt jelenti, hogy ennek a három pontnak a fokszáma maximum 1, és     vagy  -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   nem található, viszont   vagy   igen. Ha például   volt más komponensben, akkor elértük hogy   =  . Most már az   és   közötti élet színezhetjük  -szel, az   él színét  -gyel, és így tovább amíg a végén  -et  -gyel színezzük. Ezzel egy jó színezést kaptunk, és bebizonyítottuk az állítást.

HivatkozásokSzerkesztés

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