知识卡片
连通分量是可达类
无向图中可达关系是等价关系,其等价类就是连通分量。
图连通当且仅当只有一个连通分量;孤立顶点也独自构成一个分量。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 连通分量是可达类
原书出处 · 1 处
- 附录B 集合等离散数学基础 · 查看原书依据
An undirected graph is connected if every vertex is reachable from all other vertices. The connected components of an undirected graph are the equivalence classes of vertices under the “is
参考来源
- 位置:《算法导论(第4版)》附录B《集合等离散数学基础》(OEBPS/appendix002.xhtml,文本字符[20000,25000))。
- 结论依据:附录B图、树的定义及相关例子;图B.2–B.5和对应公式图已查看。
- 原始内容:An undirected graph is connected if every vertex is reachable from all other vertices. The connected components of an undirected graph are the equivalence classes of vertices under the “is