Java týden Java týden
Pouze tento týden sleva až 80 % na celý Java e-learning!
Brno? Vypsali jsme pro vás nové termíny školení OOP v Brně!

Lekce 1 - Úvod do teorie grafů

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

Cože?? Matematika??

Počkejte, jsem programátor, tohle nepotřebuji.

Graf

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ý:

Izomorfní grafy

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:

Graf – Cesta

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:

Graf – Kružnice

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:

Path

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

Strom vývoje jazyků z latiny

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ř.:

Úplný graf

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.

Podgraf

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ě).

Bipartitní graf

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á.

Orientovaný a neorientovaný graf

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.

Matice souslednosti

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).

Reprezentace v poli

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 :)

Strom

 

Stáhnout

Staženo 56x (3.71 kB)

 

 

Článek pro vás napsal Tricerator
Avatar
Jak se ti líbí článek?
5 hlasů
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Všechny články v sekci
Grafové algoritmy
Miniatura
Následující článek
Náhodný průchod grafem, průchod do hloubky a do šířky
Aktivity (8)

 

 

Komentáře

Avatar
krepsy3
Redaktor
Avatar
krepsy3:6. března 13:03

Krásný článek, jednoduchý a populárně psaný, pochopitelný i pro nematfyzáky :D :D

Jen bych rád podotknul k definici na začátku:

Definice pro normální lidi: Mějme nějaký graf, který je tvořen pomocí puntíků a čar. Puntíky jsou body, čáry jsou hrany. Hrana musí být zakončena vrcholem, jinak to není hrana.

V článku už pak nadále správně používáš pojem vrcholy, takže slovo body mi tu přijde matoucí (a zároveň je zcela objektivně nesprávné, graf nemá nic jako "body")

Takže bych to upravil takto:

Definice pro normální lidi: Mějme nějaký graf, který je tvořen pomocí puntíků (bodů) a čar (úseček). Puntíky jsou vrcholy, čáry jsou hrany. "Čára" musí být zakončena vrcholem, jinak to není hrana.

Jinak je to opravdu zdařilý článek, máš ode mě ★★★★★

Editováno 6. března 13:03
Odpovědět  +1 6. března 13:03
Programátor je stroj k převodu kávy na kód.
Avatar
Atrament
Člen
Avatar
Atrament:6. března 13:05

Víte, že vrchol na pozici i má potomky na pozici 2i a 2i + 1

nemělo by to být 2i + 1 a 2i + 2?

 
Odpovědět  +1 6. března 13:05
Avatar
Tricerator
Redaktor
Avatar
Odpovídá na Atrament
Tricerator:6. března 13:14

Máš rozhodně pravdu, 2i a 2i +1 je pro pole indexované od 1.

Odpovědět  +1 6. března 13:14
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
krepsy3
Redaktor
Avatar
Odpovídá na Tricerator
krepsy3:6. března 13:27

Ta tradičnější definice skutečně vychází z pole indexovaného od 1, což je standardní např. pro Pascal (ano, dynamická pole jsou od 0, ale ten klasický přístup to tak má), který vzniknul pro výuku programovaní.

Klasická pole indexovaná od 0 mají tu výhodu, že indexy synů mají jen jiné uzávorkování
levý 2i + 1
pravý 2(i + 1)

Samozřejmě je možné odečítat či přičítat jedničku na základě počátku indexů :)

Odpovědět 6. března 13:27
Programátor je stroj k převodu kávy na kód.
Avatar
jika knaifl
Člen
Avatar
jika knaifl:6. března 17:27

První obrázek: na grafu vlevo komunikuje v1 s v4, v3. Na grafu vpravo bych čekal totéž, ale není tomu tak. Přesto jsou izomorfní?

 
Odpovědět  +1 6. března 17:27
Avatar
Tricerator
Redaktor
Avatar
Odpovídá na jika knaifl
Tricerator:6. března 17:48

Tento graf je blbě pojmenovaný, ale i přesto izomorfní jsou. Špatně jsem to v článku napsal: nejenom přeskládáním, ale i přejmenováním vrcholů jsou grafy izomorfní. Jde o to, že grafy jsou izomorfní, pokud to, co platí pro vrcholy (u,v) tak platí i pro jejich obrazy (f(u),f(v)). Neboli pokud v grafu G vrchol u má souseda v, tak v grafu G' má vrcho f(u) souseda f(v). Neboli jak si vrcholy pojmenuji, je vlastně jedno. Nás zajímají vlastnosti. Pokud z vrcholu u vedou 4 hrany, pak z vrcholu f(u) vedou 4 hrany atd...

Editováno 6. března 17:50
Odpovědět 6. března 17:48
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
Tricerator
Redaktor
Avatar
Odpovídá na Tricerator
Tricerator:6. března 17:58

Obecně izomorfismus u grafu hledám takto. Zkusím druhý graf přejmenovat tak, aby seděl na ten první graf. Druhý graf by měl mít správně označené vrcholy vůči prvnímu takto: V_1, V_4, V_2, V_4, V_3.

Odpovědět 6. března 17:58
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
jika knaifl
Člen
Avatar
Odpovídá na Tricerator
jika knaifl:6. března 18:06

Čili pouze struktura větvení musí zůstat stejná? A co případné délky hran, ty taky musí odpovídat? A směry, v případě orientovaného grafu?

 
Odpovědět 6. března 18:06
Avatar
Tricerator
Redaktor
Avatar
Odpovídá na jika knaifl
Tricerator:6. března 18:42

Celá myšlenka izomorfismu stojí na tom, že se to jeví jinak, ale je to stejné. Jelikož nás u grafu zajímají pouze "objekty" = vrcholy a "vztahy" = hrany. Vzdálenosti nejsou důležité. Ani křížení hran nás v podstatě nezajímá. Jsou typy grafů (rovinné grafy), kde to důležité je, ale v obecných grafech ne. Směry odpovídat musí, protože jde o vztah dvou vrcholů, který musí zůstat zachován. Délky hran jsou nám jedno. Chceme-li, můžeme hrany ohodnotit (brzy se objeví ve zdrojácích) Hrana potom sama nese informaci, jestli je dlouhá 1200 ci 5 jednotek, nezávisle na délce hrany v nakreslení.

Odpovědět 6. března 18:42
Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...
Avatar
krepsy3
Redaktor
Avatar
krepsy3:16. dubna 12:49

Ono to není vyloženě blbě. Vrcholy v pravém izomorfu jsou pojmenované s čárkou. Pak lze snadno nahlédnout, že

pokud v1 ~ v1'
pak
v2 ~ v4'
v3 ~ v2'
v4 ~ v5'
v5 ~ v3'

Odpovědět 16. dubna 12:49
Programátor je stroj k převodu kávy na kód.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 10.