Definícia

Graf je usporiadaná dvojica G=(V,E):
 konečná neprázdna množina vrcholov V a
 (aj prázdna) množina hrán E
Vrchol (node) sa dá intuitívne predstaviť ako mesto na mape a hrana (edge) ako cesta medzi dvoma mestami. Potom je V množina všetkých miest a E množina všetkých ciest medzi nimi.

^ TOP

Grafická reprezentácia

Najčastejšia grafická reprezentácia grafov je zobrazovať vrcholy ako body alebo krúžky a hrany ako čiary medzi nimi. Vrcholy a hrany môžu byť ohodnotené. To znamená, že majú asociovanú číselnú hodnotu. Tieto grafy sa volajú hranovo alebo vrcholovo ohodnotené grafy (edge- and vertex-weighted graphs). Priradená hodnota sa nazýva váha (weight).

^ TOP

Základné pojmy

Hrana sa nazýva slučka (self-loop), keď je tvaru (u,u). Graf sa nazýva jednoduchý (simple), keď neobsahuje slučky a násobné hrany (viac hrán medzi rovnakými vrcholmi). Ak graf obsahuje slučky a násobné hrany, nazýva sa multigraf (multigraph). Hovoríme, že hrana (u,v) susedí (inciduje) s vrcholom u a vrcholom v. Stupeň vrcholu je počet hrán, ktoré s ním susedia. Vrchol v susedí s vrcholom u, ak existuje hrana incidentná k obom vrcholom (tj. hrana medzi nimi). Počet vrcholov grafu značíme N. Hovoríme, že graf je riedky (sparse), keď počet jeho hrán M je malý v porovnaní s počtom všetkým možných hrán N(N-1)/2. Inak hovoríme, že graf je hustý (dense).

^ TOP

Orientované grafy

Ak je hranám priradený smer, hovoríme o orientovaných grafoch (directed graphs) a hrany sa potom nazývajú orientované hrany. Podobne, ak nie je hranám priradený smer, sú to neorientované hrany a graf je tiež neorientovaný (undirected). Hrany v orientovaných grafoch sa zobrazujú šípkami, ktoré učujú ich smer. Odchádzjúci stupeň vrcholu (out-degree) je počet orientovaných hrán, ktoré majú v danom vrchole začiatok. Prichádzajúci stupeň vrcholu (in-degree) je počet hrán končiacich vo vrchole.

^ TOP

Cesty v grafe

Cesta (path) z vrcholu x do vrcholu y je postupnosť vrcholov (v0, v1,..., vk) taká, že v0=x a v0=x a hrany (v0,v1),(v1),v2)),... patria do množiny hrán E. Dĺžka takejto cesty je k. Cesta je jednoduchá, ak neobsahuje žiaden vrchol viac ako raz. Cestu nazývame cyklom, ak má začiatok a koniec v tom istom vrchole. Cyklus je jednoduchý, ak neobsahuje žiaden vrchol okrem počiatočného viac ako raz.

^ TOP

Dosiahnuteľnosť

Vrchol v nazývame dosiahnuteľným z vrcholu u, ak existuje cesta z u do v. Neorientovaný graf nazývame spojitým alebo súvislým (connected), keď existuje cesta z každého vrcholu do každého iného. Komponent grafu je maximálna množina vrcholov s vlastnosťou, že každý jej vrchol je dosiahnuteľný z každého iného vrcholu v komponente.

^ TOP

Špeciálne typy grafov

Neorientovaný graf nazývame stromom (tree), keď je acyklický a je súvislý. Hovoríme, že strom je zakorenený (rooted), keď sme jasne vyznačili jeho najvyšší vrchol – koreň (root).Každý vrchol v strome má práve jedného otca (parent) a rôzny počet synov (children). Neorientovaný graf, ktorý neobsahuje cykly je les (forest). Orientovaný acylkický graf sa nazýva DAG (directed acyclic graph). Graf je úplný, ak obsahuje hranu medzi každou dvojicou vrcholov. Graf je bipatitný, ak môže byť rozdelený na dve množiny V a W tak, že hrany vedú len z V do W alebo z W do V.

^ TOP

Vizualizácia

Na obrázku je zobrazený graf G=(V, E), kde V={1,2,3,4,5} a E={(1,2),(1,3),(2,3),(3,4)}. Graf je jednoduchý, (lebo neobsahuje slučku ani násobnú hranu), je neorientovaný, neohodnotený, obsahuje cyklus a nie je spojitý. Graf je riedky, lebo obsahuje 4 hrany a počet možných hrán je 10. Vrchol 5 sa nazýva izolovaný. Stupeň vrcholu 3 je tri a stupeň vrcholu 5 je nula. Počet komponentov v tomto grafe je dva. Sú to (1,2,3,4) a (5).

Rozdiel medzi orientovaným a neorientovaným grafom.

^ TOP