Cíl předmětu ⇫

Rozvíjet a prohlubovat logické a algoritmické myšlení studentů. Seznámit se se základními poznatky z oblasti teorie grafů.

Teorie ⇫

Slovo graf se používá v různých významech. Mnohým z Vás je určitě znám pojem graf funkce, s kterým se potkáváte nejen v matematice, ale i v dalších oborech lidské činnosti.

V matematice také existuje pojem graf, který nemá téměř nic společného se známými  grafy funkcí. Až na název, který je odvozen z řeckého slova „grafein“, což znamená „psát“. Z téhož základu jsou odvozena i jiná známa slova, jako např. „telegrafie“ (psaní na dálku), „fotografie“ (psaní světlem), „geografie“ (zeměpis). Z naznačeného vyplývá, že  v teorii grafů se budeme zabývat speciálním „psaním“, nebo přesněji „kreslením“,  prostřednictvím čehož budeme řešit úkoly a problémy z různých oblastí teorie i praxe.

Díky  teorii grafů na sebe navazují a vzájemně se ovlivňují obory značně vzdálené. Teorie grafů nachází svou aplikaci ve fyzice, chemii, biologii, ekonomice, lingvistice, kybernetice i v sociologii a pedagogice.

Teorie grafů patří mezi mladé matematické disciplíny. Jako systematická věda byla budovaná až od roku 1936, ale některé výsledky z teorie grafů se objevily už  omnoho dříve. Za zakladatele teorie grafů se pokládá vynikající matematik 18. století L.Euler, který v roce 1736 řešil následující úkol: Přes město Königsberg (Kaliningrad) tekla řeka Pregel, která vytvářela dva ostrovy. Rozdělovala tak město na čtyři části, které byly přepojeny sedmými mosty (Ilustrace 1). Úkolem bylo navrhnout okružní procházku po městě, při které se projde přes všechny mosty, ale po každém jenom jednou. Euler jednotlivé části města nahradil kroužky (body) a mosty nahradil čáry (spojnice mezi body) (Ilustrace 2). Přejít mosty žádaným způsobem je stejné jako nakreslit Ilustraci 2 „jedním tahem“ tak, aby smě každou čáru přešli právě jednou a vrátili se na to místo, kde smě začali. Euler nejenom ukázal, že tenhle úkol je neřešitelný, ale také vyslovil i podmínku (nutnou i postačující), kdy je možné a kdy není možné nakreslit podobný obrázek jedním tahem.

Obrázek 1: mosty v Königsbergu	Obrázek 2: graf mostů

Obrázek 2 znázorňuje to, čemu budeme v naší teorii říkat graf. Body X,Y,Z,V budeme nazývat vrcholy a čáry a,b,c,d,e,f,g hrany grafu.

Podobné „grafy“ dostaneme při zkoumaní letecké, nebo železniční dopravy. 19.století nahromadilo rad fyzikálních problému, které přispěli k rozvoji teorie grafů. Kirchhoff (1824-1887) uveřejnil svoje práce o elektronických obvodech, Cayley (1821-1895) vypracoval svojí teorii o strukturálních vzorcích v organické chemii a následovaly další práce. Krystalizoval se pojem „graf“ jako matematický objekt, který se skládá z prvků dvojakého druhu – z vrcholu a hran.

Nyní si ukážeme užitečnost takto intuitivně zavedeného pojmu na příkladech, v kterých budeme prezentovat graf jako téměř univerzální zobrazovací techniku.

Řešený příklad ⇫

Znázorněte situaci, že z pěti spolužáků A,B,C,D,E se čtyři (A,B,C,D) vzájemně kamarádí a jeden (E) "si rozumí" jenom s D.

Krok 1

Krok 2

Shrnutí ⇫

Měli bychom dokázat:

• znázornit libovolnou reálnou situaci pomocí grafu.

Úlohy k řešení⇫

1. Znázorněte pomocí grafu sousednost následujících států: Česká republika, Slovensko, Maďarsko, Německo, Polsko, Francie, Norsko, Rakousko, Chorvatsko.

2. Znázorněte situaci příbuzenských vztahů, kdy: Petr je bratr Ivany, Marta je matka Zdeňka, Jan je otec Petra, Vanda je manželka Jana, Roman je syn Zdeňka. Kolik rodin v příkladu vystupuje?

Zdroje textů

1. DIMA - diskrétní matematika, http://oliva.uhk.cz
2. Kovář, Petr. DISKRÉTNÍ MATEMATIKA a ÚVOD DO TEORIE GRAFŮ ( příklady k procvičení ), 2012