Farbenie vrcholov

Farbenie vrcholov grafu alebo vrcholové farbenie grafu je také zafarbenie vrcholov grafu, aby všetky susediace vrcholy (vrcholy spojené hranou) mali rôznu farbu. Farbenie vrcholov grafu je jedným z druhov farbenia grafu.

Matematická definícia

Definícia: Vrcholové farbenie grafu G=(V,E) je zobrazenie c: V→S také, že c(v)≠c(w) ak v a w sú susedné. Prvky množiny S sa nazývajú dostupné farby.

Hovoríme, že graf G má k-farbenie, ak pre neho existuje vrcholové farbenie c: V→{1,...,k}. Minimálne $k\in N$ také, že graf G má k-farbenie nazývame Chromatické číslo grafu G a označujeme ho χ(G).

Graf G s χ(G)=k sa nazýva k-chromatickým. Ak χ(G)≤k nazývame G k-zafarbiteľným

Definícia: Nech je daný graf G = (V, H), nech B ⊂ V. Podmnožinu B nazývame nezávislou podmnožinou množiny V, ak žiadne dva z jej vrcholov nie sú incidentné s tou istou hranou v grafe G.

Definícia: Množina B V je maximálnou nezávislou podmnožinou množiny V, ak neexistuje taká nezávislá Podmnožina B‘ množiny V, aby platilo B ⊂ B’ ⊂ V, B ≠ B’.

Existuje priama súvislosť medzi nezávislými podmnožinami vrcholov grafu a problematikou farbenia grafov. Máme nájsť minimálny počet farieb, pomocou ktorých môžeme zafarbiť vrcholy grafu tak, aby žiadna jeho hrana neincidovala s vrcholmi zafarbenými rovnakou farbou. Je zrejmé, že množina vrcholov zafarbených tou istou farbou tvorí nezávislú podmnožinu vrcholov a ide o nájdenie najmenšieho počtu nezávislých podmnožín, ktoré by pokryli všetky vrcholy grafu.

Regulárne farbenie vrcholov grafu Farbenie vrcholov grafu nazývame regulárnym, ak vrcholy incidentné s tou istou hranou majú rôzne farby.

k-chromatický graf: Graf G = (V,H) nazývame k-chromatickým ak na jeho regulárne zafarbenie stačí k rôznych farieb.

Chromatické číslo χ(G) grafu G nazývame také najmenšie číslo k, pre ktoré graf G je k-chromatickým.

Veta: Graf G =(V,H), H≠0 , má Chromatické číslo 2 práve vtedy, ak neobsahuje kružnice nepárnej dĺžky.

Dôkazy

Veta: Každý strom T s aspoň jednou hranou má χ(T)=2.

Dôkaz: Matematickou indukciou vzhľadom na počet vrcholov. Najmenší existujúci známy strom je strom s jednou hranou a dvoma vrcholmi a teda má χ(T)=2. Predpokladajme teda, že toto tvrdenie platí pre všetky stromy s n vrcholmi. Zvoľme si ľubovoľný strom T=(V,H) s n+1 vrcholmi. v každom strome sú minimálne 2 vrcholy stupňa 1. Zvoľme si jeden z nich a označme si ho x. Ak odoberieme z T vrchol x a hranu {x,y} s ním incidentnú, dostaneme strom T – x, s n vrcholmi a ten možno regulárne zafarbiť dvoma farbami. Toto zafarbenie môžeme preniesť aj na strom T, pričom vrchol x zafarbíme tou farbou, ktorou nie je zafarbený vrchol y, incidentný s vrcholom x.

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: Matematickou indukciou vzhľadom na počet vrcholov n. Pre n = 1 je tvrdenie vety zrejmé, pretože χ(G) = 1, m = 0. Nech n > 1 a nech tvrdenie vety platí pre každý graf s n-1 vrcholmi. V grafe G s n vrcholmi zvoľme vrchol u minimálneho stupňa a zostrojme G - u, t. j. vynechali sme 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 graf G - u je (m+1)-chromatický. Nech vrcholy grafu G - u sú zafarbené každý jednou z daných 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. Je to možné, pretože vrchol u má stupeň najviac m a máme m+1 farieb.

Toto tvrdenie možno ešte zlepšiť takto: Ak súvislý graf G =(V,H) nie je kompletný graf ani nie je kružnicou nepárnej dĺžky, potom χ(G) ≤ m

Aplikácie

Ak sú dva vysielače blízko seba, nemôžu používať tú istú frekvenciu, pretože by sa navzájom rušili. Rádiové frekvencie sú však obmedzeným prírodným zdrojom. Preto nemožno každému vysielaču priradiť inú frekvenciu. Modelom tejto situácie je graf G, ktorého vrcholy sú vysielače a v ktorom za incidentné vrcholy považujeme tie dvojice vysielačov, ktoré by sa pri pridelení rovnakej frekvencie rušili. Úloha prideliť danej množine vysielačov čo najmenej rôznych frekvencií tak, aby sa žiadne dva navzájom nerušili sa tak prevedie na úlohu ofarbiť vrcholy grafu G minimálnym počtom farieb (frekvencií) tak aby žiadne dva incidentné vrcholy (vysielače, ktoré by sa rušili) nemali pridelenú tú istú farbu (frekvenciu). Graf G na riešenie problému prideľovania frekvencií nemusí byť a ani vo väčšine prípadov nie je rovinný, hoci by tomu mohlo naznačovať rozmiestnenie vysielačov v rovine. Rôzny výkon vysielačov, prírodné podmienky šírenia rádiových vĺn, prekážky, odrazy spôsobujú, že vzájomné ovplyvňovanie sa vysielačov je veľmi zložité a preto sa nedá graf G čo do zložitosti porovnať s grafom pre farbenie rovinných máp.

Zdroje

• http://cyril.fmph.uniba.sk/mffuk/studium/stud_materialy/stud_materialy/grafy1/g1_10.PDF Archivované 2007-06-12 na Wayback Machine
• http://frcatel.fri.uniza.sk/users/paluch/grkap8-nopics.pdf
• Bučko, M. - Klešč, M.: Diskrétna Matematika, Academic press Elfa, Košice 1999