Lekce 1 - Úvod do teorie grafů
Cože?? Matematika??
Počkejte, jsem programátor, tohle nepotřebuji.
Chápu, že nudněji asi článek začínat nemůže. Zkusím vás však přesvědčit, že matematika je nejen docela rozumný standard, ale i velmi praktická dovednost. Proč zrovna grafy? Grafy jsou totiž velice mocný nástroj, jak vyjadřovat nějaké vztahy, ukládat data či prohledávat stavový prostor. Na začátek alespoň některé příklady využití grafů:
- Hledání nejkratší cesty
- Uspořádání adresářů v Linuxu
- Určování maximálního objemu dat, který proteče sítí
- Barvení politické mapy světa
- Ukládání objektů do stromové struktury
- a další...
Graf
Co je to vlastně graf? Pokud máte v hlavě lineární a kvadratické funkce, tak na ně (pro tentokrát samozřejmě) zapomeňte. Naše grafy vypadají úplně jinak.
Definice
Definice pro normální lidi: Mějme nějaký graf, který je tvořen pomocí puntíků a čar. Puntíky jsou vrcholy grafu a čáry jsou jeho hrany. Hrana musí být zakončena vrcholem z každé strany, jinak to není hrana.
Pokud máte rádi matematiku, definice výše ve formálnějším stylu by
byla: Mějme graf G = (V, E)
, kde (V, E)
je
uspořádaná dvojice prvků takových, že V
je množina vrcholů
grafu G
a E
je množina hran, které spojují vrcholy
z V
.
Pokud nejste obeznámeni s matematickým postupem, tak jen drobná vysvětlivka. Tato definice v podstatě říká, že graf je pro nás důležitý skrze to, že známe vrcholy a hrany. Všimněme si, že je (většinou) jedno, jak tento graf nakreslíme. To je velmi důležité, v počítači nemusíme mít souřadnice bodů či nic podobného, stačí nám mít uložený seznam vrcholů a hran.
Dva grafy níže jsou v podstatě identické (tzv. izomorfní). Když se pozorně podíváte, graf má pět vrcholů a z každého vedou dvě hrany. Přeskládáním prvního dostanete druhý:

Co může být ve vrcholech a co v hranách? To je na vás, grafy slouží vám, ne vy jim.
Příklad č.1 - Rybičky
Jste ředitelem obrovské firmy na dodávání rybiček v Republice. Máte v počítači mapu největších měst. Mezi nimi povedou hrany, značící vaše logistické cesty. Každý vrchol (město) bude obsahovat počet obyvatel, počet podniků a velikost skladovacího prostoru. Každá hrana obsahuje informace o délce cesty, pravděpodobnosti zácpy a jména řidičů, kteří tyto cesty jezdí.
Příklad č.2 - Úředník
Jste vládní úředník a chcete si naplánovat dodání všech hlasovacích lístků co nejefektivněji. Vzhledem k možným potížím s korupcí všechny lístky tisknete u sebe v kanceláři. Přijedou si je vyzvednout ozbrojené síly, které je budou převážet na menší a menší úřady, až se dostanou na obvodní policii, která je zanese do schránky. Máte tedy orientovaný graf, kde v hranách můžete uložit informaci o maximálním množství lístků, které se vejde do auta a počet vojáků strážících konvoj. Ve vrcholech mohou být otevírací doby jednotlivých úřadů a počet úředníků.
Typy grafů
Nyní když víme, co je to graf, podíváme se na nejdůležitější typy grafů.
Cesta
Cesta je posloupnost vrcholů a hran, kde existuje pouze jeden způsob, jak
se dostat z vrcholu V
do vrcholu U
:

Neboli je to vždy cik-cak dvojice vrchol, hrana, vrchol, hrana... Je to velmi jednoduchá struktura, nic moc k vidění, popojedeme!
Kružnice
Kružnice již je mnohem zajímavější. Můžeme jí definovat jako cestu, jejíž koncové vrcholy spojíme do jednoho:

