Graf (matematika): Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
Riadok 40:
[[Obrázok:Complete_graph_K6.svg|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 môž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 [[Zobrazenie (matematika)|funkciu]] ''w'', ktorá zobrazuje množinu hrán do množiny [[reálne číslo|reálnych čísel]] (''E → R''). Tento graf ''G = (V, E, w)'' nazývame '''hranovo-ohodnotený'''. Niekedy sa vyžaduje viac ohodnotení hrán a to vedie k použitiu viacerých funkcií.
| |||