Souvislý graf: Porovnání verzí
Smazaný obsah Přidaný obsah
oprava textu, (viz. KOLÁŘ, Josef. Teoretická informatika definice 2.14) |
přidání vlastností. zdroj: diskrétní matematika, přednášky, učebnice značka: editace z Vizuálního editoru |
||
Řádek 8:
''Vrcholový řez'' (též separátor) grafu ''G = (V, E)'' je taková množina <math>\mathit{U}\subseteq\mathit{V}\;</math>, že graf <math>G = (V\setminus U\;, E)</math> není souvislý. Obdobně se definuje ''hranový řez''. ''Vrcholová (resp. hranová) souvislost'' grafu je velikost minimálního vrcholového (resp. hranového) řezu. Graf je vrcholově (hranově) ''k-souvislý'', pokud jeho příslušná souvislost je rovna nebo větší než ''k''.
== Vlastnosti souvislých grafů ==
* Každý souvislý graf G obsahuje vrchol ''<u>v</u>'' s vlastností, že G - v (tzn. z grafu G odstraníme jeden konkrétní vrchol v) je souvislý graf
* V souvislém grafu je m ≥ n - 1 (kde ''m'' je počet hran a ''n ''je počet vrcholů)
* Jsou-li stupně včech vrcholů alespon n/2 (kde n je počet vrcholů), pak je graf souvislý
== Příklady ==
*nesouvislý graf má vrcholovou i hranovou souvislost 0
| |||