Graf (teorie grafů)

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Základní pojmy 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]

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ú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: Neorientovaný graf a jeho matice incidence Pro orientovaný graf: Orientovaný graf a jeho matice incidence

  • 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]

  • Logo Wikimedia Commons 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