Graf je abstraktný matematický objekt daný množinou vrcholov V (starší názov:uzly) a množinou hrán E 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.
- Poznámka: V slovenskej literatúre sa množina hrán zvykne označovať aj symbolom H. Vo svetovej literatúre sa obvykle označuje E z anglického edge.
Neorientovaný graf
Graf alebo neorientovaný graf G je usporiadaná dvojica G = (V, E), kde:
- V je neprázdna konečná množina vrcholov grafu,
- E 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}
E = {{1, 2}, {1, 3}, {2, 3}, {3, 4}}
Orientovaný graf
Orientovaný graf alebo digraf G je usporiadaná dvojica G = (V, E), kde:
- V je neprázdna konečná množina vrcholov grafu,
- E 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}
E = {(1, 2), (1, 3), (3, 2), (3, 4), (4, 3)}
Každý neorientovaný graf možno previesť na orientovaný graf, s tým istým počtom vrcholov a dvojnásobným počtom hrán.
Ď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).
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.
- Triviálny graf je taký, ktorého množina vrcholov V pozostáva iba z jedného vrcholu a jeho množina hrán E je prázdna.
- Graf sa nazýva rovinným, ak k nemu existuje rovinný diagram.
- Hranová množina E ú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 mož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, E) a G0 = (V0, E0) sú komplementárne, ak pre ne platí, že V = V0 a pre každé dva rôzne vrcholy u, v platí {u, v} ∈ E práve vtedy ak {u, v} ∉ E0. Graf G1 = (V, E ∪ E0) je teda úplným grafom. Graf G0 je komplement grafu G.
- 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 w, ktorá zobrazuje množinu hrán do množiny reálnych čísel (E → R). Tento graf G = (V, E, w) nazývame hranovo-ohodnotený. Niekedy sa vyžaduje viac ohodnotení hrán a to vedie k použitiu viacerých funkcií.
Podgrafy
Graf G0 = (V0, E0) je podgrafom grafu G = (V, E), ak platí V0 ⊆ V a E0 ⊆ E. Potom môžeme písať G0 ⊆ G.
Faktorový podgraf grafu G je taký podgraf G0 = (V0, E0), v ktorom platí V0 = V.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
