Robin定理

要证明命题：“如果一个无向图 \(G\) 有一个强定向（strong orientation），那么 \(G\) 是 2-边连通的（2-edge-connected）”，我们可以从反证法来理解。我们首先澄清几个术语：

定义澄清

强定向（strong orientation）：将无向图 \(G\) 的每条边赋予一个方向，得到有向图 \(D\)，使得 \(D\) 是强连通的（即对于任意两个顶点 \(u,v\)，都存在一条从 \(u\) 到 \(v\) 的有向路径）。
2-边连通图（2-edge-connected graph）：一个无向图 \(G\) 中没有“桥”（bridge）。也就是说，删除任意一条边，图仍然连通。

反证思路

假设 \(G\) 有一个强定向，但它不是 2-edge-connected。也就是说，\(G\) 存在一条桥（bridge）\(e\)。我们将通过这条桥的性质来得出矛盾。

桥的性质：

如果一条边 \(e = \{u,v\}\) 是桥，那么删除它会把图 \(G\) 分成两个连通块，记作 \(A\) 和 \(B\)，其中 \(u \in A, v \in B\)。
换句话说，所有从 \(A\) 到 \(B\) 的路径都必须经过这条边 \(e\)，因为这是唯一连接 \(A\) 和 \(B\) 的边。

强定向后的问题：

将这条桥定向为 \(u \to v\)，那么在有向图中，只能从 \(A\) 到 \(B\)，不能从 \(B\) 到 \(A\)，因为 \(e\) 是唯一的连接边，方向也固定。
同理，如果定向为 \(v \to u\)，就只能从 \(B\) 到 \(A\)。

这就意味着在有向图中，不可能对于所有 \(u \in A, v \in B\) 同时有路径从 \(u\) 到 \(v\) 和从 \(v\) 到 \(u\)。

推论：

所以只要 \(G\) 有桥，无论如何定向这条桥，都会导致得到的有向图不是强连通的，矛盾。

如果G是2-edge connected的，那么G有一个环（如果G没有环，那G就是一个树，就有bridge，矛盾)

命题： 在一个 2-边连通图 \(G\) 中，每条边都属于至少一个环（cycle）。

证明思路

我们要证明任意一条边 \(e\) 都在某个环中。

详细证明

假设

\(G = (V,E)\) 是一个无向图，且是 2-边连通的。
取任意边 \(e = \{u,v\} \in E\)。

目标

证明：存在一个环 \(C\) 使得 \(e \in C\)。

证明步骤

删除边 \(e\) 后，图依然连通： 因为 \(G\) 是 2-边连通的，删除任意一条边（包括 \(e\)）后，图仍然连通。所以，图 \(G' = (V, E \setminus \{e\})\) 连通。
在删除 \(e\) 后，寻找 \(u\) 到 \(v\) 的路径： 因为 \(G'\) 连通，所以存在至少一条路径 \(P\) 从 \(u\) 到 \(v\)，且 \(P\) 中不包含边 \(e\)。
构造环： 原图中有边 \(e = \{u,v\}\)，又有从 \(u\) 到 \(v\) 的路径 \(P\) 不含 \(e\)，那么把 \(e\) 和路径 \(P\) 拼接起来，就形成了一个环 \(C = P + e\)。
结论： 因此，边 \(e\) 属于环 \(C\)。

总结

任意边 \(e\) 删除后图仍连通 → 存在不经过 \(e\) 的另一条 \(u \to v\) 路径 → 和边 \(e\) 构成环。
所以 每条边都属于至少一个环。

强连通度与边连通度之间的推广性定理，它是 Thomassen 等人推广了经典 Thomassen–Nash-Williams 定理的结果。

一个无向图 \(G\) 存在一个 \(k\)-弧强定向（\(k\)-arc-strong orientation）当且仅当 \(G\) 是 \(2k\)-边连通的。

术语说明

\(k\)-arc-strong orientation：将无向图 \(G\) 的每条边赋予方向，使得所得有向图是 \(k\)-弧强连通的，即任意两个顶点间至少有 \(k\) 条互不共用边的有向路径（从 \(u\) 到 \(v\)，以及从 \(v\) 到 \(u\)）。
\(2k\)-edge-connected：无向图中任意删除少于 \(2k\) 条边，图仍保持连通。也就是说，边割集的最小容量至少是 \(2k\)。

k-linkage,arc-disjoint k-linkage

前者边不能相交，后者可以

你提到的这条是最大流与路径可分性的等价定理，在图论和网络流理论中非常重要。它是 Menger 定理、Ford–Fulkerson 定理等思想的一个具体表达。

✅ 命题：

在一个有向图 \(D\) 中，存在从源点 \(s\) 到汇点 \(t\) 的流值为 \(k\) 的流 ⇔ 存在 \(k\) 条从 \(s\) 到 \(t\) 的边不相交路径（edge-disjoint paths）。

这句话有时也可以推广成：

设 \(X, Y \subseteq V\)，那么从 \(X\) 到 \(Y\) 有 \(k\) 条边不交路径 ⇔ 可构造一个流网络 \(N_D\)，在该网络中从超级源 \(s\) 到超级汇 \(t\) 的最大流值为 \(k\)。

Fortune, Hopcroft, and Wyllie

The two-linkage problem is NP-complete.

这是真实的，是图论中一个经典的 NP 完全（NP-complete）问题，最早由 Fortune, Hopcroft, and Wyllie 在 1980 年证明。

🔍 什么是 Two-Linkage Problem？

定义如下：

给定一个有向图（或无向图） \(G = (V,E)\) 和两个顶点对 \((s_1,t_1)\)、\((s_2,t_2)\)，问是否存在两条顶点不相交（或边不相交）路径：

一条从 \(s_1\) 到 \(t_1\)，

一条从 \(s_2\) 到 \(t_2\)，

使得这两条路径互不重叠（顶点/边）。

你说的这句话是完全正确的，并且它表达了有向图中的强连通性（k-strong）与路径可分性（2-linkedness）之间的复杂而微妙的关系。

下面我们详细解释这两个结论的含义，并给出理论背景。

🧩 命题一：

对于每一个自然数 \(k\)，都存在一个 \(k\)-强连通有向图（\(k\)-strong digraph）\(D_k\)，它不是 2-linked。

✅ 概念澄清：

\(k\)-strong digraph：是指这个有向图在任意删除少于 \(k\) 个顶点后，仍然强连通（strongly connected）。
2-linked：给定两个源点对 \((s_1, t_1)\) 和 \((s_2, t_2)\)，是否存在两条顶点不相交的有向路径，一条从 \(s_1 \to t_1\)，另一条从 \(s_2 \to t_2\)。

✅ 为什么这成立？

有向图的高强连通性并不自动意味着它具有“多路径的并行能力”。
存在构造，使得图整体结构非常强连通（任意点对可互达），但仍然无法容纳两对独立的点对之间的同时不相交路径。
这是一个图结构上的障碍，而不是连通性数量的问题。

🧩 命题二：

判断一个 \(k\)-strong 的有向图是否 2-linked 是 NP-complete 的。

✅ 解释：

这个问题即：

给你一个强连通度至少为 \(k\) 的有向图，以及两对点 \((s_1, t_1)\), \((s_2, t_2)\)，问：是否存在两个顶点不交的有向路径，分别从 \(s_1 \to t_1\), \(s_2 \to t_2\)。

这个问题被称为 “2-linkage problem on k-strong digraphs”。

✅ 为什么是 NP-complete？

在 NP 中：你可以验证一组路径是否满足不交和起止点正确，在多项式时间内完成。
NP-hard：通过从 3-SAT 或 Hamiltonian path 等经典问题归约，可以构造一个 \(k\)-强连通图，使得是否存在所需路径对应于原问题的可满足性。
即使图本身非常强连通（\(k\)-strong），问题依然不易解。

🎯 补充说明

即使一个有向图非常连通（比如你删掉 10 个点都不会断），你仍然可能无法安排两对点之间走两条互不干扰的路径；
所以，强连通 ≠ 可并发路径；
这使得网络流、布线、调度等问题在有向图中比在无向图中更复杂。

Bang-Jensen & Thomassen 等图论专家在其研究中证明：

2-linkage problem can be solved in \(O(n^2)\) time for semi-complete digraphs.