Tak například si nakreslete trojúhelník. To je nádherná kružnice. Vyjdete z vrcholu jednou hranou a vrátíte se druhou. Samozřejmě většinou máme v grafu větší kružnice, ale to na kráse tohoto matematického vtípku nic nemění.
Strom
Strom je naprosto stěžejní struktura, které se budeme věnovat podrobněji. Můžeme jej zadefinovat jako souvislý graf bez kružnic neboli graf, kde mezi každými dvěma vrcholy existuje cesta. Je to také graf, kde existuje jeden kořen (anglicky root), který nemá žádného předka a může obsahovat potomky. Poslední vrchol, který nemá žádného potomka, se označuje pojmem list (anglicky leaf).
Například struktura adresářů na Linuxu má přesně takovýto model.
Máme kořen /
, ze kterého pak vycházejí adresáře
bin/
, etc/
, tmp/
a další...
To vypadá např. takto:

Zde uvádím strom vývoje jazyků z latiny. O důvod navíc učit se stromy.
A latinu

Strom má však mnohem více využití. Je to dobrá datová struktura. Druhů stromů je opravdu celá řada a všechny splňují jeho definici + něco navíc. B-stromy, B+-stromy, červeno-černé stromy, binární stromy, haldy atd...
No a to je ke stromu obecně všechno. Překvapeni? Ty nejjednodušší nápady mohou být i elegantní i geniální.
Uplný graf
Úplný graf na n
vrcholech je graf, ve kterém je každý
vrchol propojen se všemi ostatními.
Např.:

Podgraf
Podgraf grafu G
je opět graf, který získáme odebráním hran
nebo vrcholů. Prázdná množina, tj. graf s 0 vrcholy je podgraf libovolného
grafu.

Bipartitní grafy
Bipartitní graf Gn,m
je graf, který můžeme rozdělit na dvě
části. Každá z těchto částí obsahuje pouze hrany do druhé, tj.
neexistuje hrana, která by spojovala dva vrcholy v jedné části
(partitě).

Další dělení
Grafy můžeme dělit i následujícími způsoby.
Orientovaný vs. neorientovaný graf
Orientovaný graf je graf, kde máme přidanou informaci o tom, odkud kam hrana vede. Představte si město. Pokud uděláte graf ulic pro chodce, tak určitě bude graf neorientovaný. Chodec si může jít tam i zpět, jak se mu zlíbí. Pokud uděláte graf ulic pro řidiče aut, ve městě je jistě spousta jednosměrek, a dokonce i silnice je v podstatě jednosměrná.

Spojitý vs. nespojitý
Jak název napovídá, jedná se o to, zda z každého vrcholu existuje cesta do jiného. Pokud ano, graf je spojitý. Spojité grafy se dobře ukládají do počítače, s nespojitými je už o maličko větší režie.
Reprezentace grafů
Nyní, když již máme nějakou představu, jak graf vypadá a co dělá, nabízí se poslední otázka, jak ho uložit do nul a jedniček v počítači. Na to není jednoznačná odpověď. Záleží na typu grafu a co s nimi chcete dělat. Ukážeme si dvě nejčastější reprezentace grafu. Doporučuji se podívat do přiložených zdrojových kódů, kde přímo ukazuji konkrétní typy grafů a jejich reprezentaci.
Matice souslednosti
Pro neorientované grafy budeme mít symetrickou matici, kde
Aij = 1
pokud Vi
sousedí s Vj
a
0
pokud nikoliv. Pro orientované grafy to bude nesymetrické. To,
že sousedí Vi
s Vj
neznamená, že sousedí
Vj
s Vi
. Tedy to, že víte, jak se dostat z
X
do Y
po jednosměrce neznamená, že to umíte i
nazpátek.

Reprezentace v poli
Jednoduché typy grafů, např. binární stromy, tj. kde každý uzel má
právě 2 potomky kromě listů, se dají efektivně uložit v obyčejném poli.
Víte, že vrchol na pozici i
má potomky na pozici
2i + 1
a 2i + 2
. Zde máme příklad binárního
stromu, konkrétně haldy. Halda je datová struktura, kde předek stromu je
vždy menší než potomek (kořen je minimum).

To je pro začátek všechno. Samozřejmě to není vyčerpávající popis
všech možností. Hlavní je si uvědomit jedno. Grafy nám dávají nástroj,
jak skládat data k sobě, ne povinnost je rvát kamkoliv můžeme. Střídmost
je hlavní ctností programátora. Tak ať vám stromečky kvetou

V další lekci, Náhodný průchod grafem, průchod do hloubky a do šířky, si ukážeme náhodný průchod grafem, průchod do hloubky a do šířky.
Stáhnout
Stažením následujícího souboru souhlasíš s licenčními podmínkamiStaženo 739x (3.71 kB)