Vizing-tétel – Wikipédia
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ás
[szerkeszté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ások
[szerkesztés]- Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006. p. 85,86.