Graf (matematika)
Z Wikipédie
Graf je abstraktný matematický objekt daný množinou vrcholov V a množinou hrán H medzi dvojicami vrcholov. Grafy študuje matematická disciplína teória grafov a sú obvykle abstrakciou reálnych problémov či štruktúr. Typickým príkladom je modelovanie cestnej siete ako grafu, kde vrcholy sú mestá a hrany zastupujú cesty.
Obsah |
[upraviť] Definície
[upraviť] Neorientovaný graf
Graf alebo neorientovaný graf G je usporiadaná dvojica G = (V, H), kde:
- V je neprázdna konečná množina vrcholov grafu,
- H je množina neusporiadaných dvojíc typu {u, v}, kde u ≠ v, nazývaných hrany grafu.
Príklad neorientovaného grafu:
- V = {1, 2, 3, 4}
H = {{1, 2}, {1, 3}, {3, 2}, {3, 4}}
[upraviť] Orientovaný graf
Orientovaný graf alebo digraf G je usporiadaná dvojica G = (V, H), kde:
- V je neprázdna konečná množina vrcholov grafu,
- H je množina usporiadaných dvojíc typu (u, v), kde u ≠ v, nazývaných orientované hrany grafu.
Príklad digrafu:
- V = {1, 2, 3, 4}
H = {(1, 2), (1, 3), (3, 2), (3, 4), (4, 3)}
[upraviť] Ďalšie typy grafov
Ak sú v grafe povolené aj orientované, aj neorientované hrany, takýto graf sa nazýva migraf. Pripustením viacerých "rovnakých" hrán (u, v) (resp. {u, v}) získavame multidigraf (resp. multigraf). Ak v grafe existujú aj orientované, aj neorientované hrany a navyše niektoré z nich majú rovnaký aj začiatočny, aj koncový bod, nazývame tento graf multimigrafom. Graf, ktorý obsahuje aj slučky sa zvykne nazývať pseudograf (resp. pseudodigraf a pseudomigraf).
[upraviť] Diagram grafu
Diagram grafu je jeho grafickým znázornením a každý graf ma nekonečné množstvo diagramov. Jednoduchšie grafy je možné zobraziť do roviny (kde sa hrany pretínajú iba vo vrcholoch), takéto diagramy sa nazývajú rovinné. Vrcholy sa väčšinou zobrazujú ako krúžky či bodky a hrany ako čiary.
[upraviť] Vlastnosti grafov
- Triviálny graf je taký, ktorého množina vrcholov V pozostáva iba z jedného vrcholu a jeho množina hrán H je prázdna.
- Graf sa nazýva rovinným, ak k nemu existuje rovinný diagram.
- Hranová množina H úplneho grafu (resp. digrafu) obsahuje všetky kombinácie {u, v} (resp. (u, v)), také že u, v ∈ V a u ≠ v. Teda každé dva vrcholy sú spojené hranou.
- Pravidelným grafom stupňa k nazveme graf, v ktorom má každý vrchol v z V stupeň k.
- Graf sa nazýva bipartitný, ak jeho množinu vrcholov môžno rozdeliť na dve disjunktné množiny V1, V2, pre ktoré platí, že žiadne dva vrcholy z tej istej časti nie sú susedné.
- Grafy G = (V, H) a G0 = (V0, H0) sú komplementárne, ak pre ne platí, že V = V0 a pre každé dva rôzne vrcholy u, v platí {u, v} ∈ H práve vtedy ak {u, v} ∉ H0. Graf G1 = (V, H ∪ H0) je teda úplným grafom.
- Ak konkrétna aplikácia vyžaduje aby mali hrany priradenú určitú hodnotu (cenu alebo všeobecnejšie váhu), takýto graf obohatíme o funkciu c, ktorá zobrazuje množinu hrán do množiny reálnych čísel (H → R). Tento graf G = (V, H, c) nazývame hranovo-ohodnotený. Niekedy sa vyžaduje viac ohodnotení hrán a to vedie k použitiu viacerých funkcií.
[upraviť] Podgrafy
Graf G0 = (V0, H0) je podgrafom grafu G = (V, H), ak platí V0 ⊆ V a H0 ⊆ H. Potom môžeme písať G0 ⊆ G. Faktorový podgraf grafu G je taký podgraf G0 = (V0, H0) , v ktorom platí V0 = V.
