Vizing-tétel

A Wikipédiából, a szabad enciklopédiából

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:

\Delta(G)\leq \chi_e(G) \leq \Delta(G) + 1

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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

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

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

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

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