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.