Graf (matematika)

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.

Definície

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

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.

Vlastnosti grafov

Úplný graf so šiestimi vrcholmi

• 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 V₁, V₂, pre ktoré platí, že žiadne dva vrcholy z tej istej časti nie sú susedné.
• Grafy G = (V, E) a G₀ = (V₀, E₀) sú komplementárne, ak pre ne platí, že V = V₀ a pre každé dva rôzne vrcholy u, v platí {u, v} ∈ E práve vtedy ak {u, v} ∉ E₀. Graf G₁ = (V, E ∪ E₀) je teda úplným grafom. Graf G₀ 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 G₀ = (V₀, E₀) je podgrafom grafu G = (V, E), ak platí V₀ ⊆ V a E₀ ⊆ E. Potom môžeme písať G₀ ⊆ G.

Faktorový podgraf grafu G je taký podgraf G₀ = (V₀, E₀), v ktorom platí V₀ = V.