Farbenie grafu
Farbenie grafu možno opísať ako proces priraďovania farieb k vrcholom grafu. V tomto prípade by sa na vyplnenie dvoch susedných vrcholov nemala použiť rovnaká farba. Farbenie grafu môžeme nazvať aj ako Vertex Coloring. Pri vyfarbovaní grafu musíme dbať na to, aby graf nemal obsahovať žiadnu hranu, ktorej koncové vrcholy sú zafarbené rovnakou farbou. Tento typ grafu je známy ako správne farebný graf.
Príklad vyfarbenia grafu
tlačidlo v strede css
V tomto grafe zobrazujeme správne farebný graf, ktorý je popísaný takto:
Vyššie uvedený graf obsahuje niekoľko bodov, ktoré sú popísané nasledovne:
- Na zafarbenie dvoch susedných vrcholov nemožno použiť rovnakú farbu.
- Môžeme to teda nazvať ako správne farebný graf.
Aplikácie farbenia grafov
Existujú rôzne aplikácie farbenia grafov. Niektoré z ich dôležitých aplikácií sú opísané nasledovne:
- Pridelenie
- Farbenie mapy
- Plánovanie úloh
- sudoku
- Pripravte rozvrh hodín
- Riešenie konfliktov
Chromatické číslo
Chromatické číslo možno opísať ako minimálny počet farieb potrebný na správne vyfarbenie akéhokoľvek grafu. Inými slovami, chromatické číslo možno opísať ako minimálny počet farieb, ktoré sú potrebné na zafarbenie akéhokoľvek grafu takým spôsobom, že žiadne dva susedné vrcholy grafu nebudú mať priradenú rovnakú farbu.
Príklad chromatického čísla:
Aby sme pochopili chromatické číslo, zvážime graf, ktorý je opísaný takto:
Vyššie uvedený graf obsahuje niekoľko bodov, ktoré sú popísané nasledovne:
- Na zafarbenie dvoch susedných vrcholov sa nepoužíva rovnaká farba.
- Minimálny počet farieb tohto grafu sú 3, čo je potrebné na správne vyfarbenie vrcholov.
- V tomto grafe je teda chromatické číslo = 3
- Ak chceme tento graf správne vyfarbiť, v tomto prípade potrebujeme aspoň 3 farby.
Typy chromatického počtu grafov:
Existujú rôzne typy grafov chromatického počtu, ktoré sú opísané nasledovne:
Graf cyklu:
Graf bude známy ako graf cyklu, ak obsahuje 'n' hrán a 'n' vrcholov (n >= 3), ktoré tvoria cyklus dĺžky 'n'. V grafe cyklu môžu byť len 2 alebo 3 stupne všetkých vrcholov.
Chromatické číslo:
- Chromatické číslo v grafe cyklu bude 2, ak je počet vrcholov v tomto grafe párny.
- Chromatické číslo v grafe cyklu bude 3, ak je počet vrcholov v tomto grafe nepárny.
Príklady grafu cyklu:
Existujú rôzne príklady grafov cyklov. Niektoré z nich sú opísané takto:
Príklad 1: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe cyklu sú 3 rôzne farby pre tri vrcholy a žiadny zo susedných vrcholov nie je zafarbený rovnakou farbou. V tomto grafe je počet vrcholov nepárny. Takže
Chromatické číslo = 3
Príklad 2: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe cyklu sú 2 farby pre štyri vrcholy a žiadny zo susedných vrcholov nie je zafarbený rovnakou farbou. V tomto grafe je počet vrcholov párny. Takže
Chromatické číslo = 2
Príklad 3: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe sú 4 rôzne farby pre päť vrcholov a dva susedné vrcholy sú zafarbené rovnakou farbou (modrou). Takže tento graf nie je graf cyklu a neobsahuje chromatické číslo.
Príklad 4: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe sú 2 rôzne farby pre šesť vrcholov a žiadny zo susedných vrcholov nie je zafarbený rovnakou farbou. V tomto grafe je počet vrcholov párny. Takže
Chromatické číslo = 2
Plánovač graf
Graf bude známy ako plánovací graf, ak je nakreslený v rovine. Okraje grafu plánovača sa nesmú krížiť.
Chromatické číslo:
- V plánovacom grafe musí byť chromatické číslo menšie alebo rovné 4.
- Graf plánovača možno zobraziť aj pomocou všetkých vyššie uvedených grafov cyklov okrem príkladu 3.
Príklady plánovacieho grafu:
Existujú rôzne príklady rovinných grafov. Niektoré z nich sú opísané takto:
Príklad 1: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe sú 3 rôzne farby pre tri vrcholy a žiadna z hrán tohto grafu sa neprekríži. Takže
aká veľká je obrazovka môjho monitora
Chromatické číslo = 3
Tu je chromatické číslo menšie ako 4, takže tento graf je rovinný graf.
Príklad 2: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe sú 2 rôzne farby pre štyri vrcholy a žiadna z hrán tohto grafu sa neprekríži. Takže
Chromatické číslo = 2
Tu je chromatické číslo menšie ako 4, takže tento graf je rovinný graf.
Príklad 3: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe je 5 rôznych farieb pre päť vrcholov a žiadna z hrán tohto grafu sa neprekríži. Takže
Chromatické číslo = 5
Tu je chromatické číslo väčšie ako 4, takže tento graf nie je rovinným grafom.
Príklad 4: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe sú 2 rôzne farby pre šesť vrcholov a žiadna z hrán tohto grafu sa neprekríži. Takže
Chromatické číslo = 2
Tu je chromatické číslo menšie ako 4, takže tento graf je rovinný graf.
Kompletný graf
Graf bude známy ako úplný graf, ak sa na spojenie každých dvoch odlišných vrcholov použije iba jedna hrana. Každý vrchol v kompletnom grafe je spojený s každým iným vrcholom. V tomto grafe bude každý vrchol zafarbený inou farbou. To znamená, že v úplnom grafe dva vrcholy neobsahujú rovnakú farbu.
Chromatické číslo
V úplnom grafe sa chromatické číslo bude rovnať počtu vrcholov v tomto grafe.
Príklady kompletného grafu:
Existujú rôzne príklady úplných grafov. Niektoré z nich sú opísané takto:
Príklad 1: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Existujú 4 rôzne farby pre 4 rôzne vrcholy a žiadna z farieb nie je rovnaká vo vyššie uvedenom grafe. Podľa definície je chromatické číslo počet vrcholov. takže,
Chromatické číslo = 4
Príklad 2: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Existuje 5 rôznych farieb pre 5 rôznych vrcholov a žiadna z farieb nie je rovnaká vo vyššie uvedenom grafe. Podľa definície je chromatické číslo počet vrcholov. takže,
Chromatické číslo = 5
nájsť v mape c++
Príklad 3: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Existujú 3 rôzne farby pre 4 rôzne vrcholy a jedna farba sa opakuje v dvoch vrcholoch vo vyššie uvedenom grafe. Tento graf teda nie je úplný graf a neobsahuje chromatické číslo.
Bipartitný graf
Graf bude známy ako bipartitný graf, ak obsahuje dve množiny vrcholov, A a B. Vrchol A sa môže spojiť iba s vrcholmi B. To znamená, že hrany nemôžu spojiť vrcholy s množinou.
Chromatické číslo
V každom bipartitnom grafe je chromatické číslo vždy rovné 2.
Príklady bipartitného grafu:
Existujú rôzne príklady bipartitných grafov. Niektoré z nich sú opísané takto:
Príklad 1: V nasledujúcom grafe musíme určiť chromatické číslo.
Riešenie: Vo vyššie uvedenom grafe sú 2 rôzne sady vrcholov. Takže chromatické číslo všetkých bipartitných grafov bude vždy 2. Takže
Chromatické číslo = 2
strom:
Prepojený graf bude známy ako strom, ak v tomto grafe nie sú žiadne obvody. V strome sa chromatické číslo bude rovnať 2 bez ohľadu na to, koľko vrcholov je v strome. Každý bipartitný graf je tiež strom.
Chromatické číslo
V každom strome sa chromatické číslo rovná 2.
inicializátor slovníka c#
Príklady stromu:
Existujú rôzne príklady stromu. Niektoré z nich sú opísané takto:
Príklad 1: V nasledujúcom strome musíme určiť chromatické číslo.
Riešenie: Existujú 2 rôzne farby pre štyri vrcholy. Strom s ľubovoľným počtom vrcholov musí obsahovať chromatické číslo ako 2 vo vyššie uvedenom strome. takže,
Chromatické číslo = 2
Príklad 2: V nasledujúcom strome musíme určiť chromatické číslo.
Riešenie: Pre päť vrcholov existujú 2 rôzne farby. Strom s ľubovoľným počtom vrcholov musí obsahovať chromatické číslo ako 2 vo vyššie uvedenom strome. takže,
Chromatické číslo = 2
Reálny príklad chromatického čísla
Predpokladajme, že Marry je manažérkou v spoločnosti Xyz. Spoločnosť najíma niektorých nových zamestnancov a ona musí získať plán školení pre týchto nových zamestnancov. Musí si naplánovať tri stretnutia a tých pár časových úsekov sa snaží čo najviac využiť na stretnutia. Ak je zamestnanec, ktorý musí byť na dvoch rôznych stretnutiach, manažér musí na tieto stretnutia použiť rôzne časové plány. Predpokladajme, že chceme získať vizuálnu reprezentáciu tohto stretnutia.
Pre vizuálnu reprezentáciu Marry používa bodku na označenie stretnutia. Ak existuje zamestnanec, ktorý má dve stretnutia a potrebuje sa pripojiť k obom stretnutiam, obe stretnutia budú spojené pomocou hrany. Rôzne časové úseky sú znázornené pomocou farieb. Manažér teda vyplní bodky týmito farbami takým spôsobom, že dve bodky neobsahujú rovnakú farbu, ktorá zdieľa okraj. (To znamená, že zamestnanec, ktorý sa potrebuje zúčastniť na dvoch stretnutiach, nesmie mať rovnaký časový úsek). Vizuálna reprezentácia je opísaná takto:
