有向无环图转强连通图的最小加边数定理

Terrible · 2024-03-28 17:17:06 · 算法·理论

摘要与方法简介\quad 本篇论证了通过向一个（结点数大于 1 的）有向无环图中加入有向边使其变成一个强连通图的最小加边数为 n，其中 n 为该 有向无环图 中 无入度点数 与 无出度点数 中的较大者。

（1）引理先论证了对于 有向二分图 这一特殊情形的结论，论证时通过构造二分图最大匹配将匹配部分结点记为“中游”，单向二分图起点侧剩余结点记为“上游”，终点侧剩余结点记为“下游”，并通过在中游内部加边使“中游”形成环路，即有 \forall“上游”\to“中游” \to \forall“下游”，再从下游向上游加单向边，使得 \forall“下游”\to 特定“上游”结点，以此构造了的最小加边方案，从而论证了可以加入 n 条有向边使得有向二分图变为强连通图的最小加边数；

（2）定理说明了向（结点数大于 1 的） 有向无环图 中加入小于 n 个有向边必不能使其变为强连通图，其后说明了任一 有向无环图 都可以对应一个 有向二分图 ，这意味着 有向二分图 的加边方案同样适用于对应它的 有向无环图 ，从而得到（结点数大于 1 的） 有向无环图 加有向边变成一个 强连通图 的最小加边数为 n 的结论。

定理部分论证有点问题，主要是 DAG 转 有向二分图的部分，有空再修吧

引理 单向二分图变强连通图的加边方案

引理 \quad 向 \color{fb7e18}\textsf{左侧结点} 数为 n_1，\color{398d47}\textsf{右侧结点} 数为 n_2（n_1\geqslant n_2），边均为有向边，且从 \color{fb7e18}\textsf{左侧结点} 指向 \color{398d47}\textsf{右侧结点} ，无孤立结点的有向二分图添加 n_1 条从 \color{398d47}\textsf{右侧结点} 指向 \color{fb7e18}\textsf{左侧结点} 的有向边，可以使得其变为强连通图。

注：结点 u 是图 G 中的 孤立结点 ，是指在 G 中没有任一条边以结点 u 为端点，即没有边与 u 相连，无孤立结点 意味着所有结点都有一条边与之相连。有向图 G 是 强连通图，是指 G 中任意两个结点 u,v 之间存在一条有向路径使 u,v 互相连接。特别说明：任何一点都和其本身连接。

[证明]：

设二分图 G 的（二分图）最大匹配数 {}^{[1]} 为 m( m\leqslant n_2)，就可以对应找到一组（二分图）最大匹配对依次为

进而可以找到左边点序列 u_1,u_2,\cdots,u_{n_1} 与右边点序列 v_1,v_2,\cdots,v_{n_2} 使得 G 中存在有向边 \langle u_i,v_i\rangle,i=1,2,\cdots,m。

此时在左边点序列 u_{m+1},u_{m+2},\cdots,u_{n_1} 中的一点 u_0 和右边点序列 v_{m+1},v_{m+2},\cdots,v_{n_2} 中的一点 v_0 之间不存在有向边 \langle u_0,v_0\rangle。反证：如果存在这样一条有向边，那么 \langle u_0,v_0\rangle 的两边端点都有别于之前找到的一组最大匹配对 \langle u_1,v_1\rangle,\langle u_2,v_2\rangle,\cdots,\langle u_m,v_m\rangle，于是

是一个匹配数为 m+1 的一组匹配对，与之前找到的匹配是最大匹配矛盾，所以 G 中不存在这样的一条有向边 \langle u_0,v_0\rangle，据此我们有：

由于 u_{m+1},u_{m+2},\cdots,u_{n_1} 都不为孤立结点，那么 \forall i=m+1,m+2,\cdots,n_1,\exists k_0=1,2,\cdots,m 使得 G 中存在有向边 \langle u_i,v_{k_0}\rangle；

由于 v_{m+1},v_{m+2},\cdots,v_{n_2} 都不为孤立结点，那么 \forall i=m+1,m+2,\cdots,n_2,\exists k_0=1,2,\cdots,m 使得 G 中存在有向边 \langle u_{k_0},v_i\rangle。

