A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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 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
- http://frcatel.fri.uniza.sk/users/paluch/grkap8-nopics.pdf
- Bučko, M. - Klešč, M.: Diskrétna Matematika, Academic press Elfa, Košice 1999
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Binárny strom (teória grafov)
Cesta (teória grafov)
Chromatické číslo
Chromatický index
Cyklomatické číslo grafu
Eulerovský ťah
Excentricita (teória grafov)
Faktor grafu
Farbenie grafu
Farbenie vrcholov
Grafová postupnosť
Graf (matematika)
Hamiltonovská kružnica
Hamiltonovský graf
Hrana (teória grafov)
Komplement grafu
Komponent grafu
Kostra grafu
Kružnica (teória grafov)
Minimálna kostra grafu
Most (teória grafov)
Neplanárny graf
Nezávislá množina
Ohodnotený graf
Oreho veta
Orientované stromy
Párny graf
Petersenov graf
Podgraf
Priesečníkové číslo (teória grafov)
Problém obchodného cestujúceho
Problém siedmich mostov
Rovinný graf
Súvislý graf
Sled (teória grafov)
Spektrálna teória grafov
Strom (teória grafov)
Teória grafov
Teória grafov – grafová postupnosť
Topologická teória grafov
Vrchol (teória grafov)
Vzdialenosť (teória grafov)
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk