Graf (matematika): Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
d robot Pridal: sv:Graf (grafteori) |
|||
Riadok 45:
* 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 '''
=== Podgrafy ===
| |||