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:
- 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:
- 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.