Robin定理

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

定义澄清

  • 强定向（strong orientation）：将无向图 的每条边赋予一个方向，得到有向图 ，使得
    是强连通的（即对于任意两个顶点 ，都存在一条从 到 的有向路径）。
  • 2-边连通图（2-edge-connected graph）：一个无向图

    中没有“桥”（bridge）。也就是说，删除任意一条边，图仍然连通。

反证思路

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

桥的性质：

  • 如果一条边
    是桥，那么删除它会把图
    分成两个连通块，记作 和 ，其中 。
  • 换句话说，所有从 到
    的路径都必须经过这条边
    ，因为这是唯一连接 和 的边。

强定向后的问题：

  • 将这条桥定向为 ，那么在有向图中，只能从 到 ，不能从 到 ，因为 是唯一的连接边，方向也固定。
  • 同理，如果定向为 ，就只能从 到 。
    这就意味着在有向图中，不可能对于所有 同时有路径从 到 和从 到 。

推论：

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

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

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

证明思路

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

详细证明

假设

  • 是一个无向图，且是
    2-边连通的。
  • 取任意边 。

目标

证明：存在一个环 使得 。

证明步骤

  1. 删除边
    后，图依然连通： 因为 是
    2-边连通的，删除任意一条边（包括 ）后，图仍然连通。 所以，图
    连通。
  2. 在删除 后，寻找 到 的路径： 因为 连通，所以存在至少一条路径 从 到 ，且 中不包含边 。
  3. 构造环： 原图中有边 ，又有从 到 的路径 不含 ， 那么把 和路径 拼接起来，就形成了一个环 。
  4. 结论： 因此，边 属于环 。

总结

  • 任意边 删除后图仍连通 →
    存在不经过 的另一条 路径 → 和边 构成环。
  • 所以 每条边都属于至少一个环。
    image-20250713235607655强连通度与边连通度之间的推广性定理，它是 Thomassen
    等人推广了经典 Thomassen–Nash-Williams 定理的结果。

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

术语说明

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

k-linkage,arc-disjoint

k-linkage
image-20250714001510268前者边不能相交，后者可以

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

✅ 命题：

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

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

设 ，那么从 到 有 条边不交路径 ⇔ 可构造一个流网络 ，在该网络中从超级源 到超级汇 的最大流值为 。

Fortune, Hopcroft, and

Wyllie
The two-linkage problem is NP-complete.

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

🔍 什么是 Two-Linkage Problem？

定义如下：

给定一个有向图（或无向图） 和两个顶点对 、，
问是否存在两条顶点不相交（或边不相交）路径：

  • 一条从 到 ，
  • 一条从 到 ，
    使得这两条路径互不重叠（顶点/边）。

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

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

🧩 命题一：

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

✅ 概念澄清：

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

✅ 为什么这成立？

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

🧩 命题二：

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

✅ 解释：

这个问题即：

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

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

✅ 为什么是 NP-complete？

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

🎯 补充说明

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

2-linkage problem can be solved in time for semi-complete
digraphs.