Graf (matematika)

**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

### Neorientovaný graf
right
**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* = 

### Orientovaný graf
right
**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

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

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ý graf|rovinné]]**. Vrcholy sa väčšinou zobrazujú ako krúžky či bodky a hrany ako čiary.

## Vlastnosti grafov
170px|thumb|Ú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ý graf|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*, *v* ∈ *V* a *u ≠ v*. Teda každé dva vrcholy sú spojené hranou.
* **[[Pravidelný graf|Pravidelným grafom stupňa ''k'']]** nazveme graf, v ktorom má každý vrchol *v* z *V* stupeň *k*.
* Graf sa nazýva **[[biparitný graf|bipartitný]]**, ak jeho množinu vrcholov možno rozdeliť na dve disjunktné množiny *V<sub>1</sub>*, *V<sub>2</sub>*, pre ktoré platí, že žiadne dva vrcholy z tej istej časti nie sú susedné.
* Grafy *G = (V, E)* a *G<sub>0</sub> = (V<sub>0</sub>, E<sub>0</sub>)* sú **komplementárne**, ak pre ne platí, že *V = V<sub>0</sub>* a pre každé dva rôzne vrcholy *u*, *v* platí *{u, v} ∈ E* práve vtedy ak *{u, v} ∉ E<sub>0</sub>*. Graf *G<sub>1</sub> = (V, E ∪ E<sub>0</sub>)* je teda úplným grafom. Graf *G<sub>0</sub>* je **[[komplement grafu|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 **[[ohodnotený graf|hranovo-ohodnotený]]**. Niekedy sa vyžaduje viac ohodnotení hrán a to vedie k použitiu viacerých funkcií.

### Podgrafy

Graf *G<sub>0</sub> = (V<sub>0</sub>, E<sub>0</sub>)* je **[[podgraf]]om** grafu *G = (V, E)*, ak platí *V<sub>0</sub>* ⊆ *V* a *E<sub>0</sub>* ⊆ *E*. Potom môžeme písať *G<sub>0</sub>* ⊆ *G*.

**[[Faktorový podgraf]]** grafu *G* je taký podgraf *G<sub>0</sub> = (V<sub>0</sub>, E<sub>0</sub>)*, v ktorom platí *V<sub>0</sub> = V*.

Kategória:Teória grafov