执行以下流程：

(i)在 G 中添加有向边 \langle v_1,u_2\rangle,\langle v_2,u_3\rangle,\cdots,\langle v_{m-1},u_m\rangle,\langle v_m,u_1\rangle 得到 G_1'；

(ii)在 G_1' 中添加有向边

\begin{aligned}&\langle v_{m+1},u_{m+1}\rangle,\langle v_{m+2},u_{m+2}\rangle,\cdots,\langle v_{n_2},u_{n_2}\rangle,\\&\langle v_{n_2},u_{n_2+1}\rangle,\langle v_{n_2},u_{n_2+2}\rangle,\cdots,\langle v_{n_2},u_{n_1}\rangle\end{aligned}

得到 G'。

定理 有向无环图转强连通图的最小加边数

定理 \quad 设 G 是 n\bigl(2\leqslant n<+\infty\bigr) 个结点的有向无环图，G 中有 n_1 个结点没有入边，n_2 个结点没有出边，那么最少需要向 G 中添加 \max(n_1,n_2) 条有向边才能使得新得到的图 G' 是一个强连通图。

注：称 G 中既存在入边也存在出边的结点为 内部结点，没有入边的结点为 无入边结点，没有出边的结点为 无出边结点。

[证明]：

注意到：若设 G 的反图为 G_r，G_r 显然也为有向无环图； G 的无入边结点在 G_r 中是无出边结点，G 的无出边结点在 G_r 是无入边结点；通过加边生成的强连通图 G' 的反图 G_r' 也会是强连通图，同样，若加边后生成的新图 G'' 不是强连通图，那么它的反图 G_r'' 也不是强连通图。故求 G 变强连通的加边数等于 G_r 变强连通图的加边数，于是不妨设 n_1\geqslant n_2。

必要性 （加少于 \max(n_1,n_2)=n_1 条边必不强连通）：

少于 \max(n_1,n_2)=n_1 条边无法使得 n_1 个无入度的点变为有入度的点，设 u 是加边后的图中无入度的点，那么存在 v 异于 u （这要求 G 有至少 2 个结点）使得 v 不能通过有向路径到达 u。

充分性 （加 \max(n_1,n_2)=n_1 条边可以强连通）：

①对 G 中任意一点 u，都存在一个无入度点 v_1 和一个无出度点 v_2，满足可以通过有向路径从 v_1 到达 u，以及通过有向路径从 u 到达 v_2。

证①：

执行以下流程：

(i)令 v=u；

(ii)若存在 G 中一条 v' 指向 v 的有向边，那么令 v=v'，重复 (ii)；否则 v 是无入边的点，即为其一所求的 v_1。

设某刻在 (ii) 中存在 v 到 u 的有向路径 r，若存在 G 中一条 v' 指向 v 的有向边，那么存在 v' 到 u 的有向路径 r'，且 r' 比 r 长度多 1。由数学归纳法可知任意时刻 v 到 u 都存在一条有向路径 r，r 的长度是执行 (ii) 的次数。这样一条有向路径长度必然小于 n<+\infty，否则根据鸽巢原理，必然有一个点被有向路径包含至少两次，从而意味着 G 中存在环，与 G 是无环图的事实相反。因而，v_1 总是可以通过这样有限次迭代找到，从而 v_1 总是存在的。

同理 v_2 也总是存在的。

于是有：

②设 G=\langle V,E\rangle 中无入边结点集合为 V_1=\{u_1,u_2,\cdots,u_{n_1}\}，无出边的点分别为 V_2=\{v_1,v_2,\cdots,v_{n_2}\}，G 中可达性有向边集为

构建二分图 G_1 为

根据引理得可以在 G_1 中加入 \max(n_1,n_2)=n_1 条边得到一个强连通图 G_1'=\langle V_1,V_2,E_1'\rangle，满足相对差集 E_1'-E_1 中有 n_1 条有向边，可知可以通过向 G 中加入 n_1 条边得到

参考文献

[1] Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics, 17, 449-467.