Souvislý graf
Z Wikipedie, otevřené encyklopedie
Souvislý graf je takový (neorientovaný) graf, v němž platí, že pro každé dva vrcholy x, y existuje alespoň jedna cesta 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.
[editovat] Řezy
Vrcholový řez 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.
[editovat] Příklady
- nesouvislý graf má vrcholovou i hranovou souvislost 0
- souvislý graf je (z definice) 1-souvislý
- úplný graf Kn je maximálně souvislý, jeho hranová souvislost je n
- každý strom je minimálně souvislý, jeho hranová souvislost je 1
