Graf (teorie grafů)

Graf je základním objektem teorie grafů. Jedná se o reprezentaci množiny objektů, u které chceme znázornit, že některé prvky jsou propojeny. Objektům se přiřadí vrcholy a jejich propojení značí hrany mezi nimi. Grafy slouží jako abstrakce mnoha různých problémů. Často se jedná o zjednodušený model nějaké skutečné sítě (například dopravní), který zdůrazňuje topologické vlastnosti objektů (vrcholů) a zanedbává geometrické vlastnosti, například přesnou polohu.
Obsah
Definice[editovat | editovat zdroj]
Neorientovaný graf je dvojice , kde V je neprázdná množina tzv. vrcholů (někdy také uzlů) a je množina dvouprvkových množin vrcholů, tzv. (neorientovaných) hran.
Orientovaný graf je dvojice , kde V je neprázdná množina tzv. vrcholů (uzlů) a je množina uspořádaných dvojic vrcholů, tzv. (orientovaných) hran.
Hrana se tedy u neorientovaných grafů chápe jako dvouprvková množina vrcholů . Říkáme, že hrana vede mezi u a v, popř. spojuje u a v. To odpovídá záměru: Graf je neorientovaný, tj. na pořadí vrcholů u hrany nezáleží.
U orientovaných grafů se hrana chápe jako uspořádaná dvojice vrcholů u a v. Pak říkáme, že hrana vede z u do v. I to odpovídá záměru: Graf je orientovaný, tj. na pořadí vrcholů u hrany záleží. Hrana je tedy něco jiného než hrana . Koncové vrcholy hrany jsou u neorientované hrany vrcholy u a v, u orientované hrany také vrcholy u a v.
Varianty[editovat | editovat zdroj]
- Někdy se v grafu hodí povolit takzvané smyčky, hrany, které začínají i končí ve stejném vrcholu. Takovému grafu se někdy říká pseudograf.
- Pokud je E multimnožina, pak se jedná o multigraf a násobným hranám se říká multihrany nebo paralelní (rovnoběžné) hrany.
- Hranám je možné určit orientaci, pak se jedná o orientovaný graf. Většinou se značí šipkou z jednoho vrcholu do druhého a říká se, že hrana e=(u,v) vede z u do v.
Zobecněním grafu takovým, že hrany nemusí obsahovat právě dva vrcholy, je hypergraf.
Okolí vrcholu[editovat | editovat zdroj]
Sousedství[editovat | editovat zdroj]
Pokud jsou dva vrcholy spojeny hranou, říká se, že spolu sousedí. Všechny vrcholy, se kterými daný vrchol v sousedí, jsou jeho sousedství nebo okolí N(v).
Stupeň[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Stupeň vrcholu.
Stupeň vrcholu deg(v) je velikost jeho sousedství. V případě orientovaných grafů se rozlišuje vstupní stupeň deg+(v), počet hran, které vcházejí do vrcholu v, a výstupní stupeň deg-(v), počet hran, které vychází z vrcholu v.
Regularita[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Regulární graf.
Graf je k-regulární, pokud mají všechny jeho vrcholy stupeň právě k.
Skóre[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Skóre grafu.
Skóre grafu je multimnožina stupňů všech vrcholů.
Princip sudosti[editovat | editovat zdroj]
Platí rovnost , neboť každá hrana přispěje k sumě právě hodnotou 2.
Speciální stupně grafu[editovat | editovat zdroj]
Často se používají hodnoty minimálního a maximálního stupně přes všechny vrcholy, minimální stupeň , maximální stupeň a průměrný stupeň .
Podgrafy a minory[editovat | editovat zdroj]
Odebrání hrany[editovat | editovat zdroj]
Pokud e je hrana grafu G, G-e označuje graf na stejné množině vrcholů s množinou hran . (graf pak neobsahuje hranu e)
Odebrání vrcholu[editovat | editovat zdroj]
Pokud v je vrchol grafu G, G-v označuje graf na množině vrcholů a jeho množina hran se liší od původní tím, že neobsahuje hrany vrcholu v, tedy .
Podgraf[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Podgraf.
Graf G je podgraf grafu G’, pokud může vzniknout z G’ odebráním nějakých vrcholů a hran.
Indukovaný podgraf[editovat | editovat zdroj]
Graf G je indukovaný podgraf grafu G’, pokud může vzniknout z G’ odebráním nějakých vrcholů.
Kontrakce hrany[editovat | editovat zdroj]
Pokud e={u,v} je hrana grafu G, G.e označuje graf, který vznikne z G odstraněním e a identifikací vrcholů u a v. Pokud má vzniknout obyčejný graf, požaduje se odstranění násobných hran a smyček, které mohly vzniknout.
Minor[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Minor (teorie grafů).
Graf G je minor grafu G’, pokud může vzniknout z G’ odebráním nějakých vrcholů a hran a kontrakcí hran.
Sledy, tahy, cesty[editovat | editovat zdroj]
Sled[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Sled (graf).
Sled v grafu je posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana.
Tah[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Tah (graf).
Tah v grafu je sled, ve kterém se neopakují hrany.
Cesta[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Cesta (graf).
Cesta je sled, ve kterém se neopakují vrcholy, tedy každý vrchol se v cestě objevuje nejvýše jednou. Existuje-li mezi dvěma vrcholy sled v grafu, existuje mezi nimi i cesta (protože každý úsek mezi dvěma výskyty stejného vrcholu se dá „vystřihnout“).
Na všechny tyto pojmy se dá také nahlížet jako na podgraf.
Souvislost[editovat | editovat zdroj]
Graf je souvislý, pokud mezi každými dvěma vrcholy existuje cesta. V případě orientovaných grafů se mluví o silné souvislosti, pokud mezi každými dvěma vrcholy v obou směrech existuje cesta respektující orientaci.
Komponenta souvislosti[editovat | editovat zdroj]
- Podrobnější informace naleznete v článku Komponenta grafu.
Komponenta souvislosti je každý v inkluzi maximální souvislý podgraf. Souvislé grafy jsou právě ty, co mají pouze jednu komponentu souvislosti. U orientovaných grafů se navíc rozlišují silně souvislé komponenty.
Důležité typy grafů[editovat | editovat zdroj]
Reprezentace grafu[editovat | editovat zdroj]
- „obrázkem“, správně řečeno nakreslením: viz rovinný graf
- maticí sousednosti: je-li |V| = n, pak čtvercová matice sousednosti A je typu a platí . Pokud je graf neorientovaný, stačí na jeho reprezentaci (horní nebo dolní) trojúhejníková matice.
- maticí vzdálenosti: jsou-li hrany grafu ohodnocené, lze výše uvedenou matici modifikovat tak, že místo jedničky je na daném pozici uvedeno ohodnocení (délka) příslušné hrany
- Laplaceovou maticí: opět čtvercová matice, tentokrát typu , pro niž platí
- maticí incidence: je-li |V| = n a |E| = m, pak matice incidence je typu a platí
- Jinými slovy, každá hrana má 1 u vrcholu kde začíná a -1 u vrcholu kde končí. U neorientovaných grafů je vždy +1 když je hrana v incidenci s vrcholem.
Pro neorientovaný graf: Pro orientovaný graf:
- seznamem sousedů: je-li |V| = n, uspořádáme vrcholy grafu do pole velikosti n a v i-tém prvku tohoto pole bude ukazatel na spojový seznam vrcholů, které s vrcholem i sousedí. Toto uspořádání je vhodné při množství údajů menším než n^2. Tj. při ostře menším počtu hran než n^2, kde n je počet vrcholů. Jedná se o tzv. řídké grafy, kterých je v prostředí sítí nejvíce.
Isomorfismus grafů[editovat | editovat zdroj]
Grafy G a G’ jsou isomorfní právě tehdy, když existuje takové zobrazení , že platí Tedy zhruba řečeno, G a G' se liší pouze „očíslováním“ svých vrcholů.
Ohodnocení grafu[editovat | editovat zdroj]
Pro některé účely se vrcholy nebo hrany grafu ohodnocují, například reálnými čísly, pomocí ohodnocovací funkce nebo .
Reference[editovat | editovat zdroj]
- Jiří Matoušek, Jaroslav Nešetřil: Kapitoly z diskrétní matematiky, nakladatelství Karolinum, Praha 2002, ISBN 80-246-0084-6
- Roman Čada, Tomáš Kaiser, Zdeněk Ryjáček: Diskrétní matematika, Západočeská univerzita v Plzni, Březen 2004, ISBN 80-7082-939-7
- Zdeněk Ryjáček: Pracovní texty přednášek Teorie grafů a diskrétní optimalizace 1 Volně ke stažení, PDF verze
- prof. RNDr. Radim Bělohlávek, DSc.: Algoritmická matematika 2 Volně ke stažení, PDF verze
- Jiří Demel: Grafy a jejich aplikace, nakladatelství Academia, Praha 2002, ISBN 80-200-0990-6