Souvislý graf

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 K_n je maximálně souvislý, jeho hranová souvislost je n
• každý strom je minimálně souvislý, jeho hranová souvislost je 1

[editovat] Související články

• Silně souvislá komponenta