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.

Obsah

[úprava] Definície

[úprava] 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:

Obrázok:Undirected graph.svg
V = {1, 2, 3, 4}
H = {{1, 2}, {1, 3}, {3, 2}, {3, 4}}

[úprava] 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:

Obrázok:Directed graph.svg
V = {1, 2, 3, 4}
H = {(1, 2), (1, 3), (3, 2), (3, 4), (4, 3)}

[úprava] Diagram grafu

Jednoduchšie grafy je možné zobraziť do roviny; vrcholy sa väčšinou zobrazujú ako krúžky či bodky a hrany ako čiary.