Graf (teorie grafů)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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. 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.


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

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