有向图的连通性

如果略去方向是连通图，则是 弱联通图 或 连通图

若任何一对结点之间至少有一个结点到另一个结点是可达的，则是 单向连通图

如果所有结点互相都可达，则是 强连通图

强连通分支 弱连通分支 单向连通分支

属于同一个强/弱连通分支的结点属于同一个 等价类

---

定理

在有向图中，任何一个定点都在唯一一个强连通分支内，在至少一个弱联通分支内

---

渡河问题 酒桶均分问题

无向赋权图的最短通路