图论复习——dfs树,点双,边双,强连通分量

知识点

dfs树

对一个图运行 dfs 算法，每个点$u$的父亲定义为第一次遍历$u$时的前驱结点，若无则为根。
无向图的 dfs树 没有横叉边。
有向图的 dfs树 横叉边方向唯一，总是从后访问的点指向先访问的点。
dfs树详解

tarjan

点双

定义：

不存在割点的图。

性质：

两点一线型点双，较为特殊，以下在讨论特定性质时可能不纳入考虑范围。

1. 点双的dfs树上，根只有一个儿子，除叶子和根外每个点都有回边跨过。
   
2. 表述1：点双（两点一线型除外）中任意两点至少包含在一个简单环内。
   表述2：点双（两点一线型除外）中任意两点间都存在至少两条简单路径，并且这两条路径不经过相同的点。
   表述3：点双（两点一线型除外）中任意两条边至少包含在一个简单环内。
3. 对于点双中任意两点$u,v$，若点$p$在点双中，则一定存在$u-p-v$的简单路径；若点$p$不在点双中，则一定不存在$u-p-v$的简单路径。
   （对于点双中的任意一对点，连接它们的简单路径所经过点的并集一定就是这个点双本身。）
4. 对于点双中任意两点$u,v$，若边$p$在点双中，则一定存在$u-p-v$的简单路径。
5. 若点双中有奇环，由3.4.得任意两点间的简单路径有偶数长度和奇数长度的，所以点双里的所有边和点都在奇环上。
6. 一个有割点的无向图可以由若干个点双组成，点双间以割点相连接，两相邻的点双之间的公共点一定是唯一的，且一定是割点。
7. 无向图中的每个割点至少属于两个点双，其余点和每条边都只属于一个点双。
8. 点双连通分量一定是边双连通分量（两点一线型除外），反之不一定。

圆方树

圆方树是根据点双把无向图缩点所形成的树。
我们把每一个点双缩成一个 “方点”，把原有的点称作 “圆点”。然后我们把原图的边全部删除，让每个点向其所属的点双的 “方点” 连边。
显然，一个割点会向多个方点连边，而由此，除了根节点以外，所有的非割点都是叶子节点。 我们也知道，圆点和圆点之间不会互相连边，方点和方点之间也不会互相连边。

（第一个是原图，第三个是原图对应的圆方树）

应用：

• 处理有关简单路径的问题
• 处理有关图的连通性的问题
• %%%大佬的Blog

边双

定义：

不存在桥的图。

性质：

1. 边双的dfs树上，每条树边都有回边跨过。
2. 表述1：边双中任意一条边都包含在至少一个简单环中。
   表述2：边双中任意两点间都存在至少两条简单路径，并且这两条路径不经过相同的边。
3. 不是点双的边双可以由点双组成。
   
   （由两个点双组成的边双）
4. 在一个有割边的无向图中，把每一个边双缩成一个点，然后这些点之间由原来的割边相连形成了一棵树。
5. 无向图中两点一线型点双的边其实就是割边，割边不属于任何边双，而其它非割边的边都属于且仅属于一个边双。

小小总结：

点双和边双都是 由一些简单环组成的无向连通图，
不严谨地说，点双是"边的集合"，边双是"点的集合"。
图上的简单路径问题，一般用圆方树（点双）解决。

强连通分量

定义：

若有向图$G$满足：图中任意两点$u,v$间都存在从$u$到$v$的有向路径和从$v$到$u$的有向路径，则称$G$是一个强连通图。有向图的极大强连通子图，称为强连通分量。

性质：

1. 在强连通图中，每个点的入度和出度一定都不为0。
2. 把有向图中的每个强连通分量缩成一个点，将得到一个$DAG$(有向无环图)。