Graf (matematika): Rozdiel medzi revíziami

Smazaný obsah Přidaný obsah
Vegbot (diskusia | príspevky)
typo gram
Riadok 10:
 
* ''V'' je neprázdna konečná [[množina]] '''vrcholov''' grafu,
* ''E'' je množina [[Neusporiadaná dvojica|neusporiadaných dvojíc]] typu {''u'', ''v''}, kde ''u ≠ v'', nazývaných '''hrany''' grafu.
 
Príklad neorientovaného grafu:
Riadok 21:
 
* ''V'' je neprázdna konečná [[množina]] '''vrcholov''' grafu,
* ''E'' je množina [[usporiadaná dvojica|usporiadaných dvojíc]] typu (''u'', ''v''), kde ''u ≠ v'', nazývaných '''orientované hrany''' grafu.
 
Príklad digrafu:
Riadok 43:
* 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ôžnomož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 '''[[ohodnotený graf|hranovo-ohodnotený]]'''. Niekedy sa vyžaduje viac ohodnotení hrán a to vedie k použitiu viacerých funkcií.
Riadok 49:
=== 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]]