图论（八）——割边割点

一、割边（桥）

$\quad$桥，顾名思义，连接两块区域的中介，桥断了，那么这两块区域便不能相互流通了。说明在一张图中，能称之为桥的边是连通图中这样一条边，如果这条边断开了，那么图便不连通。如下图所示，红色的边即为割边（桥），这些边断开了整张图便不连通。

$\quad$如何寻找这样一条边呢？直观来看，我们可以依次遍历图中每一条边，判断断开该边后该图是否连通（判断图是否连通可以从图中任一顶点开始进行DFS或者BFS，若能遍历到所有顶点则图连通，反之则不连通），若断开后图不连通则该边为割边。因为有$E$E条边，每去除一条边需要遍历整张图顶点$V$V，这样实现的时间复杂度为$O(VE)$O(VE)，很是暴力。
$\quad$不过别担心，Robert Tarjan站了出来，他提出了很多图算法，其中有专门高效解决图割边割点问题的算法，我们在讲完割点后统一实现。

二、割点

$\quad$与割边类似，割点即为一张连通图中这样一个点，删除这个点和它所连接的边，整个图变得不连通，这样的点为割点。如下图中$V_5$V5​即为割点。

$\quad$直观上来看，求图割点只需依次去除图中一个点，看去除该点后图是否连通即可。算法时间复杂度为$O(V^2)$O(V2)。同样也可以用Tarjan解决。
接下来说下割点的性质：

• 树顶点是割点，树叶($d(v)=1$d(v)=1)一定不是割点。
• 无环非平凡连通图至少有两个非割点。证明：由于G是无环非平凡连通图，所以存在非平凡生成树，而非平凡生成树至少两片树叶，它不能为割点，所以，它也不能为G的割点。
• 恰有两个非割点的连通单图是一条路。证明：设T是G的一棵生成树。由于G有n-2个割点，所以，T有n-2个割点，即T只有两片树叶，所以T是一条路。这说明，G的任意生成树为路。一个单图的任意生成树为路，则该图为圈或路，若为圈，则G没有割点，矛盾，所以，G为路。
• 若v是单图G的割点，则它不是G的补图的割点。

三、Tragan算法之求图割边割点