[图论] 耳分解与双极定向问题

Felix72 · 2025-07-05 10:33:25 · 算法·理论

耳分解

耳分解是一种划分图的形式。具体地，我们以一个环为主体，并在这个环上不断贴若干条链（环）上去，就像朴素的画花的方法一样。如果每次贴上去的链都不是环，即始末节点不同，则这种分解方式称作开耳分解。

我们容易用归纳法证明充分性：一个图是边双连通分量，当且仅当这张图能被耳分解。一个图是点双连通分量，当且仅当这张图能被开耳分解。对于必要性的证明，我们考虑（开）耳分解一个图，由于这个图的双连通性，我们不会遇到找不到一条新链的情况。

双极定向问题

双极定向问题可以描述如下：

给一张无向图定向，使得这张图满足以下三个条件：

• 图是一张 DAG 图；

（S, T 是给定节点。）

如果你高中选修生物，你会发现双极定向是把一个图变成一个纺锤体的过程。有定理如下：一个图可以基于 S, T 双极定向，等价于这个图加上边 (S, T) 之后是点双连通分量。充分性是容易证明的，必要性通过下面所述算法证明。

双极定向问题可以用耳分解的思路求解，算法程序如下：

• 以 S 为根建 DFS 树；
• 将 (T, 1) 这个二元组加入空队列；
• 当队列非空时：
  • 取出队首的元素 (pos, dir)；
  • 从 pos 开始不断跳父亲，途中做如下操作：
  • 如果这条边已经被标记过了，就结束循环；
  • 否则根据 dir 定向，如果 dir = 1 则向下，否则向上。
  • 找到当前父亲的所有前向边，其中若有边 (prt, x) 满足 x 在 pos 的子树里，把二元组 (x, 1 - dir) 加入队列，并根据 dir 的值给当前前向边定向。

这个算法正确性容易证明。而因为图是点双连通图，所以不会有桥或者割点存在，保证了所有边都会被定向。至此必要性被证明。