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. Významově se tak překrývá s pojmem binární relace, o grafech se ale mluví hlavně v kontextu relací nad konečnými množinami. 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. Může jít ale o v podstatě jakékoliv dobře definované vztahy mezi objekty, například na sociální síti můžeme studovat graf uživatelů (vrcholy) a jejich vzájemná propojení (hrany).
Definice[editovat | editovat zdroj]
Nejobecněji můžeme orientovaný graf definovat jako trojici , kde je množina vrcholů (někdy také uzlů), je množina hran a zobrazení určuje incidenci hran. (tj. znamená, že hrana vede z vrcholu do vrcholu .) Tato definice umožňuje existenci paralelních hran (tj. takových hran které mají stejný počáteční i koncový vrchol, tedy .) Pokud v grafu paralelní hrany nejsou, (tj. zobrazení je prosté), o grafu říkáme, že je prostý. Prosté grafy jsou v aplikacích běžné a tato vlastnost se často implicitně předpokládá a proto se často uvádí rovnou specializovaná definice, kdy graf definujeme jen jako dvojici , kde , tedy hrany identifikujeme přímo s dvojicemi vrcholů.
Neorientovaný graf můžeme definovat analogicky, s tím rozdílem, že zobrazení incidence je . Tedy u hrany nezáleží na pořadí vrcholů. Pro prosté neorientované grafy můžeme opět definici specializovat na , kde . Množina (resp. obor hodnot ) je množinou jedno (pokud ) a dvouprvkových množin vrcholů, tzv. (neorientovaných) hran. Jednoprvková množina v tomto případě značí smyčku. V aplikacích můžeme chtít uvažovat jen na grafy bez smyček a tedy se omezit pouze na dvouprvkové množiny odpovídající hranám.
Ekvivalentně můžeme pro neorientovaný graf použít definici pro orientovaný graf a vyžadovat vlastnost, že pro každou dvojici vrcholů je počet hran z do stejný jako počet hran z do , tedy respektive pro prosté grafy jednodušeji: . Pokud o grafech uvažujeme jako o relacích, neorientované grafy v tomto pojetí odpovídají symetrickým relacím.
Varianty[editovat | editovat zdroj]
- Grafu, který obsahuje smyčky, tj. hrany, které začínají i končí ve stejném vrcholu se někdy říká pseudograf. V aplikacích se běžně smyčky neuvažují.
- Pro definici grafu s paralelními hranami můžeme míst použití zobrazení incidence ekvivalentně uvažovat o jako o multimnožině. Graf s více hranami mezi týmiž vrcholy se také říká multigraf a paralelním (rovnoběžným) hranám se říká multihrany
- 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]
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]
Graf je k-regulární, pokud mají všechny jeho vrcholy stupeň právě k.
Skóre[editovat | editovat zdroj]
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]
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]
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]
Sled v grafu je posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana.
Tah[editovat | editovat zdroj]
Tah v grafu je sled, ve kterém se neopakují hrany.
Cesta[editovat | editovat zdroj]
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]
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úhelní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.
Izomorfismus grafů[editovat | editovat zdroj]
Grafy G a G’ jsou izomorfní právě tehdy, když existuje taková bijekce , ž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 .
Externí odkazy[editovat | editovat zdroj]
- Obrázky, zvuky či videa k tématu graf na Wikimedia Commons
- Doc. Ing. Vítečková Miluše CSc., Bc. Přidal Petr, Ing. Koudela Tomáš: Teorie grafů, Technická univerzita Ostrava, Listopad 2015, Dostupné online
- 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