Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


1. Úvod / Využití grafů

Co jsou grafy?

Ještě před matematickou definicí grafu je vhodné si říct, co grafy jsou a k čemu se využívají. Grafů rozeznáváme celou řadu typů, v tomto textu nám však nepůjde ani o grafy využívané ve statistice (sloupcový, koláčový...), ani o grafy funkcí.

Grafy si můžeme představit jako zjednodušení reálného světa, kde studovaný problém znázorníme pomocí bodů a čar, které je spojují, a tím popisují vlastnosti. Takovým bodům pak v teorii grafů říkáme vrcholy grafu a čáry, které je spojují, nazýváme hrany grafu.

Příklad 1: města na mapě

Jedním z typických problémů teorie grafů je hledání nejkratší cesty.

Představme si, že chceme zjistit nejkratší cestu mezi vybranými městy (pro zjednodušení jsou na obrázku č. 2.28 jen čtyři města).

Jediná vlastnost, která nás bude zajímat, je vzdálenost mezi městy (vzdálenost = délka cesty, kterou bychom museli ujet po silnici). Jako vrcholy tedy použijeme města; hrany pak budou popisovat, že mezi městy existuje cesta a jak je dlouhá. Přitom zanedbáváme další, v tuto chvíli zbytečné informace - z kolika různých silnic se cesta skládá, jakého jsou tvaru nebo například zeměpisná poloha měst (sever, jih...). Jediné informace, které pak algoritmus (zjednodušeně: postup řešení problému) využije, budou čísla na hranách spojujících města (vzdálenosti mezi městy).

Podrobněji se k této úloze vrátíme v kapitole 2.

Příklad: vzdálenosti měst v grafu
Znázornění vzdáleností mezi městy pomocí grafu - obrázek z Kapitoly 2, 2.28

Příklad 2: kamarádi

Následující problém ukazuje možnosti popisu rozličných situací pomocí grafů.

Mějme čtyři kamarády: Annu, Petra, Honzu a Václava. Pomocí grafu znázorníme, kdo koho zná (kdo s kým kamarádí). Znalostí grafů lze pak jednodušeji dokazovat různé důsledky - podobnou úlohu z matematické olympiády si můžete vyzkoušet zde.

Příklad: kdo je s kým kamarád zapsáno v grafu
Obr. č. 1.1 - Kamarádi

Příklad 3: stromy

Stromy jsou zvláštním typem grafů často používaným v informatice (více o stromech). Pomocí vhodně navrženého stromu lze např. jednodušeji vyhledávat či třídit čísla - příklad: binární vyhledávácí strom.

Příklad: binární vyhledávací strom
Binární vyhledávací strom - obrázek z Kapitoly 2, 2.30


Úvod

Základní pojmy

Vybrané problémy

Procvičování