为有向图, 到 有通路, , 与 相互可达, .
- 具有自反性, 传递性.
- 具有自反性, 对称性, 传递性.
基图为无向连通图, 弱连通. , 单向连通. , 强连通.
定理 强连通当且仅当 中存在经过每个顶点至少一次的回路.
定理 单向连通当且仅当 中存在经过每个顶点至少一次的通路.
D=<V,E> 为有向图, vi 到 vj 有通路, vi→vj, vi 与 vj 相互可达, vi↔vj.
基图为无向连通图, D 弱连通. ∀vi,vj∈V,vi→vj∨vj→vi, D 单向连通. forallvi,vj∈V,vi↔vj, D 强连通.
定理 D 强连通当且仅当 D 中存在经过每个顶点至少一次的回路.
定理 D 单向连通当且仅当 D 中存在经过每个顶点至少一次的通路.