Ohodnotený graf

Ohodnotený graf alebo vážený graf je graf, ktorého prvky sú ohodnotené číslom (váhou), ktoré určujú výhodnosť prechodu daným prvkom (cena, priepustnosť, rýchlosť, ...).

Ohodnotený graf môže byť neorientovaný alebo orientovaný. Pomocou ohodnotených grafov možno riešiť množstvo praktických problémov. Najznámejším problémom riešeným pomocou ohodnoteného grafu je problém obchodného cestujúceho.

Hranovo ohodnotený graf

Hranovo ohodnotený graf je graf s ohodnotenými hranami.

Definícia: Graf G(v,e) sa nazýva hranovo ohodnotený, ak každej hrane $e\in E$ je priradené nejaké číslo $w\in R$.

Definícia: Kladne hranovo ohodnotený graf je taký graf G, w, že $w(e)>0$

Vrcholovo ohodnoteny graf

Vrcholovo ohodnotený graf alebo uzlovo ohodnotený graf je graf s ohodnotenými vrcholmi.

Definícia: Graf G je sa nazýva vrcholovo ohodnotený, ak každému vrcholu je priradené nejaké číslo.

Graf môže byť ohodnotený súčasne hranovo aj vrcholovo. Môže mať tiež viacero ohodnotení pre hrany alebo vrcholy. Napríklad každá hrana môže mať dve ohodnotenia: rýchlosť a cenu. Optimalizácia cesty z vrcholu v do vrcholu u potom závisí od toho, akú váhu priradíme času za ktorý sa dostaneme z vrcholu v do vrcholu u a cene, ktorú za túto cestu zaplatíme.