Graf (matematika)

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Graf alebo neorientovaný 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[upraviť | upraviť zdroj]

Neorientovaný graf[upraviť | upraviť zdroj]

Undirected graph.svg

Graf alebo neorientovaný graf G je usporiadaná dvojica G = (V, E), kde:

Príklad neorientovaného grafu:

V = {1, 2, 3, 4}
E = {{1, 2}, {1, 3}, {2, 3}, {3, 4}}

Orientovaný graf[upraviť | upraviť zdroj]

Directed graph.svg

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

Ú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, vV 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, E) a G0 = (V0, E0)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[upraviť | upraviť zdroj]

Graf G0 = (V0, E0) je podgrafom grafu G = (V, E), ak platí V0V a E0E. Potom môžeme písať G0G.

Faktorový podgraf grafu G je taký podgraf G0 = (V0, E0) , v ktorom platí V0 = V.