Souvislý graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Vrcholový řez (též separátor) grafu G = (V, E) je taková množina \mathit{U}\subseteq\mathit{V}\;, že graf G = (V\setminus U\;, E) 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ů[editovat | editovat zdroj]

  • 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ů alespon n/2 (kde n je počet vrcholů), pak je graf souvislý

Příklady[editovat | editovat zdroj]

  • nesouvislý graf má vrcholovou i hranovou souvislost 0
  • souvislý graf je (z definice) 1-souvislý
  • úplný graf K_n je maximálně souvislý, jeho hranová souvislost je n
  • každý strom je minimálně souvislý, jeho hranová souvislost je 1

Související články[editovat | editovat zdroj]