Zadanie_8167-12333.doc

TEÓRIA GRAFOV

Zadanie: Farbenie vrcholov a hrán

MENO: MÁRIA RICHNAVSKÁ ODBOR : H OSPODÁRSKA INFORMATIKA ŠTUDIJNÁ SKUPINA: DRUHÁ ROK: 2007/2008 OBSAH Základné pojmy Farbenie vrcholov Farbenie hrán Totálne farbenie Použitie v bežnom živote a príklady

1. Základné pojmy GRAFOM G = (V, H) nazývame usporiadanú dvojicu množín V a H, kde V je konečná množina (v našom prípade to bude množina niektorých bodov v rovine) a H je množina dvojprvkových podmnožín množiny V (v našom prípade to bude množina čiar spájajúcich dva body v rovine z množiny V). Prvky množiny V nazývame VRCHOLY grafu a prvky množiny H nazývame HRANY grafu. Vrcholy grafu spojené hranou nazývame SUSEDNÉ VRCHOLY. Nech G= (V,H) je graf alebo digraf, v ∈V, h ∈ H. Vrchol je INCIDENTNÝ s hranou h, ak je

v jedným z vrcholov hrany h. Hrany h, k ∈ H, h≠k sú vrchol.

INCIDENTNÉ,

ak majú spoločný jeden

Veta Problém zafarbiť graf minimálnym počtom farieb je NP-ťažký. 2. Farbenie vrcholov Súvislý graf nazveme N-ZAFARBITEĽNÝM, ak postačuje n farieb na zafarbenie jeho vrcholov tak, že žiadne dva susedné vrcholy nie sú zafarbené rovnakou farbou. CHROMATICKÝM ČÍSLOM grafu G nazveme prirodzené číslo

 (G )

, ktoré udáva minimálny počet farieb

 (G )

potrebných na to aby bol graf G n-zafarbiteľným. Pre chromatické číslo súvislého grafu G je

 (G )

, kde

 (G )  1  s (G )

s (G )

udáva maximálny stupeň vrcholu v grafe G. Veta Nech m je maximum zo všetkých stupňov vrcholov grafu G = (V,H) a nech |V| = n. Potom χ(G) ≤ m+1.

Dôkaz Ak n = 1, potom χ(G) = 1, m = 0. Ak n › 1 a zároveň tvrdenie vety platí pre každý graf s n-1 vrcholmi, potom v grafe G, ktorý má n vrcholov, zvolíme vrchol u minimálneho stupňa a zostrojíme G-u, t.j. vynechávame z grafu G vrchol u a hrany s ním incidentné. Najväčší zo všetkých stupňov vrcholov v grafe G-u je m alebo m-1. Podľa indukčného predpokladu je potom graf G-u (m+1)-chromatický. Nech vrcholy grafu G-u sú zafarbené každý jednou z m+1 farieb. Toto zafarbenie prenesieme na graf G tak, že vrcholu u priradíme tú farbu, ktorú nemá žiadny z jeho susedných vrcholov. Ak súvislý graf G = (V,H) nie je kompletný graf a ani nie je kružnicou nepárnej dĺžky, potom χ(G)≤m. Vety Graf G je 2-ZAFARBITEĽNÝ práve vtedy, keď neobsahuje kružnicu nepárnej dĺžky ako svoj podgraf. Graf je párny = bipartitný, ak je 2-farbiteľný. Každý strom (aspoň s 1 hranou) je 2-zafarbiteľný.

Dôkaz Náš predpoklad je: veta platí pre každý strom, ktorý má n vrcholov. Majme strom S=(V,H), ktorý má n+1 vrcholov. Vyberieme si jeden vrchol (S má minimálne 2 vrcholy stupňa 1). Ak ho z S odoberieme a odoberieme aj hranu s ním incidentnú, tento strom môžeme zafarbiť 2 farbami. Takéto zafarbenie prenesieme na pôvodný strom S, pod podmienkou, že odobratý vrchol zafarbíme inou farbou akou je zafarbený susedný. Veta Nech je najväčší zo stupňov vrcholov grafu G rovný d. • Ak d≠2 graf G neobsahuje kompletný podgraf s d+1 vrcholmi, tak

≤d

 (G ) (inak

=d+1.

 (G ) •

Ak d=2 a graf G neobsahuje kružnicu nepárnej dĺžky, tak

=2, inak

 (G ) =3.

 (G ) Veta

Každý rovinný graf je 5-zafarbiteľný. Hodnotu chromatického čísla grafu môžeme presne určiť pomocou tzv. chromatického polynómu. Odhad chromatického čísla grafu alebo dokonca znalosť tohto čísla v konkrétnom grafe však ešte nedávanávod, ako vrcholy grafu zafarbiť tak, aby susedné vrcholy neboli zafarbené rovnakou farbou. Preto ukážem aspoň jeden pomerne ľahký algoritmus pre farbenie grafu. Algoritmus je heuristický a je založený na skutočnosti, že je výhodné zafarbiť najskôr vrcholy s veľkým stupňom. Predpoklad: vrcholy grafu G sú označené v1, v2, . . ., vP. Zoraďme vrcholy grafu do neklesajúcej postupnosti P=(vk1, vK2, ... , vKP). Platí: deg vK1 ≥ degK2 ≥ ... ≥ degVkp HEURISTICKÝ ALGORITMUS FARBENIA GRAFOV 1. Položíme j=1 2. Nezafarbený vrchol vK1, ktorý má najmenší index i zafarbíme farbou j. Postupne vyberáme vrcholy z postupnosti P podľa rastúceho indexu i. Ak nie sú zafarbené a nie sú susedné s vrcholmi zafarbenými farbou j, tak ich touto farbou zafarbíme. 3. Ak pri farbení grafu farbou číslo j nezafarbíme všetky vrcholy grafu, ktoré ešte neboli zafarbené, tak j: = j+1 a vrátime sa na krok 2. V opačnom prípade nasleduje postup na krok 4. 4. Posledne určená hodnota j udáva odhad chromatického čísla uvažovaného grafu. Súčasne je graf zafarbený j farbami.

Postupnosť P je P= (v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11). Položme j=1. Farbou číslo 1 zafarbíme vrcholy v1, v6, v9, v10, v11. Zvýšme premennú j o jednotku, dostaneme j=2, farbou 2 zafarbíme vrcholy v2, v4, v7. Farbou číslo 3 zafarbíme vrcholy v3, v5, v8. Tým sme zafarbili všetky vrcholy grafu, chromatické číslo grafu nie je väčšie ako 3. K číslam farby nasledovne:

1-červená, 2-zelená, 3-modrá.

3. Farbenie hrán

Hranové zafarbenie je také zafarbenie, kedy hrany, ktoré sú incidentné s rovnakými vrcholmi, musia mať rôzne farby. Shannon položil úlohu: Majme elektrické zariadenia, v ktorom sú určité miesta prepojené drôtmi. Aby sme drôty vychádzajúce z určitého miesta rozlíšili, použijeme drôty rozličných farieb. Problém najmenšieho počtu farieb sa dá riešiť ako problém hranového chromatického čísla. Vizingov teorém Keď G je konečný graf bez slučiek, ktorého najväčší stupeň je r, potom r≤ χ(G) ≤r+1.

4. Totálne farbenie Definujme si totálne chromatické číslo χt(G) grafu G= (V,H). Farbíme hrany aj vrcholy. Podmienky:

➢ 2 rovnako zafarbené vrcholy nesmú byť spojené hranou ➢ Žiadne 2 rovnako zafarbené hrany neincidujú s tým istým vrcholom ➢ Žiadna hrana nesmie byť incidentná s vrcholom tej istej farby, akú má sama V(G) ∪ E(G) = S1 ∪ S2 ∪ . . . ∪ SK (V1 ∪ E1) (V2 ∪ E2). . .(VK ∪ EK) Si bolo nezávislé, neobsahovalo neincidentné prvky Existencia odhadu: χt(G) ≥ m+1, pričom m je najväčší zo všetkých stupňov vrcholov grafu G. Domnienka: G= (H,V) s maximálnym stupňom vrcholov m platí: χt(G) ≤ m+2. Ak platí táto podmienka, tak môžeme napísať m+1≤ χt(G) ≤m+2.

Χt(K5)≥5 5. Použitie v bežnom živote a príklady

✔

Rozvrhovanie skúšok na univerzite tak, aby žiaden zo študentov nemal naplánované 2 skúšky naraz. (Vrcholy sú predmety, hrana spája vrcholy len vtedy, ak existuje študent, ktorý ide na obe skúšky. Časové priradenia skúšok sú reprezentované inými farbami )

✔

Priraďovanie frekvencií (Každý vysielač je vrchol, 2 vrcholy sú spojené, ak sú vzdialené do 100 km. Priradenie kanálov zodpovedá zafarbeniu grafu, a to tak, že každá farba reprezentuje iný kanál)

✔

Uskladňovanie n nebezpečných látok, ktoré nesmú byť skladované v jednom priestore (vrcholy sú látky, 2 vrcholy sú spojené hranou, ak príslušné látky nesmú byť skladované spoločne)

✔

Indexový register (výpočet v cykle je zrýchlený, ak sú v efektívnych kompilátoroch použité premenné, ktoré sú ukladané dočasne v indexových registroch CPU namiesto v regulárnej pamäti. Čiže každý vrchol grafu reprezentuje premennú v slučke. Hrana medzi 2 vrcholmi existuje, keď im odpovedajúce premenné sú uložené v indexovom registri v rovnakom čase výpočtu. Chromatické číslo grafu dáva počet potrebných registrov)

✔

Problém nákupných tašiek 6. Príklady

Medzi príklady prikladám pojem DISKRÉTNY tento graf platí:

GRAF

, čo je množina izolovaných bodov. Pre

Veta

Diskrétny graf má chromatické číslo 1.

Príklad na strom (vysvetlenie uvedené vyššie):

Chromatické číslo grafu:

Χ=2