Бојење графикона
Бојење графа се може описати као процес додељивања боја врховима графа. У овом случају, иста боја не треба да се користи за попуњавање два суседна врха. Такође можемо назвати бојење графова као бојење темена. Код бојења графа морамо водити рачуна да граф не сме да садржи ниједну ивицу чији су крајњи врхови обојени истом бојом. Овај тип графикона је познат као график правилног боје.
Пример бојења графикона
стринг токенизер јава
На овом графикону приказујемо правилно обојен графикон, који је описан на следећи начин:
Горњи графикон садржи неке тачке које су описане на следећи начин:
- Иста боја се не може користити за бојење два суседна врха.
- Дакле, можемо га назвати као правилно обојен граф.
Примене бојења графова
Постоје различите примене бојења графова. Неке од њихових важних примена су описане на следећи начин:
- Додељивање
- Бојење мапе
- Планирање задатака
- Судоку
- Припремите распоред
- Решавање конфликата
Хроматски број
Хроматски број се може описати као минимални број боја потребних за правилно бојење било ког графикона. Другим речима, хроматски број се може описати као минимални број боја које су потребне да би се било који граф обојио на начин да ниједна два суседна врха графа неће добити исту боју.
Пример хроматског броја:
Да бисмо разумели хроматски број, размотрићемо графикон који је описан на следећи начин:
Горњи графикон садржи неке тачке које су описане на следећи начин:
- Иста боја се не користи за бојење два суседна врха.
- Минимални број боја овог графа је 3, што је потребно за правилно бојење врхова.
- Дакле, у овом графикону, хроматски број = 3
- Ако желимо да правилно обојимо овај графикон, у овом случају су нам потребне најмање 3 боје.
Врсте хроматског броја графикона:
Постоје различите врсте хроматског броја графикона, који су описани на следећи начин:
Графикон циклуса:
Граф ће бити познат као циклусни граф ако садржи 'н' ивица и 'н' врхова (н >= 3), који чине циклус дужине 'н'. Може постојати само 2 или 3 степена свих врхова у циклусном графу.
Хроматски број:
- Хроматски број у циклусном графу биће 2 ако је број врхова у том графу паран.
- Хроматски број у циклусном графу биће 3 ако је број врхова у том графу непаран.
Примери графикона циклуса:
Постоје разни примери циклусних графова. Неки од њих су описани на следећи начин:
Пример 1: У следећем графикону морамо одредити хроматски број.
Решење: У горњем циклусном графикону постоје 3 различите боје за три темена, а ниједан од суседних врхова није обојен истом бојом. У овом графу, број врхова је непаран. Тако
Хроматски број = 3
Пример 2: У следећем графикону морамо одредити хроматски број.
Решење: У горњем циклусном графикону постоје 2 боје за четири темена, а ниједан од суседних врхова није обојен истом бојом. У овом графу, број врхова је паран. Тако
Хроматски број = 2
Пример 3: У следећем графикону морамо одредити хроматски број.
Решење: У горњем графикону постоје 4 различите боје за пет врхова, а два суседна врха су обојена истом бојом (плавом). Дакле, овај граф није циклусни граф и не садржи хроматски број.
Пример 4: У следећем графикону морамо одредити хроматски број.
Решење: У горњем графикону постоје 2 различите боје за шест врхова, а ниједан од суседних врхова није обојен истом бојом. У овом графу, број врхова је паран. Тако
Хроматски број = 2
Планер Грапх
Графикон ће бити познат као граф планера ако је нацртан у равни. Ивице графа планера не смеју се укрштати.
Хроматски број:
- У графикону планера, хроматски број мора бити мањи или једнак 4.
- График планера се такође може приказати свим горе наведеним графовима циклуса осим примера 3.
Примери Планер графикона:
Постоје разни примери планер графова. Неки од њих су описани на следећи начин:
Пример 1: У следећем графикону морамо одредити хроматски број.
Решење: У горњем графу постоје 3 различите боје за три темена, а ниједна од ивица овог графа се не укршта. Тако
регистар меморија
Хроматски број = 3
Овде је хроматски број мањи од 4, тако да је овај график раван.
Пример 2: У следећем графикону морамо одредити хроматски број.
Решење: У горњем графу постоје 2 различите боје за четири темена, а ниједна ивица овог графа се не укршта. Тако
Хроматски број = 2
Овде је хроматски број мањи од 4, тако да је овај график раван.
Пример 3: У следећем графикону морамо одредити хроматски број.
Решење: У горњем графу постоји 5 различитих боја за пет врхова и ниједна од ивица овог графа се не укршта. Тако
Хроматски број = 5
Овде је хроматски број већи од 4, тако да овај график није раван.
Пример 4: У следећем графикону морамо одредити хроматски број.
Решење: У горњем графу постоје 2 различите боје за шест врхова и ниједна од ивица овог графа се не укршта. Тако
Хроматски број = 2
Овде је хроматски број мањи од 4, тако да је овај график раван.
Комплетан графикон
Граф ће бити познат као комплетан граф ако се само једна ивица користи за спајање свака два различита темена. Сваки врх у комплетном графу повезан је са сваким другим врхом. У овом графу, сваки врх ће бити обојен другом бојом. То значи да у комплетном графу два врха не садрже исту боју.
Хроматски број
цео број у низ у Јави
У потпуном графу, хроматски број ће бити једнак броју врхова у том графу.
Примери комплетног графикона:
Постоје разни примери комплетних графикона. Неки од њих су описани на следећи начин:
Пример 1: У следећем графикону морамо одредити хроматски број.
Решење: Постоје 4 различите боје за 4 различита врха, а ниједна боја није иста у горњем графикону. Према дефиницији, хроматски број је број врхова. Тако,
Хроматски број = 4
Пример 2: У следећем графикону морамо одредити хроматски број.
Решење: Постоји 5 различитих боја за 5 различитих врхова, а ниједна боја није иста у горњем графикону. Према дефиницији, хроматски број је број врхова. Тако,
Хроматски број = 5
Пример 3: У следећем графикону морамо одредити хроматски број.
Решење: Постоје 3 различите боје за 4 различита врха, а једна боја се понавља у два врха у горњем графикону. Дакле, овај граф није потпун и не садржи хроматски број.
Бипартите Грапх
Граф ће бити познат као бипартитни граф ако садржи два скупа темена, А и Б. Теме А може се спојити само са врховима Б. То значи да се ивице не могу спојити са врховима скупом.
Хроматски број
У било ком дводелном графу, хроматски број је увек једнак 2.
Примери дводелног графикона:
Постоје разни примери бипартитних графова. Неки од њих су описани на следећи начин:
Пример 1: У следећем графикону морамо одредити хроматски број.
Решење: Постоје 2 различита скупа врхова у горњем графу. Дакле, хроматски број свих бипартитних графова ће увек бити 2. Дакле
Хроматски број = 2
Дрво:
Повезани граф ће бити познат као стабло ако у том графу нема кола. У стаблу, хроматски број ће бити једнак 2 без обзира на то колико врхова има дрво. Сваки бипартитни граф је такође дрво.
Хроматски број
У било ком стаблу, хроматски број је једнак 2.
јава синцхронизе
Примери дрвета:
Постоје разни примери дрвета. Неки од њих су описани на следећи начин:
Пример 1: У следећем стаблу морамо да одредимо хроматски број.
Решење: Постоје 2 различите боје за четири врха. Дрво са било којим бројем врхова мора да садржи хроматски број као 2 у горњем дрвету. Тако,
Хроматски број = 2
Пример 2: У следећем стаблу морамо да одредимо хроматски број.
Решење: Постоје 2 различите боје за пет врхова. Дрво са било којим бројем врхова мора да садржи хроматски број као 2 у горњем дрвету. Тако,
Хроматски број = 2
Пример хроматског броја из стварног живота
Претпоставимо да је Марри менаџер у компанији Ксиз. Компанија запошљава неке нове запослене, а она мора да добије распоред обуке за те нове запослене. Она мора да закаже три састанка и покушава да искористи неколико временских термина што је више могуће за састанке. Ако постоји запослени који мора да буде на два различита састанка, онда менаџер треба да користи различите временске распореде за те састанке. Претпоставимо да желимо да добијемо визуелни приказ овог састанка.
За визуелни приказ, Марри користи тачку да означи састанак. Ако постоји запосленик који има два састанка и захтева да се придружи оба састанка, онда ће оба састанка бити повезана уз помоћ ивице. Различити временски интервали су представљени уз помоћ боја. Дакле, менаџер испуњава тачке овим бојама на такав начин да две тачке не садрже исту боју која дели ивицу. (То значи да запослени који треба да присуствује два састанка не сме имати исти термин). Визуелни приказ овога је описан на следећи начин:
