Warning: session_start(): open(/tmp/sess_d1f5b8599263baf3a8fe9ee1bd4f019d, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 连通分量 ======
===== 有向图:强连通分量 =====
强连通分量中的一个点属于且仅属于一个边双连通分量。
缩点时,同一连通分量的点缩成一个点,最终会变成一个 DAG。唯一需要注意的是,重新建图时要判断原边的两个点是否在同一个强连通分量内。
===== 无向图:双连通分量 =====
==== 点双连通分量 ====
点双连通分量删掉任意一个点后仍连通,任意两个点双连通分量至多有一个共同点(因此不会有共同边,否则必然属于同一个分量),且该共同点为割点。一个点可以属于多个点双连通分量。
缩点时,同一连通分量的点缩成一个点,同时保留割点,根据从属关系将分量与割点依次相连。如果把同一连通分量的点都连到对应的割点上,貌似就是一棵圆方树(或森林)了。
特殊地,$K_1,K_2$ 是点双连通分量。
==== 边双连通分量 ====
边双连通分量删掉任意一条边后仍连通,任意两个边双连通分量互不相交(因此不会有共同点,否则必然属于同一个分量),且两个边双连通分量之间以割边链接。一个点最多属于一个边双连通分量(可以不属于任何边双连通分量)。
缩点时,同一连通分量的点缩成一个点,整个图会变成一个树(或森林)。
特殊地,$K_1$ 是边双连通分量。
==== 两种连通分量的关系 ====
- 点双连通分量一定是边双连通分量(除 $K_2$ 的特殊情况),反之不一定;
- 点双连通分量可以有公共点,而边双连通分量不能有公共边;
- 边双连通关系可以传递,但是点双连通关系不行:比如两个三元环有一个共同顶点的图,不属于同一个三元环的任意两个点是边双连通的,但不是点双连通的;
==== 割点与割边的关系 ====
割点和割边没有必然关系:两个端点是割点的边不一定是割边,割边的两个端点也不一定是割点。
下图的 $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 }}
===== 实现中可能遇到的问题 =====
- 求边双连通分量中存在重边,此时每次向儿子走时不能单纯地不回父亲节点,而是标记父边具体的编号,不选择这条边回去。比如对于有重边的 $K_2$,实际应该是一个边双连通分量。
- 给定的图不一定连通,需要处理。
===== 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 ]]