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 Užití
3 Vlastnosti grafů
4 Rozdělení grafů
5 Důležité typy grafů
6 Reprezentace grafu
7 Isomorfismus grafů
8 Reference

[editovat] Základní pojmy

prvky množiny V se nazývají vrcholy grafu, 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)
ř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 u je incidentní s h.
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] Užití

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ů), tedy zejména jejich vzájemné propojení a zanedbává geometrické vlastnosti, například přesnou polohu.

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

[editovat] Podle četnosti hran

Prosté grafy - tyto grafy nemají rovnoběžné hrany, tzn. mezi libovolnými dvěma vrcholy vede nejvýše jedna hrana
Multigrafy - mezi dvěma vrcholy multigrafu může vést libovolný počet hran; graf je pak definován jako $G = (V, E,ε)$ . Hrana je abstraktní objekt a funkce $\epsilon: E \rightarrow {V \choose 2}$ určuje, které dva vrcholy tato hrana spojuje

Dále pak také:

řídké grafy - grafy s relativně malým množstvím hran (vzhledem k počtu vrcholů).
husté grafy

[editovat] 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}$ )

[editovat] Podle souvislosti

souvislé (existuje-li cesta mezi každou dvojicí vrcholů)
nesouvislé

[editovat] Podle existence kružnice v grafu

cyklické
acyklické (např. stromy)

[editovat] Podle toho, zda lze graf nakreslit do roviny bez křížení hran

rovinné (tež planární)
nerovinné

[editovat] 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í. 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.

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

---

Jiří Demel: Grafy a jejich aplikace, nakladatelství Academia, Praha 2002, ISBN 80-200-0990-6