Graf (teorie grafů)

Z Wikipedie, otevřené encyklopedie

Základní pojmy teorie grafů
Základní pojmy teorie grafů

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

[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 ρ(h1) = ρ(h2), říkáme, že h1 a h2 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
  • 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
  • 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