Souvislý graf je takový (neorientovaný) graf, v němž platí, že pro každé dva vrcholy x, y existuje sled z x do y.
Pro orientované grafy se zavádí dva „druhy“ souvislosti: slabá souvislost — graf je slabě souvislý, pokud jeho symetrizace je souvislý graf; silná souvislost — graf je silně souvislý, pokud pro každé dva vrcholy x, y existuje cesta z x do y i z y do x.
Řezy Vrcholový řez (též separátor) grafu G = (V, E) je taková množina , že graf 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 v 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ů alespoň n/2 (kde n je počet vrcholů), pak je graf souvislý
Příklady nesouvislý graf má vrcholovou i hranovou souvislost 0 souvislý graf je (z definice) 1-souvislý úplný graf je maximálně souvislý, jeho hranová souvislost je n - 1 každý strom je minimálně souvislý, jeho hranová souvislost je 1
Související články Silně souvislá komponenta
Kategorie:Grafové pojmy Kategorie:Typy grafů