Bojanje grafikona
Bojanje grafa može se opisati kao proces dodjeljivanja boja vrhovima grafa. Pri tome se ista boja ne smije koristiti za ispunjavanje dvaju susjednih vrhova. Bojanje grafova možemo nazvati i Vertex Coloring. Kod bojanja grafa moramo paziti da graf ne smije sadržavati nijedan brid čiji su krajnji vrhovi obojeni istom bojom. Ova vrsta grafa je poznata kao ispravno obojeni graf.
Primjer bojanja grafikona
iterator java mapa
Na ovom grafikonu prikazujemo ispravno obojeni grafikon koji je opisan na sljedeći način:
Gornji grafikon sadrži neke točke koje su opisane na sljedeći način:
- Ista boja se ne može koristiti za bojanje dvaju susjednih vrhova.
- Stoga ga možemo nazvati pravilno obojenim grafom.
Primjene bojanja grafikona
Postoje različite primjene bojanja grafova. Neke od njihovih važnih primjena opisane su kako slijedi:
- Zadatak
- Bojanje karte
- Raspoređivanje zadataka
- Sudoku
- Pripremite raspored
- Rješavanje sukoba
Kromatski broj
Kromatski broj može se opisati kao minimalni broj boja potrebnih za pravilno bojanje bilo kojeg grafa. Drugim riječima, kromatski broj se može opisati kao minimalni broj boja koje su potrebne za bojanje bilo kojeg grafa na takav način da nijedna dva susjedna vrha grafa neće dobiti istu boju.
Primjer kromatskog broja:
Da bismo razumjeli kromatski broj, razmotrit ćemo graf koji je opisan na sljedeći način:
Gornji grafikon sadrži neke točke koje su opisane na sljedeći način:
- Ista boja se ne koristi za bojanje dvaju susjednih vrhova.
- Minimalni broj boja ovog grafa je 3, koliko je potrebno za pravilno bojanje vrhova.
- Dakle, u ovom grafikonu, kromatski broj = 3
- Ako želimo pravilno obojiti ovaj graf, u ovom slučaju, potrebne su nam najmanje 3 boje.
Vrste grafova kromatskog broja:
Postoje različite vrste grafova kromatskog broja, koji su opisani na sljedeći način:
Grafikon ciklusa:
Graf će biti poznat kao ciklusni graf ako sadrži 'n' bridova i 'n' vrhova (n >= 3), koji tvore ciklus duljine 'n'. Mogu postojati samo 2 ili 3 stupnja svih vrhova u grafu ciklusa.
Kromatski broj:
- Kromatski broj u cikličkom grafu bit će 2 ako je broj vrhova u tom grafu paran.
- Kromatski broj u cikličnom grafu bit će 3 ako je broj vrhova u tom grafu neparan.
Primjeri ciklusnog grafikona:
Postoje različiti primjeri cikličnih grafova. Neki od njih opisani su na sljedeći način:
Primjer 1: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: U gornjem grafu ciklusa postoje 3 različite boje za tri vrha, a nijedan od susjednih vrhova nije obojen istom bojom. U ovom grafu broj vrhova je neparan. Tako
Kromatski broj = 3
Primjer 2: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: U gornjem grafu ciklusa postoje 2 boje za četiri vrha, a nijedan od susjednih vrhova nije obojen istom bojom. U ovom grafu broj vrhova je paran. Tako
Kromatski broj = 2
Primjer 3: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: Na gornjem grafu postoje 4 različite boje za pet vrhova, a dva susjedna vrha obojena su istom bojom (plavo). Dakle, ovaj graf nije ciklički graf i ne sadrži kromatski broj.
Primjer 4: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: U gornjem grafu postoje 2 različite boje za šest vrhova, a nijedan od susjednih vrhova nije obojen istom bojom. U ovom grafu broj vrhova je paran. Tako
Kromatski broj = 2
Planer Graph
Graf će biti poznat kao planer graf ako je nacrtan u ravnini. Rubovi grafa planera ne smiju se križati.
Kromatski broj:
- U grafu planera, kromatski broj mora biti manji ili jednak 4.
- Grafikon planera također se može prikazati svim gornjim grafikonima ciklusa osim primjera 3.
Primjeri Planer grafa:
Postoje različiti primjeri ravnih grafova. Neki od njih opisani su na sljedeći način:
Primjer 1: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: U gornjem grafu postoje 3 različite boje za tri vrha, a niti jedan rub ovog grafa se ne križa. Tako
java do while primjer
Kromatski broj = 3
Ovdje je kromatski broj manji od 4, tako da je ovaj graf ravni graf.
Primjer 2: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: U gornjem grafu postoje 2 različite boje za četiri vrha, a niti jedan rub ovog grafa se ne križa. Tako
Kromatski broj = 2
Ovdje je kromatski broj manji od 4, tako da je ovaj graf ravni graf.
Primjer 3: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: U gornjem grafu postoji 5 različitih boja za pet vrhova, a niti jedan rub ovog grafa se ne križa. Tako
Kromatski broj = 5
Ovdje je kromatski broj veći od 4, tako da ovaj graf nije ravni graf.
Primjer 4: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: U gornjem grafu postoje 2 različite boje za šest vrhova, a niti jedan rub ovog grafa se ne križa. Tako
Kromatski broj = 2
Ovdje je kromatski broj manji od 4, tako da je ovaj graf ravni graf.
Kompletan grafikon
Graf će biti poznat kao potpuni graf ako se samo jedan brid koristi za spajanje svaka dva različita vrha. Svaki vrh u potpunom grafu povezan je sa svakim drugim vrhom. U ovom grafu, svaki vrh će biti obojen drugom bojom. To znači da u cijelom grafu dva vrha nemaju istu boju.
Kromatski broj
U potpunom grafu, kromatski broj će biti jednak broju vrhova u tom grafu.
Primjeri kompletnog grafikona:
Postoje različiti primjeri cjelovitih grafova. Neki od njih opisani su na sljedeći način:
Primjer 1: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: Postoje 4 različite boje za 4 različita vrha, a nijedna boja nije ista u gornjem grafu. Prema definiciji, kromatski broj je broj vrhova. Tako,
Kromatski broj = 4
Primjer 2: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: Postoji 5 različitih boja za 5 različitih vrhova, a nijedna boja nije ista u gornjem grafu. Prema definiciji, kromatski broj je broj vrhova. Tako,
Kromatski broj = 5
okvir java zbirke
Primjer 3: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: Postoje 3 različite boje za 4 različita vrha, a jedna boja se ponavlja u dva vrha u gornjem grafu. Dakle, ovaj graf nije potpuni graf i ne sadrži kromatski broj.
Bipartitni graf
Graf će biti poznat kao bipartitni graf ako sadrži dva skupa vrhova, A i B. Vrh A se može spojiti samo s vrhovima B. To znači da bridovi ne mogu spojiti vrhove sa skupom.
Kromatski broj
U svakom bipartitnom grafu, kromatski broj je uvijek jednak 2.
Primjeri bipartitnog grafa:
Postoje različiti primjeri bipartitnih grafova. Neki od njih opisani su na sljedeći način:
Primjer 1: U sljedećem grafikonu moramo odrediti kromatski broj.
Riješenje: Postoje 2 različita skupa vrhova u gornjem grafu. Tako će kromatski broj svih bipartitnih grafova uvijek biti 2. Dakle
Kromatski broj = 2
Stablo:
Povezani graf bit će poznat kao stablo ako u tom grafu nema krugova. U stablu će kromatski broj biti jednak 2 bez obzira koliko vrhova ima u stablu. Svaki bipartitni graf je također stablo.
Kromatski broj
U svakom stablu, kromatski broj je jednak 2.
graditelj dizajn uzorak
Primjeri stabla:
Postoje različiti primjeri stabla. Neki od njih opisani su na sljedeći način:
Primjer 1: U sljedećem stablu moramo odrediti kromatski broj.
Riješenje: Postoje 2 različite boje za četiri vrha. Stablo s bilo kojim brojem vrhova mora sadržavati kromatski broj kao 2 u gornjem stablu. Tako,
Kromatski broj = 2
Primjer 2: U sljedećem stablu moramo odrediti kromatski broj.
Riješenje: Postoje 2 različite boje za pet vrhova. Stablo s bilo kojim brojem vrhova mora sadržavati kromatski broj kao 2 u gornjem stablu. Tako,
Kromatski broj = 2
Primjer kromatskog broja iz stvarnog života
Pretpostavimo da je Marry menadžer u tvrtki Xyz. Tvrtka zapošljava neke nove zaposlenike, a ona mora dobiti raspored obuke za te nove zaposlenike. Mora zakazati tri sastanka, a nekoliko termina pokušava iskoristiti što je više moguće za sastanke. Ako postoji zaposlenik koji mora biti na dva različita sastanka, tada voditelj treba koristiti različite vremenske rasporede za te sastanke. Pretpostavimo da želimo dobiti vizualni prikaz ovog sastanka.
Za vizualni prikaz, Marry koristi točku za označavanje sastanka. Ako postoji zaposlenik koji ima dva sastanka i želi se pridružiti oba sastanka, tada će oba sastanka biti povezana uz pomoć ruba. Različiti vremenski odsječci predstavljeni su uz pomoć boja. Stoga upravitelj ispunjava točke tim bojama na takav način da dvije točke ne sadrže istu boju koja dijeli rub. (To znači da zaposlenik koji treba prisustvovati dvama sastancima ne smije imati isto vrijeme). Vizualni prikaz ovoga opisan je na sljedeći način:
