图的连通 (6)

9.3 三连通元件

3连通跟2连通真的不太一样。
以2连通来说，如果我们今天把整张图，依照关节点切开，形成很多破碎子图(也就是允许有某些边悬挂在图上，其中一个端点并不在子图的点集内，这张子图不算是一个图)，此时我们可以说对於每一个不完整的图内部的任何两个点，都能够透过两条点不重复的路径相连，而且这两条路径都在该破碎子图内部。此外，若两个点分属不同的破碎子图的话，那麽他们之间一定不存在两条点不重复的路径。

但是同样的定义套用在3连通元件却说不通。考虑下面这张图：我们知道 u 和 v 之间有3条点不重复的路径联络彼此，但是将 {u, v} 这两个点拿掉以後，会拆出三个破碎子图。考虑其中一个破碎子图，若我们挑选两个点，它虽然在原本的图上存在 3 条点不重复的路径，但是其中会有一条绕出破碎子图。也就是说我们在考虑把这些边划分出去的时候，还得考虑 3条路径有一条绕出去的情形...

(图片来源：https://d-nb.info/1010461893/34)

这个现象最早由美国数学家 MacLaine 於 1937 年率先提出。然後在 1966 年由任职於多伦多大学的英国数学家 Tutte 引进了 "虚拟边" 的概念，将 3连通图的理论更完整地刻画出来。有了这些图结构的刻画以後，接下来就是设计演算法的部分了。除了 1973 年发表的 Hopcroft-Tarjan 演算法以外，在 1989 年由两位义大利人 Di Battista (现在任职於罗马大学) 以及 Tamassia (现在任职於布朗大学) 提出了一个叫做 SPQR-树的资料结构，这让动态处理 3连通元件变得相当有效率。