2020-2021:teams:i_dont_know_png:nikkukun:connected_component
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:nikkukun:connected_component [2020/05/14 01:38] nikkukun create page |
2020-2021:teams:i_dont_know_png:nikkukun:connected_component [2020/05/15 02:00] (当前版本) nikkukun add some contents of cut vertex and cut edge |
||
|---|---|---|---|
| 行 30: | 行 30: | ||
| - 点双连通分量可以有公共点，而边双连通分量不能有公共边； | - 点双连通分量可以有公共点，而边双连通分量不能有公共边； | ||
| - 边双连通关系可以传递，但是点双连通关系不行：比如两个三元环有一个共同顶点的图，不属于同一个三元环的任意两个点是边双连通的，但不是点双连通的； | - 边双连通关系可以传递，但是点双连通关系不行：比如两个三元环有一个共同顶点的图，不属于同一个三元环的任意两个点是边双连通的，但不是点双连通的； | ||
| + | |||
| + | ==== 割点与割边的关系 ==== | ||
| + | |||
| + | 割点和割边没有必然关系：两个端点是割点的边不一定是割边，割边的两个端点也不一定是割点。 | ||
| + | |||
| + | 下图的 $2, 4$ 是割点，但 $(2, 4)$ 不是割边： | ||
| + | |||
| + | {{ 2020-2021:teams:i_dont_know_png:nikkukun:connected-components-pic1.png }} | ||
| + | |||
| + | 下图的 $(1, 2)$ 是割边，但 $1, 2$ 不是割点： | ||
| + | |||
| + | {{ 2020-2021:teams:i_dont_know_png:nikkukun:connected-components-pic2.png }} | ||
| + | |||
| + | |||
| ===== 实现中可能遇到的问题 ===== | ===== 实现中可能遇到的问题 ===== | ||
| 行 37: | 行 51: | ||
| + | |||
| + | ===== Reference ===== | ||
| + | |||
| + | - [[https://byvoid.com/zhs/blog/biconnect/|图的割点、桥与双连通分支 - BYVoid]] | ||
| + | - [[https://blog.aor.sd.cn/archives/418/|点双连通分量 & 圆方树学习笔记 - RainAir]] | ||
| + | - [[https://blog.csdn.net/qq_39670434/article/details/81973923|Tarjan算法——边双和点双 - 千杯湖底沙. ]] | ||
| + | - [[https://blog.csdn.net/hailiang70303/article/details/87553759|寒假2019培训：双连通分量（点双+边双） - Purple-Ziy-fire ]] | ||
2020-2021/teams/i_dont_know_png/nikkukun/connected_component.1589391493.txt.gz · 最后更改: 2020/05/14 01:38 由 nikkukun
