Graf (teorie grafů)

Z Wikipedie, otevřené encyklopedie

Graf je základním objektem teorie grafů. Je to uspořádaná dvojice (V, E), kde V je nějaká neprázdná množina a E množina některých dvojic prvků z V.

Obsah

1 Základní pojmy
2 Vlastnosti grafů
3 Rozdělení grafů
4 Důležité typy grafů
5 Reprezentace grafu
6 Isomorfismus grafů
7 Reference

[editovat] Základní pojmy

prvky množiny V se nazývají vrcholy grafu (ang. vertex), někdy se pro vrcholy používá též pojem uzly
prvky množiny E se nazývají hrany grafu a mohou to být buď uspořádané nebo neuspořádané dvojice (viz rozdělení níže) (ang. edge)
řekneme, že prvek i sousedí s prvkem j, pokud z i vede hrana do j
relace ρ z množiny E do V se nazývá incidenční relace, je-li hrana h v relaci s vrcholem u, říkáme že hrana h s vrcholem u inciduje.
je-li |ρ(h)| = 1, říkáme, že hrana h je smyčka.
platí-li, že ρ(h₁) = ρ(h₂), říkáme, že h₁ a h₂ jsou rovnoběžné hrany

[editovat] Vlastnosti grafů

Pro libovolnou hranu platí: 1 ≤ |ρ(h)| ≤ 2. Tzn, že každá hrana inciduje právě s jedním nebo právě se dvěma vrcholy

Pro libovolný graf existuje cyklomatické číslo grafu, pro které platí:

C(G) = |E| − |V| + p

kde E je množina všech hran, V je množina všech vrcholů a p je počet komponent grafu. Cyklomatické číslo C(G) značí počet nezávislých kružnic v grafu. Je-li C(G) = 0, pak graf neobsahuje kružnice.

Pro hodnost matice incidence h(A) grafu G platí:

h(A) = |V| − p

kde V je množina všech vrcholů a p je počet komponent grafu (je-li G souvisl graf, je hodnota p rovna 1).

[editovat] Rozdělení grafů

Grafy lze dělit podle mnoha různých hledisek:

podle četnosti hran
- jednoduché grafy (mezi libovolnými dvěma vrcholy vede nejvýše jedna hrana)
- multigrafy (mezi dvěma vrcholy může vést libovolný počet hran; graf je pak definován jako $G = (V, E,ε)$ , kde $\epsilon: E \rightarrow {V \choose 2}$ , neboli hrana je abstraktní objekt a funkce $ε$ určuje, které dva vrcholy tato hrana spojuje
podle orientace hran
- orientované (hrany jsou uspořádané dvojice vrcholů, tedy platí $E\subseteq{V\times V}$ )
- neorientované (hrany jsou dvouprvkové množiny vrcholů, tedy $E\subseteq{V \choose 2}$ )
podle souvislosti
- souvislé (existuje-li cesta mezi každou dvojicí vrcholů)
- nesouvislé
podle existence kružnice v grafu
- cyklické
- acyklické (např. stromy)
podle toho, lze graf nakreslit do roviny bez křížení hran
- rovinné
- nerovinné
další důležité rozdělení:
- neohodnocené grafy
- ohodnocené grafy, kde každé hraně přísluší nějaká další informace - typicky číslo, u grafů popisujících stavový automat hodnota přečtená ze vstupu. Obecně mluvíme o 'ohodnocovací funkci' - zobrazení, které každé hraně z množiny hran přiřadí 'hodnotu hrany'. Hodnota hrany může např. znamenat vzdálenost mezi vrcholy, kapacitu hrany pro přenos (informací, komodit) a jiné.

[editovat] Důležité typy grafů

[editovat] Reprezentace grafu

„obrázkem“, správně řečeno nakreslením: viz rovinný graf
maticí sousednosti: je-li |V| = n, pak čtvercová matice sousednosti A je typu $\{0, 1\}^{n\times n}$ a platí $\mathit{A}_{i,j} = 1 \Leftrightarrow \{i, j\}\in\mathit{E}$
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 $\mathbb{Z}^{n\times n}$ , pro niž platí

$(\mathit{L}_G)_{i, j} = \begin{cases} deg(i), & i = j \\ -1, &\{i, j\}\in\mathit{E} \\ 0, &i\ne j\;\land\{i, j\}\notin\mathit{E} \end{cases}$

deg(i) je počet hran, které začínají nebo končí ve vrcholu i, tzv. stupeň vrcholu

maticí incidence: je-li |V| = n a |E| = m, pak matice incidence je typu $\{-1, 0, +1\}^{n\times m}$ a platí

$(\mathit{I}_G)_{i, e} = \begin{cases} -1, & e = (i, \bullet) \\ +1, & e = (\bullet, i) \\ 0, & \mbox{jinak} \end{cases}$

Jinými slovy, každá hrana má -1 u vrcholu, kde začíná a +1 tam, kde končí. U neorientovaných grafů je na obou místech +1.

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í

[editovat] Isomorfismus grafů

Grafy G a G’ jsou isomorfní právě tehdy, když existuje takové zobrazení $f: V(G) \to V(G')$ , že platí $\{\mathit{i, j}\}\in E(G) \Leftrightarrow \{\mathit{f(i), f(j)}\}\in E(G')$ Tedy zhruba řečeno, G a G' se liší pouze „očíslováním“ svých vrcholů.

[editovat] Reference

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 prednášek Teorie grafů a diskrétní optimalizace 1 Volně ke stažení, PDF verze

Citováno z „http://cs.wikipedia.org../../../g/r/a/Graf_%28teorie_graf%C5%AF%29.html“

Kategorie: Teorie grafů