Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Barvení grafu

Definice (Neorientovaný graf s násobnými hranami (multigraf))

je trojice kde a jsou disjunktní množiny a je zobrazení (hrany prohlásíme za abstraktní objekty a určuje pro každou hranu dvojici vrcholů, které jsou jejími konci).

Poznámka

Pro orientovaný graf je pojem definován obdobně, pouze hrany jsou přiřazeny uspořádané dvojici vrcholů, tedy: .

Definice (Geometrický duál grafu)

Nechť je topologický rovinný graf. Označme množinu stěn Jako (geometrický) duál grafu definujeme multigraf tvaru kde se definuje předpisem jestliže hrana je společnou hranicí stěn a (přičemž může být jestliže z obou stran hrany je tatáž stěna). Značíme jej (Sice opravdu platí , ale pak již pro spočítání druhého duálu potřebujeme znát duál i pro multigrafy!)

Úloha (barvení mapy)

Uvažme politickou mapu, na níž jsou vyznačeny hranice států. Předpokládejme, že každý stát tvoří souvislou oblast ohraničenou nějakou topologickou kružnicí. Dvě oblasti pokládáme za sousední, jesliže mají společný aspoň kousek hranice. Každý stát na takové mapě chceme vybarvit nějakou barvou tak, že sousední státy nikdy nebudou mít stejnou barvu. Jaký minimální počet barev je potřeba?

Definice (Barevnost grafu)

Buď graf, přirozené číslo. Zobrazení nazveme obarvením grafu pomocí barev, pokud pro každou hranu platí Barevnost (chromatické číslo) grafu označovaná je minimální počet barev potřebný k obarvení

Lemma

Duální graf rovinného grafu je rovinný graf.

Převod úlohy barvení mapy na úlohu hledání barevnosti grafu

Máme-li mapu, kterou chápeme jako nakreslení nějakého grafu potom otázka obarvitelnosti mapy pomocí barev je ekvivalentní s obarvitelností duálního grafu pomocí barev. Na druhé straně platí, že každý rovinný graf se vyskytne jako podgraf duálního grafu nějakého vhodného grafu. Takto lze převést problém barvení map na problémy barevnosti rovinných grafů.

Věta (Věta o pěti barvách)

Pro každý rovinný graf platí

Důkaz

Indukcí dle počtu vrcholů grafu. Pro je tvrzení triviální. Podle důsledku věty o počtu hran v rovinném grafu existuje vrchol stupně Pokud má vrchol stupeň použijeme indukční předpoklad: obarvíme graf 5 barvami a přiřadíme barvu, která není mezi barvami jeho (nejvýše čtyř) sousedů. Zbývá tedy případ, kdy má stupeň 5 a jeho sousedi jsou obarveni různými barvami. Graf má pevně zvolené rovinné nakreslení a v tomto nakreslení budou sousedé vrcholu v takovém pořadí, v jakém příslušné hrany vycházejí z vrcholu (např. po směru hodinových ručiček). Uvažme vrcholy a a nechť je množina všech vrcholů grafu obarvených barvami nebo Zřejmě

Nastávají dva případy:

1. Neexistuje cesta z do používající pouze vrcholů z Mějme množinu vrcholů, které jsou v spojeny s cestou používající jen vrcholy z Definujeme nové obarvení takto: pokud a pokud změníme barvu z na nebo z na (tzn. na množině zaměníme barvy). Zřejmě je obarvení, a protože můžeme položit Tedy je obarvení grafu 5 barvami.
2. Pokud taková cesta existuje (označme ji ), uvažme vrcholy a Zřejmě a jsou disjunktní množiny. Cesta spolu s hranami a tvoří kružnici, která odděluje a a proto by každá cesta z do musela použít některý vrchol této kružnice. Neexistuje tedy cesta z do používající pouze vrcholů z a obarvení grafu G 5 barvami lze zkonstruovat stejně jako v předchozím případě, pouze musíme začít s vrcholy a

Věta (Problém čtyř barev)

Je možné každou mapu obarvit 4 barvami?

Důkaz

Věta platí, ale je velmi těžké ji dokázat (probírání mnoha případů počítačem).

Poznámka

NP-úplné problémy: je dán neorientovaný graf a číslo

1. Je možné obarvit barvami?
2. Totéž, ale předem víme, že k=3.
3. Totéž, ale graf je rovinný.
4. Totéž, ale stupeň libovolného vrcholu je nejvýše 4.
5. Je dáno obarvení třemi barvami, dotaz na netriviálně jiné.