Barvanje grafov
Barvanje grafa lahko opišemo kot postopek dodeljevanja barv vozliščem grafa. Pri tem ne smete uporabiti iste barve za zapolnitev dveh sosednjih oglišč. Barvanje grafov lahko imenujemo tudi barvanje vozlišč. Pri barvanju grafov moramo paziti, da graf ne sme vsebovati robov, katerih končna oglišča so obarvana z isto barvo. Ta vrsta grafa je znana kot pravilno obarvan graf.
Primer barvanja grafa
spati v js
V tem grafu prikazujemo pravilno obarvan graf, ki je opisan na naslednji način:
Zgornji graf vsebuje nekaj točk, ki so opisane na naslednji način:
- Iste barve ni mogoče uporabiti za barvanje dveh sosednjih oglišč.
- Zato ga lahko imenujemo pravilno obarvan graf.
Uporaba barvanja grafov
Obstajajo različne uporabe barvanja grafov. Nekaj njihovih pomembnih aplikacij je opisanih takole:
- Dodelitev
- Barvanje zemljevida
- Razporejanje nalog
- Sudoku
- Pripravite urnik
- Reševanje konfliktov
Kromatsko število
Kromatsko število lahko opišemo kot najmanjše število barv, potrebnih za pravilno barvanje katerega koli grafa. Z drugimi besedami, kromatsko število lahko opišemo kot minimalno število barv, ki so potrebne za barvanje katerega koli grafa na tak način, da nobeni dve sosednji točki grafa ne bosta dodeljeni enake barve.
Primer kromatskega števila:
Da bi razumeli kromatsko število, si bomo ogledali graf, ki je opisan na naslednji način:
Zgornji graf vsebuje nekaj točk, ki so opisane na naslednji način:
- Ista barva se ne uporablja za barvanje dveh sosednjih vozlišč.
- Najmanjše število barv tega grafa je 3, kar je potrebno za pravilno barvanje vozlišč.
- Zato je v tem grafu kromatsko število = 3
- Če želimo pravilno obarvati ta graf, v tem primeru potrebujemo vsaj 3 barve.
Vrste grafov kromatskega števila:
Obstajajo različne vrste grafov kromatskega števila, ki so opisani na naslednji način:
Ciklični graf:
Graf bo znan kot ciklični graf, če vsebuje 'n' robov in 'n' vozlišč (n >= 3), ki tvorijo cikel dolžine 'n'. Vse točke v cikličnem grafu so lahko samo 2 ali 3 stopnje.
Kromatsko število:
- Kromatsko število v cikličnem grafu bo 2, če je število vozlišč v tem grafu sodo.
- Kromatsko število v cikličnem grafu bo 3, če je število vozlišč v tem grafu liho.
Primeri cikličnih grafov:
Obstajajo različni primeri cikličnih grafov. Nekateri izmed njih so opisani takole:
Primer 1: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem cikličnem grafu obstajajo 3 različne barve za tri vozlišča in nobeno od sosednjih vozlišč ni obarvano z isto barvo. V tem grafu je število vozlišč liho. torej
Kromatsko število = 3
Primer 2: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem cikličnem grafu sta 2 barvi za štiri vozlišča in nobeno od sosednjih vozlišč ni obarvano z isto barvo. V tem grafu je število vozlišč sodo. torej
Kromatsko število = 2
Primer 3: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem grafu so 4 različne barve za pet vozlišč, dve sosednji točki pa sta pobarvani z isto barvo (modro). Torej ta graf ni ciklični graf in ne vsebuje kromatskega števila.
Primer 4: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem grafu sta 2 različni barvi za šest vozlišč in nobena od sosednjih tock ni obarvana z isto barvo. V tem grafu je število vozlišč sodo. torej
Kromatsko število = 2
Graf načrtovalca
Graf bo znan kot načrtovalni graf, če je narisan v ravnini. Robovi grafa planerja se ne smejo križati.
Kromatsko število:
- V načrtovalnem grafu mora biti kromatsko število manjše ali enako 4.
- Graf planerja lahko prikažejo tudi vsi zgornji ciklični grafi razen primera 3.
Primeri grafa Planer:
Obstajajo različni primeri ravninskih grafov. Nekateri izmed njih so opisani takole:
Primer 1: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem grafu so 3 različne barve za tri vozlišča in noben rob tega grafa se ne križa. torej
združi javanski niz
Kromatsko število = 3
Tukaj je kromatsko število manjše od 4, zato je ta graf ravninski graf.
Primer 2: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem grafu sta 2 različni barvi za štiri vozlišča in noben rob tega grafa se ne križa. torej
Kromatsko število = 2
Tukaj je kromatsko število manjše od 4, zato je ta graf ravninski graf.
Primer 3: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem grafu je 5 različnih barv za pet vozlišč in nobeden od robov tega grafa se ne križa. torej
Kromatsko število = 5
Tukaj je kromatsko število večje od 4, zato ta graf ni ravninski graf.
Primer 4: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem grafu sta 2 različni barvi za šest vozlišč in nobeden od robov tega grafa se ne križa. torej
Kromatsko število = 2
java string concat
Tukaj je kromatsko število manjše od 4, zato je ta graf ravninski graf.
Celoten graf
Graf bo znan kot popoln graf, če bo samo en rob uporabljen za združevanje vsaki dve različni točki. Vsako vozlišče v popolnem grafu je povezano z vsakim drugim vozliščem. V tem grafu bo vsako vozlišče obarvano z drugo barvo. To pomeni, da v celotnem grafu dve točki ne vsebujeta iste barve.
Kromatsko število
V popolnem grafu bo kromatsko število enako številu vozlišč v tem grafu.
Primeri popolnega grafa:
Obstajajo različni primeri popolnih grafov. Nekateri izmed njih so opisani takole:
Primer 1: V naslednjem grafu moramo določiti kromatsko število.
rešitev: Obstajajo 4 različne barve za 4 različna vozlišča in nobena barva ni enaka v zgornjem grafu. Po definiciji je kromatsko število število oglišč. Torej,
Kromatsko število = 4
Primer 2: V naslednjem grafu moramo določiti kromatsko število.
rešitev: Obstaja 5 različnih barv za 5 različnih vozlišč in nobena barva ni enaka v zgornjem grafu. Po definiciji je kromatsko število število oglišč. Torej,
Kromatsko število = 5
Primer 3: V naslednjem grafu moramo določiti kromatsko število.
rešitev: Obstajajo 3 različne barve za 4 različna oglišča in ena barva se ponovi v dveh ogliščih v zgornjem grafu. Torej ta graf ni popoln graf in ne vsebuje kromatskega števila.
Bipartitni graf
Graf bo znan kot dvodelni graf, če vsebuje dva niza tock, A in B. Tocko A se lahko združi samo z oglišči B. To pomeni, da robovi ne morejo združiti oglišč z množico.
Kromatsko število
V vsakem bipartitnem grafu je kromatsko število vedno enako 2.
Primeri bipartitnega grafa:
Obstaja več primerov bipartitnih grafov. Nekateri izmed njih so opisani takole:
Primer 1: V naslednjem grafu moramo določiti kromatsko število.
rešitev: V zgornjem grafu sta 2 različna niza tock. Torej bo kromatsko število vseh bipartitnih grafov vedno 2. Torej
Kromatsko število = 2
Drevo:
Povezani graf bo znan kot drevo, če v tem grafu ni vezij. V drevesu bo kromatsko število enako 2, ne glede na to, koliko vozlišč je v drevesu. Vsak bipartitni graf je tudi drevo.
Kromatsko število
V katerem koli drevesu je kromatsko število enako 2.
1 do 100 rimska št
Primeri drevesa:
Obstajajo različni primeri drevesa. Nekateri izmed njih so opisani takole:
Primer 1: V naslednjem drevesu moramo določiti kromatsko število.
rešitev: Za štiri oglišča sta 2 različni barvi. Drevo s poljubnim številom vozlišč mora vsebovati kromatsko število kot 2 v zgornjem drevesu. Torej,
Kromatsko število = 2
Primer 2: V naslednjem drevesu moramo določiti kromatsko število.
rešitev: Obstajata 2 različni barvi za pet oglišč. Drevo s poljubnim številom vozlišč mora vsebovati kromatsko število kot 2 v zgornjem drevesu. Torej,
Kromatsko število = 2
Primer kromatskega števila v resničnem življenju
Recimo, da je Marry poslovodja v podjetju Xyz. Podjetje zaposli nekaj novih zaposlenih, ona pa mora dobiti urnik usposabljanja za te nove zaposlene. Načrtovati mora tri sestanke in skuša čim več časa izkoristiti za sestanke. Če mora biti zaposleni na dveh različnih sestankih, mora vodja za ta sestanka uporabiti različna urnika. Recimo, da želimo dobiti vizualno predstavitev tega sestanka.
Za vizualno predstavitev Marry uporablja piko za označevanje srečanja. Če obstaja zaposleni, ki ima dva sestanka in se želi pridružiti obema sestankoma, bosta oba sestanka povezana s pomočjo roba. Različne časovne reže so predstavljene s pomočjo barv. Upravitelj torej zapolni pike s temi barvami tako, da dve piki ne vsebujeta iste barve, ki si deli rob. (To pomeni, da zaposleni, ki se mora udeležiti dveh sestankov, ne sme imeti istega termina). Vizualna predstavitev tega je opisana na naslednji način:
