Barvení grafu
Barvení grafu lze popsat jako proces přiřazování barev vrcholům grafu. V tomto případě by stejná barva neměla být použita k vyplnění dvou sousedních vrcholů. Barvení grafu můžeme také nazvat jako Vertex Coloring. Při vybarvování grafu musíme dbát na to, že graf nesmí obsahovat žádnou hranu, jejíž koncové vrcholy jsou obarveny stejnou barvou. Tento typ grafu je známý jako správně barevný graf.
Příklad vybarvení grafu
primitivní datové typy v jazyce Java
V tomto grafu zobrazujeme správně barevný graf, který je popsán následovně:
Výše uvedený graf obsahuje některé body, které jsou popsány následovně:
- Stejnou barvu nelze použít k obarvení dvou sousedních vrcholů.
- Můžeme jej tedy nazvat jako správně barevný graf.
Aplikace barvení grafů
Existují různé aplikace barvení grafů. Některé z jejich důležitých aplikací jsou popsány takto:
- Úkol
- Barvení mapy
- Plánování úkolů
- sudoku
- Připravte rozvrh hodin
- Řešení konfliktů
Chromatické číslo
Chromatické číslo lze popsat jako minimální počet barev potřebný pro správné obarvení jakéhokoli grafu. Jinými slovy, chromatické číslo lze popsat jako minimální počet barev, které jsou potřeba k obarvení jakéhokoli grafu takovým způsobem, že žádné dva sousední vrcholy grafu nebudou mít přiřazenu stejnou barvu.
Příklad chromatického čísla:
Abychom pochopili chromatické číslo, budeme uvažovat graf, který je popsán takto:
Výše uvedený graf obsahuje některé body, které jsou popsány následovně:
- K obarvení dvou sousedních vrcholů není použita stejná barva.
- Minimální počet barev tohoto grafu jsou 3, což je potřeba pro správné obarvení vrcholů.
- V tomto grafu je tedy chromatické číslo = 3
- Pokud chceme tento graf správně vybarvit, v tomto případě potřebujeme alespoň 3 barvy.
Typy chromatického počtu grafů:
Existují různé typy grafů chromatického počtu, které jsou popsány následovně:
Graf cyklu:
Graf bude známý jako graf cyklu, pokud obsahuje 'n' hran a 'n' vrcholů (n >= 3), které tvoří cyklus délky 'n'. V grafu cyklu mohou být pouze 2 nebo 3 stupně všech vrcholů.
Chromatické číslo:
- Chromatické číslo v grafu cyklu bude 2, pokud je počet vrcholů v tomto grafu sudý.
- Chromatické číslo v grafu cyklu bude 3, pokud je počet vrcholů v tomto grafu lichý.
Příklady cyklického grafu:
Existují různé příklady cyklických grafů. Některé z nich jsou popsány takto:
Příklad 1: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu cyklu jsou 3 různé barvy pro tři vrcholy a žádný ze sousedních vrcholů není obarven stejnou barvou. V tomto grafu je počet vrcholů lichý. Tak
Chromatické číslo = 3
Příklad 2: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu cyklu jsou 2 barvy pro čtyři vrcholy a žádný ze sousedních vrcholů není obarven stejnou barvou. V tomto grafu je počet vrcholů sudý. Tak
Chromatické číslo = 2
Příklad 3: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu jsou 4 různé barvy pro pět vrcholů a dva sousední vrcholy jsou obarveny stejnou barvou (modrou). Tento graf tedy není graf cyklu a neobsahuje chromatické číslo.
Příklad 4: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu jsou 2 různé barvy pro šest vrcholů a žádný ze sousedních vrcholů není obarven stejnou barvou. V tomto grafu je počet vrcholů sudý. Tak
Chromatické číslo = 2
Plánovací graf
Graf bude známý jako plánovací graf, pokud je nakreslen v rovině. Okraje plánovacího grafu se nesmí křížit.
Chromatické číslo:
- V plánovacím grafu musí být chromatické číslo menší nebo rovno 4.
- Plánovací graf lze také zobrazit pomocí všech výše uvedených grafů cyklů kromě příkladu 3.
Příklady plánovacího grafu:
Existují různé příklady rovinných grafů. Některé z nich jsou popsány takto:
Příklad 1: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu jsou 3 různé barvy pro tři vrcholy a žádná z hran tohoto grafu se navzájem nekříží. Tak
strsep c
Chromatické číslo = 3
Zde je chromatické číslo menší než 4, takže tento graf je rovinný graf.
Příklad 2: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu jsou 2 různé barvy pro čtyři vrcholy a žádná z hran tohoto grafu se navzájem nekříží. Tak
Chromatické číslo = 2
Zde je chromatické číslo menší než 4, takže tento graf je rovinný graf.
Příklad 3: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu je 5 různých barev pro pět vrcholů a žádná z hran tohoto grafu se navzájem nekříží. Tak
Chromatické číslo = 5
Zde je chromatické číslo větší než 4, takže tento graf není rovinným grafem.
Příklad 4: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu jsou 2 různé barvy pro šest vrcholů a žádná z hran tohoto grafu se navzájem nekříží. Tak
jarní mvc
Chromatické číslo = 2
Zde je chromatické číslo menší než 4, takže tento graf je rovinný graf.
Kompletní graf
Graf bude známý jako úplný graf, pokud se ke spojení každých dvou odlišných vrcholů použije pouze jedna hrana. Každý vrchol v kompletním grafu je spojen s každým dalším vrcholem. V tomto grafu bude každý vrchol obarven jinou barvou. To znamená, že v úplném grafu dva vrcholy neobsahují stejnou barvu.
Chromatické číslo
V úplném grafu se chromatické číslo bude rovnat počtu vrcholů v tomto grafu.
Příklady kompletního grafu:
Existují různé příklady úplných grafů. Některé z nich jsou popsány takto:
Příklad 1: V následujícím grafu musíme určit chromatické číslo.
Řešení: Existují 4 různé barvy pro 4 různé vrcholy a žádná z barev není ve výše uvedeném grafu stejná. Podle definice je chromatické číslo počet vrcholů. Tak,
Chromatické číslo = 4
Příklad 2: V následujícím grafu musíme určit chromatické číslo.
Řešení: Existuje 5 různých barev pro 5 různých vrcholů a žádná z barev není ve výše uvedeném grafu stejná. Podle definice je chromatické číslo počet vrcholů. Tak,
Chromatické číslo = 5
Příklad 3: V následujícím grafu musíme určit chromatické číslo.
Řešení: Existují 3 různé barvy pro 4 různé vrcholy a jedna barva se opakuje ve dvou vrcholech ve výše uvedeném grafu. Tento graf tedy není úplný graf a neobsahuje chromatické číslo.
Bipartitní graf
Graf bude známý jako bipartitní graf, pokud obsahuje dvě sady vrcholů, A a B. Vrchol A se může spojit pouze s vrcholy B. To znamená, že hrany nemohou spojit vrcholy s množinou.
Chromatické číslo
V každém bipartitním grafu je chromatické číslo vždy rovno 2.
Příklady bipartitního grafu:
Existují různé příklady bipartitních grafů. Některé z nich jsou popsány takto:
Příklad 1: V následujícím grafu musíme určit chromatické číslo.
Řešení: Ve výše uvedeném grafu jsou 2 různé sady vrcholů. Takže chromatické číslo všech bipartitních grafů bude vždy 2. Takže
Chromatické číslo = 2
Strom:
Souvislý graf bude znám jako strom, pokud v tomto grafu nejsou žádné obvody. Ve stromu se chromatické číslo bude rovnat 2 bez ohledu na to, kolik vrcholů je ve stromu. Každý bipartitní graf je také strom.
Chromatické číslo
V každém stromu je chromatické číslo rovno 2.
srovnatelná java
Příklady stromu:
Existují různé příklady stromu. Některé z nich jsou popsány takto:
Příklad 1: V následujícím stromu musíme určit chromatické číslo.
Řešení: Existují 2 různé barvy pro čtyři vrcholy. Strom s libovolným počtem vrcholů musí obsahovat chromatické číslo jako 2 ve výše uvedeném stromu. Tak,
Chromatické číslo = 2
Příklad 2: V následujícím stromu musíme určit chromatické číslo.
Řešení: Pro pět vrcholů existují 2 různé barvy. Strom s libovolným počtem vrcholů musí obsahovat chromatické číslo jako 2 ve výše uvedeném stromu. Tak,
Chromatické číslo = 2
Skutečný příklad chromatického čísla
Předpokládejme, že Marry je manažerkou ve společnosti Xyz. Společnost najme nějaké nové zaměstnance a ona musí získat plán školení pro tyto nové zaměstnance. Musí naplánovat tři schůzky a snaží se těch pár časových úseků co nejvíce využít pro schůzky. Pokud existuje zaměstnanec, který musí být na dvou různých schůzkách, pak musí manažer pro tyto schůzky použít různé časové plány. Předpokládejme, že chceme získat vizuální reprezentaci tohoto setkání.
Pro vizuální znázornění používá Marry tečku k označení schůzky. Pokud existuje zaměstnanec, který má dvě schůzky a chce se připojit k oběma schůzkám, pak se obě schůzky propojí pomocí hrany. Různé časové úseky jsou znázorněny pomocí barev. Správce tedy vyplní tečky těmito barvami takovým způsobem, že dva tečky neobsahují stejnou barvu, která sdílí okraj. (To znamená, že zaměstnanec, který se potřebuje zúčastnit dvou schůzek, nesmí mít stejný časový úsek). Vizuální reprezentace je popsána takto:
