Portál:Matematika/Odporúčaný článok/28 2011
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ť zdroj]
Neorientovaný graf[upraviť zdroj]
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[upraviť zdroj]
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.