Grafikon színezése
A gráf színezése a gráf csúcsaihoz színek hozzárendelésének folyamataként írható le. Ebben nem szabad ugyanazt a színt használni a két szomszédos csúcs kitöltésére. A gráfszínezést Vertex színezésnek is nevezhetjük. A gráf színezésénél ügyelnünk kell arra, hogy a gráf ne tartalmazzon olyan élt, amelynek végcsúcsai azonos színűek. Ez a fajta gráf a Megfelelően színezett gráf néven ismert.
Példa a grafikonok színezésére
szimmetrikus különbség
Ezen a grafikonon a megfelelően színezett grafikont mutatjuk be, amelynek leírása a következő:
A fenti grafikon néhány pontot tartalmaz, amelyek leírása a következő:
- Ugyanaz a szín nem használható a két szomszédos csúcs színezésére.
- Ezért nevezhetjük megfelelően színezett gráfnak.
Grafikus színezés alkalmazásai
A grafikonok színezésének számos alkalmazása létezik. Néhány fontos alkalmazásukat az alábbiakban ismertetjük:
- Feladat
- Térkép színezése
- A feladatok ütemezése
- Sudoku
- Készítse elő az órarendet
- Konfliktusmegoldó
Kromatikus szám
A kromatikus szám úgy írható le, mint a színek minimális száma, amely bármely gráf megfelelő színezéséhez szükséges. Más szavakkal, a kromatikus szám a színek minimális számaként írható le, amely bármely gráf színezéséhez szükséges oly módon, hogy a gráf két szomszédos csúcsához ne legyen ugyanaz a szín.
Példa kromatikus számra:
A kromatikus szám megértéséhez egy grafikont veszünk figyelembe, amelynek leírása a következő:
A fenti grafikon néhány pontot tartalmaz, amelyek leírása a következő:
- Nem ugyanazt a színt használják a két szomszédos csúcs színezésére.
- A gráf színeinek minimális száma 3, ami szükséges a csúcsok megfelelő színezéséhez.
- Ezért ezen a grafikonon a kromatikus szám = 3
- Ha megfelelően szeretnénk színezni ezt a grafikont, ebben az esetben legalább 3 színre van szükségünk.
A kromatikus számú grafikon típusai:
Különféle típusú kromatikus számú gráfok léteznek, amelyek leírása a következő:
Ciklusgrafikon:
Egy gráfot ciklusgráfnak nevezünk, ha 'n' élt és 'n' csúcsot tartalmaz (n >= 3), amelyek 'n' hosszúságú ciklust alkotnak. A ciklusgráf összes csúcsának csak 2 vagy 3 foka lehet.
Kromatikus szám:
- A ciklusgráf kromatikus száma 2 lesz, ha a gráf csúcsainak száma páros.
- A ciklusgráf kromatikus száma 3 lesz, ha a gráf csúcsainak száma páratlan.
Példák ciklusdiagramra:
A ciklusgrafikonokra különféle példák vannak. Némelyikük leírása a következő:
1. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti ciklusgrafikonon három csúcshoz 3 különböző szín tartozik, és a szomszédos csúcsok egyike sem azonos színnel. Ebben a gráfban a csúcsok száma páratlan. Így
Kromatikus szám = 3
2. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti ciklusgráfban négy csúcshoz 2 szín tartozik, és a szomszédos csúcsok egyike sem azonos színnel. Ebben a gráfban a csúcsok száma páros. Így
Kromatikus szám = 2
3. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti grafikonon 4 különböző szín található öt csúcshoz, és két szomszédos csúcs azonos színnel (kék) van színezve. Tehát ez a gráf nem ciklusgráf, és nem tartalmaz kromatikus számot.
4. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti grafikonon 2 különböző szín található hat csúcshoz, és a szomszédos csúcsok egyike sem azonos színnel. Ebben a gráfban a csúcsok száma páros. Így
Kromatikus szám = 2
Tervező grafikon
Egy gráfot tervező gráfnak nevezünk, ha síkban rajzoljuk meg. A tervező gráf élei nem keresztezhetik egymást.
Kromatikus szám:
- Tervező gráfban a kromatikus számnak kisebbnek vagy egyenlőnek kell lennie 4-nél.
- A tervezői grafikont a 3. példa kivételével az összes fenti ciklusgrafikon is megjelenítheti.
Példák Planer grafikonra:
Különféle példák vannak a gyalugráfokra. Némelyikük leírása a következő:
1. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti gráfban három csúcshoz 3 különböző szín tartozik, és ennek a gráfnak egyik éle sem keresztezi egymást. Így
java osztálydiagram
Kromatikus szám = 3
Itt a kromatikus szám kisebb, mint 4, tehát ez a gráf síkgráf.
2. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti gráfban négy csúcshoz 2 különböző szín tartozik, és ennek a gráfnak egyik éle sem keresztezi egymást. Így
Kromatikus szám = 2
Itt a kromatikus szám kisebb, mint 4, tehát ez a gráf síkgráf.
3. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti gráfban öt csúcshoz 5 különböző szín tartozik, és ennek a gráfnak egyik éle sem keresztezi egymást. Így
Kromatikus szám = 5
Itt a kromatikus szám nagyobb, mint 4, tehát ez a gráf nem síkgráf.
4. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti gráfban hat csúcshoz 2 különböző szín tartozik, és ennek a gráfnak egyik éle sem keresztezi egymást. Így
Kromatikus szám = 2
Itt a kromatikus szám kisebb, mint 4, tehát ez a gráf síkgráf.
css határ
Teljes grafikon
Egy gráfot teljes gráfnak nevezünk, ha csak egy élt használunk minden két különböző csúcs összekapcsolására. A teljes gráf minden csúcsa minden más csúcshoz kapcsolódik. Ezen a grafikonon minden csúcs más színnel lesz színezve. Ez azt jelenti, hogy a teljes gráfban két csúcs nem ugyanazt a színt tartalmazza.
Kromatikus szám
Egy teljes gráfban a kromatikus szám megegyezik a gráf csúcsainak számával.
Példák a teljes grafikonra:
Különféle példák vannak a teljes grafikonokra. Némelyikük leírása a következő:
1. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: Négy különböző csúcshoz 4 különböző szín tartozik, és a fenti grafikonon egyik szín sem azonos. A definíció szerint a kromatikus szám a csúcsok száma. Így,
Kromatikus szám = 4
2. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: Öt különböző csúcshoz 5 különböző szín tartozik, és a fenti grafikonon egyik szín sem azonos. A definíció szerint a kromatikus szám a csúcsok száma. Így,
Kromatikus szám = 5
3. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: 4 különböző csúcshoz 3 különböző szín tartozik, és a fenti grafikonon egy szín két csúcsban ismétlődik. Tehát ez a gráf nem teljes gráf, és nem tartalmaz kromatikus számot.
Bipartite Graph
Egy gráfot bipartit gráfnak nevezünk, ha két csúcshalmazt tartalmaz, A-t és B-t. A csúcsa csak B csúcsaihoz kapcsolódhat. Ez azt jelenti, hogy az élek nem csatlakozhatnak a csúcsokhoz egy halmazsal.
Kromatikus szám
Bármely kétrészes gráfban a kromatikus szám mindig egyenlő 2-vel.
Példák kétoldalú gráfra:
Különféle példák vannak a kétoldalú gráfokra. Némelyikük leírása a következő:
1. példa: A következő grafikonon meg kell határoznunk a kromatikus számot.
Megoldás: A fenti gráfban 2 különböző csúcskészlet található. Tehát az összes kétrészes gráf kromatikus száma mindig 2 lesz. Tehát
Kromatikus szám = 2
Fa:
Az összekapcsolt gráfot fának nevezzük, ha a gráfban nincsenek áramkörök. Egy fában a kromatikus szám 2 lesz, függetlenül attól, hogy hány csúcsa van a fának. Minden kétrészes gráf egyben fa is.
Kromatikus szám
Bármely fában a kromatikus szám egyenlő 2-vel.
formázza meg a dátumot java-ban
Példák a fára:
Különféle példák vannak a fára. Némelyikük leírása a következő:
1. példa: A következő fában meg kell határoznunk a kromatikus számot.
Megoldás: Négy csúcshoz 2 különböző szín tartozik. Egy tetszőleges számú csúcsú fának a kromatikus számot 2-ként kell tartalmaznia a fenti fában. Így,
Kromatikus szám = 2
2. példa: A következő fában meg kell határoznunk a kromatikus számot.
Megoldás: Öt csúcshoz 2 különböző szín tartozik. Egy tetszőleges számú csúcsú fának a kromatikus számot 2-ként kell tartalmaznia a fenti fában. Így,
Kromatikus szám = 2
Valós példa a kromatikus számra
Tegyük fel, hogy Marry a Xyz Company menedzsere. A cég felvesz néhány új alkalmazottat, és képzési ütemtervet kell készítenie az új alkalmazottak számára. A három találkozót be kell ütemeznie, és igyekszik a lehető legtöbb időt kihasználni a megbeszélésekre. Ha van olyan alkalmazott, akinek két különböző megbeszélésen kell részt vennie, akkor a vezetőnek eltérő időbeosztást kell alkalmaznia ezekre a megbeszélésekre. Tegyük fel, hogy vizuálisan szeretnénk ábrázolni ezt a találkozót.
A vizuális ábrázoláshoz Marry a pontot használja a találkozás jelzésére. Ha van olyan alkalmazott, akinek két megbeszélése van, és mindkét értekezlethez csatlakoznia kell, akkor mindkét értekezlet egy él segítségével összekapcsolódik. A különböző időréseket színek segítségével ábrázoljuk. Tehát a menedzser ezekkel a színekkel tölti ki a pontokat úgy, hogy két pontban ne legyen ugyanaz a szín, amely egy élen osztozik. (Ez azt jelenti, hogy annak az alkalmazottnak, akinek részt kell vennie a két megbeszélésen, nem szabad ugyanazt az időpontot kapnia). Ennek vizuális megjelenítését a következőképpen írjuk le:
