Gráfok színezése

A MathWikiből
(Változatok közti eltérés)
12. sor: 12. sor:
 
Egy grafnal gyakori kerdes, hogy minimalisan hany szin kell ahhoz, hogy "jol" kitudjuk szinezni a graf csucsait. Ezt a szamot nevezzuk a kromatikus szamnak es <math>\chi(G)</math>-vel jeloljuk.
 
Egy grafnal gyakori kerdes, hogy minimalisan hany szin kell ahhoz, hogy "jol" kitudjuk szinezni a graf csucsait. Ezt a szamot nevezzuk a kromatikus szamnak es <math>\chi(G)</math>-vel jeloljuk.
  
<math>\chi(G)</math>-nek nehany tulajdonsaga:
+
 
 +
====<math>\chi(G)</math>-nek nehany tulajdonsaga:====
  
 
<math>\chi(G) = 1</math> akkor es csak akkor ha graf fuggetlen pontokbol all (eleket nem tartalmaz)
 
<math>\chi(G) = 1</math> akkor es csak akkor ha graf fuggetlen pontokbol all (eleket nem tartalmaz)

A lap 2007. április 29., 23:57-kori változata

A gráfelméletben, gráfok színezésének nevezzük azt, amikor színeket (vagy számokat) rendelünk egy gráf külön részeihez. Ezek alatt a részek alatt csúcsokat, éleket, vagy lapokat értünk.

A leggyakoribb a csúcsok színezésének a problémája, ugyanis a másik két esetet is tudjuk csúcsszínezésként vizsgálni: egy gráf élszínezése megfelel az élgráfjának a csucsszinezesevel, es egy graf lapszinezese megfelel a graf dualisanak a csucsszinezesevel.

Egy grafban azt nevezzuk egy "jo" csucsszinezesnek, amikor ket szomszedos csucs (ket csucs amely kozott fut el) kulonbozo szinu.

Nagyon sok megoldatlan kerdes van a grafok szinezese teren, viszont szamtalan erdekes hasznalata is van a grafszinezesnek. Peldaul az ismert Sudoku jatekot is lehet egy grafnak tekinteni, ahol a sorokat, oszlopokat, es 3x3-as negyzeteket klikkeknek vesszuk.


Tartalomjegyzék

Kromatikus Szam

Egy grafnal gyakori kerdes, hogy minimalisan hany szin kell ahhoz, hogy "jol" kitudjuk szinezni a graf csucsait. Ezt a szamot nevezzuk a kromatikus szamnak es χ(G)-vel jeloljuk.


χ(G)-nek nehany tulajdonsaga:

χ(G) = 1 akkor es csak akkor ha graf fuggetlen pontokbol all (eleket nem tartalmaz)

χ(G) = 2 ha G paros graf

χ(G) \geq 3 ha G tartalmaz paratlan kort.

χ(G) \geq ω(G) (ahol ω(G) G klikkszamat jeloli)

Ha χ(G) = ω(G) akkor a graf perfekt.

χ(G) \leq Δ(G) + 1 (ahol Δ(G) G maximalis fokszamat jeloli)

χ(G) \leq Δ(G) ha G nem teljes graf es nem paratlan hosszu kor (ld. Brooks tetelet)

χ(Kn) = n ahol Kn az n csucsu teljes grafot jeloli.


Egy grafnak az elkromatikus szama az a minimalis ertek, ahany szinnel ki tudjuk ugy szinezni a graf eleit, hogy tetszoleges ket el, melynek egy kozos csucs a vegpontja, ne legyen azonos szinu. Az elkromatikus szamot χe(G)-vel jeloljuk.


Brooks tétel

Ha G egy egyszeru, osszefuggo, nem teljes graf es nem paratlan hosszusagu kor, akkor χ(G) \leq Δ(G), ahol Δ(G) G maximalis fokszamat jeloli.

Bizonyitas:

Δ(G) = 2 -re nyilvanvalo az allitas, ugyanis ha a maximalis fokszam 2, akkor vagy egy kort, vagy egy utat kapunk. Egy ut vagy egy paros kor eseteben 2 szinnel ki tudjuk szinezni a grafot, es ha a kor paratlan hosszusagu akkor csak harommal.

Most mar feltehetjuk hogy Δ(G)  \geq 3. Csucsszamra valo indukcioval bizonyitjuk az allitast.

Elso lepesben azt latjuk be, hogy eleg ketszeresen osszefuggo grafokat vizsgalnunk. Indirekt tegyuk fel hogy nem ketszeresen osszefuggo a vizsgalando grafunk, ami azt jelenti hogy letezik x pont melyet elhagyva legalabb ket komponensre esik szet a grafunk. Ha pontosan ket komponensre esik szet, akkor minket komponensbe visszaillesztve x-et, nevezzuk ezeket a komponenseket G1 es G2-nek. Ha tobb mint ket komponensre esik szet, akkor maradjon G1 tovabbra is egy komponens es G2 meg legyen az osszes tobbi komponens es x unioja: G2 = (G \ G1) \cup {x}. A ket komponensben minden csucs fokszama ugyanannyi marad, csak x fokszama csokken. Tehat tovabbra sem lesz egyik fokszam negyobb mint Δ(G) viszont x feltetlenul kisebb lesz mindket komponensben Δ(G)-nel. Ebbol kovetkezik, hogy egyik komponens sem lehet Δ(G) + 1 pontu teljes graf. Tehat, az indukcios feltevesunk miatt, mindket komponenes kiszinezheto Δ(G) szinnel, es ha x-et mindket komponensben ugyanolyan szinure valasztjuk, akkor ha ujra "osszerakjuk" a grafot akkor az eredeti grafunknak egy Δ(G) szinnel valo jo szinezeset kapjuk.

Masodik lepesben pedig azt igazoljuk, hogy eleg haromszorosan osszefuggo grafokat neznunk. Ismet indirekt tegyuk fel hogy egy x es y pont elhagyasaval szetesik a grafunk G1 es G2-re. Vegezzuk el ugyanazt az eljarast mint az elso lepesben. Itt csak akkor van gond, ha az egyik komponens minden szinezese olyan hogy x es y egyforma szinu, es a masik komponens minden szinezesenel x es y kulonbozo szinu. Ebben az esetben nem tudjuk ujra "osszerakni" a grafunkat. Ebben az esetben tekintsuk a G1 es G2 komponenst es mindkettoben huzzunk be x es y kozott egy elt. Igy x es y fokszama tovabbra is legfeljebb Δ(G) marad, vagyis az indukcios felteves miatt vagy mindket komponens kiszinezheto Δ(G) szinnel, vagy legalabb az egyik komponensunk egy Δ(G) + 1 csucsu teljes graf. Ha szinezheto mindketto Δ(G) szinnel, akkor mindket komponensben kulonbozo szinu x es y, tehat "ossze tudjuk illeszteni" a ket komponenst es keszen vagyunk. Ha pedig az egyik komponensunk egy Δ(G) + 1 pontu teljes graf, akkor ebben a komponensben x-nek es y-nak is csak egy szomszedja volt a masik komponensben. Jeloljuk ezeket x' es y'-vel. Ha most elvesszuk mondjuk az x es y' csucsot az eredeti grafukbol, akkor ismet ket reszre esik a grafunk. Ha ezzel a ket ponttal vegezzuk el az elobbi algoritmust akkor nem kapunk olyan komponenst ami teljes graf, tehat megkapjuk a graf egy Δ(G) szinnel valo jo szinezeset.

Innentol mar csak haromszorosan osszefuggo grafokra kell bizonyitanunk az allitast. Legyenek v1,v2,vn olyan csucsi G-nek, hogy v1 es vn kozott fut el, v2 es vn kozott is fut el, viszont v1 es v2 kozott nem fut el (mivel G nem teljes graf es osszefuggo, ezert ilyen csucsokat minden esetben talalunk). Jeloljuk a graf tobbi pontjat a kovetkezokeppen: v3,v4,...,vn − 1 es minden pontnak legyen nagyobb indexu szomszedja is. Ha most elvesszuk a grafbol a v1 es v2 csucsokat akkor G tovabbra is osszefuggo marad, hiszen haromszorosan osszefuggo volt. Ennek a grafnak tekintsuk egy feszitofajat. Egy feszitofanak legalabb ket elsofoku pontja van, tehat lesz elsofoku pontja vn-en kivul. Legyen ez a csucsunk v3. Tehat most elvehetjuk v1, v2, es v3-at a grafbol es osszefuggo marad, es most ennek a grafnak tekintjuk a feszitofajat, es hasonloan kapjuk v4-et.

Az utolso lepesben mar csak meg kell adnunk egy megfelelo szinezest Δ(G) szinnel: Szinezzuk v1-et es v2-ot egyforma szinure. A tobbi csucsot indexuk szerint sorban szinezzuk ki moho modon: vi-hez mindig talalunk majd szabad szint, mert ennek a csucsoknak mindig csak a kisebb indexu csucsat szineztuk meg ki es ebbol kevesebb van mint Δ(G). Csak vn-nek lehet Δ(G) szomszedja, ezek kozott viszont ketto (v1 es v2) mar egyforma szinu. Ezzel igazoltuk az allitast.

Vizing tétel

Ha G egyszeru graf, akkor χe(G) \leq Δ(G) + 1

Bizonyitas:

A bizonyitasban megmutatjuk, hogy minden esetben ki tudjuk szinezni a graf eleit Δ(G) szinnel. Kezdjuk el szinezni a grafot, es tegyuk fel, hogy egy x es y1 pontok kozotti elet meg nem szineztunk ki. A graf minden v csucsahoz rendeljunk egy c(v) szint ugy, hogy c(v) azt a szint jelolje ami meg nem szerepel az egyik v-bol kiindulo elen sem. Ilyen azert lesz mindig, mert egy csucsbol legfeljebb Δ(G) el indulhat ki. Ha c(x) = c(y1) akkor ezzel a c(x) szinnel kiszinezhetjuk az x es y1 kozott futo elet.

Tegyuk fel, hogy c(x) \neq c(y1). Ekkor, ha x-bol nem indul ki c(y1) szinu el, akkor az x es y1 kozott futo elet kiszinezhetjuk ezzel a szinnel. Egyebkent, tegyuk fel hogy x es x egy y2 szomszedja kozott futo el szine c(y1). Most, ha x-bol nem indul ki c(y2) szinu el, akkor ezzel a szinnel szinezzuk az x,y2 elet, es ekkor mar nem indul ki x-bol c(y1) szinu el. Egyebkent feltehetjuk, hogy x es egy y3 csucs kozotti el szine c(y2), es folytatjuk az elozo modon az algoritmust az y4, y5, stb. pontokkal.

Csak egy esetben nem tudjuk folytatni az algoritmust: ha talalunk egy olyan n-t, hogy az x es yn kozottti el szine c(yn − 1), de egy j (1 \leq j < n) indexre c(yn) = c(yj). Ebben az esetben tekintsuk G-nek azt a reszgrafjat, pontosan azok az elek szerepelnek, melyek G-ben c(x) vagy c(yn) szinuek. Ebben a grafban Δ = 2, x-bol nem indul ki c(x) szinu el, es yn es yj-bol pedig nem indul ki c(yn) szinu el. Ez azt jelenti, hogy ennek a harom pontnak a fokszama maximum 1, es x yj vagy yn-tol kulonbozo komponensben van (mivel hogy a graf izolalt pontokbol, utakbol, es korokbol allhat a maximalis fokszam miatt). Csereljuk fel az elek szinet abban a komponensben, melyben x nem talalhato, viszont yj vagy yn igen. Ha peldaul yj volt mas komponensben, akkor elertuk hogy c(yj) = c(x). Most mar az x es yj kozotti elet szinezhetjuk c(x)-szel, az x,yj − 1 el szinet c(yj − 1) − el, es igy tovabb amig a vegen x,y1-et c(y1)-el szinezzuk. Ezzel egy jo szinezest kaptunk, es bebizonyitottuk az allitast.

Személyes eszközök