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 |
[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 ρ(h1) = ρ(h2), říkáme, že h1 a h2 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
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í
) - neorientované (hrany jsou dvouprvkové množiny vrcholů, tedy
)
[editovat] Podle souvislosti
[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
a platí 
- 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í

- 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
a platí

- 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í
, že platí
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