Menger 定理

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Mar.18 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

Menger 定理

    Menger 定理是图的连通性问题的核心结论之一，它描述了「图的连通度」与「连通图中不同点对间的不相交路的数目」之间的关系。下面我们先给出一些定义，然后给出 Menger 定理。

一些定义

    设 `u` 与 `v` 是图 `G` 的两个不相邻顶点, `S` 是 `G` 的一 个顶点子集，如果 `u` 与 `v` 不在 `G−S` 的同一分支上, 则称 `S` 分离 (Separate) `u` 和 `v` ，`S` 为 `u` 和 `v` 的 分离集。

    如上图所示，`{u_1,u_4}` 和 `{u_1u_2,u_1u_4,u_4u_6}` 分离了点 `u_2` 和 `u_6`。

    图 `G` 的一族路，如果它们的内部顶点都不相同，则称它们是 内部不交 (Internally Disjoint)的。

    图 `G` 的一族路，如果它们没有公共边，则称它们是 边不重 (Edge-disjoint) 的。

原生 Menger 定理

    顶点版本的 Menger 定理 如下所示:

设 `x` 与 `y` 是图 `G` 中的 不相邻点，则 `G` 中分离 `x` 和 `y` 的最少点数等于 `G` 中内部不交的 `x`,`y` 路的最大数目

    简单可以理解为：要使得 `x` 和 `y` 分离，则需要从内部不交的 `x``y` 路上各自至少删去一个点，也即 |分离集| `\ge` |内部不交的路的条数|。Menger 定理证明了等号是成立的。

    如上所示，独立的 `x`,`y` 路最大条数是 `2` (红色和蓝色路)，分离点 `x` 与 `y` 的最小分离集是 `{u_1,u_4}`，包含两个顶点。

    边版本的 Menger 定理 如下所示:

设 `x` 与 `y` 是图 `G` 中的 不同点，则 `G` 中分离点 `x` 和 `y` 的最少边数等于 `G` 中边不重的 `x`,`y` 路的最大数目

    如上图所示，边不重的 `x`,`y` 路最大条数是 `2` (红色和蓝色路，虽然和上面例子中的两条路相同，但是定义不同。这个例子中的「边不重的 `x`,`y` 路」和「不相交的 `x`,`y` 路」恰巧相同)。分离点 `x` 与 `y` 的最小边分离集是 `{xu_1,xu_4}`，包含两条边。

Whitney Menger 定理

    Whitney 针对 `k` 连通图的改进的 Menger 定理如下所示:

非平凡简单图 `G` 是 `k` (`k \ge 2`) 连通的，当且仅当 `G` 的任意两个顶点 `u` 和 `v` 之间至少存在 `k` 条内部不交路

    证明:

    必要性: 由于 `G` 是 `k` (`k \ge 2`) 连通的，设 `u` 和 `v` 是 `G` 的两个顶点，分两种情况讨论:

1. 若 `u` 和 `v` 不相邻，则存在点割可以分离 `u` 和 `v`，设这个分离集为 `U`，因此有 `|U| \ge \kappa(H) \ge k`。由 menger_1 可得，`u` 和 `v` 之间存在至少 `k` 条内部不交路。
2. 若 `u` 和 `v` 相邻，考虑删除连接 `u` 和 `v` 的邻边，则此时 `u` 和 `v` 不相邻，设此时的图为 `G'`。由 `\kappa(G)-1 \le \kappa(G-e) \le \kappa(G)` (p.s. 在下面 extra 进行证明) 可得，`G'` 是 `k-1` 连通的。则由 menger_1 可得，在 `G'` 中，`u` 和 `v` 之间至少存在 `k-1` 条内部不交路。则再加上删去的那一条边，`u` 和 `v` 之间就至少有 `k` 条内部不交路。

    充分性: 证明思路是证明不存在 `k-1` 点割。

1. 若 `G` 不存在点割，则 `G` 是完全图，故任意顶点之间存在 `n-1` 条内部不交路 (i.e. 经过其它 `n-2` 个 点的路，以及经过 `u` 和 `v` 的邻边)
2. 若 `G` 存在点割，且 `u` 和 `v` 不相邻，设 `U` 是分离 `u` 与 `v` 的最小点割，则 `G−U` 不连通。已知 `u` 与 `v` 之间至少存在 `k` 条内部不交路，若 `|U| = \kappa(G) \le k−1`，则 `G−U` 中至少至少存在一条 `u`,`v` 路，即 `G−U` 连通，这与假设矛盾，说明不存在 `k-1` 点割，所以有 `\kappa(G) \ge k`，即 `G` 是 `k` 连通的。
3. 若 `G` 存在点割，且 `u` 和 `v` 相邻，考虑删除 `uv` 边的图 `G'`，则图 `G'` 属于情况 2，可得图 `G'` 是 `k-1` 连通的，加回 `uv` 边，可得图 `G` 是 `k` 连通的

    menger_3 是定义完全图 (或以完全图为生成子图) 的连通度为 `n−1` 的依据 (因完全图中任意两点间都有 `n−1` 条内部不交路)。

    下面对上面用到的 extra 进行证明，该定理可以与我们上一篇文章中介绍过的 `\kappa(G)-1 \le \kappa(G-v)` 相比较。

`\kappa(G)-1 \le \kappa(G-e) \le \kappa(G)`

    证明: TODO!!!

    先证右边的不等号: 首先，`G` 的点割一定是 `G-uv` 的点割，故有`G` 的最小点割一定是 `G-uv` 的一个点割 (不一定是最小点割)，因此有 `\kappa(G-e) \le \kappa(G)` 成立。

    现在证明左边的不等号: 下设 `\kappa(G-uv) < \kappa(G)`，令 `V_{min}` 是 `G-uv` 的一个最小点割，但 `V_{min}` 不是 `G` 的一个点割，也即 `G-V_{min}` 是连通的。假设 `G-uv-V_{min}` 有两个连通分支 `X` 和 `Y`，下面分情况讨论:

• 若
• 若 `|X|=|Y|=1`，则说明 `V_{min}` 是一个 `n-2` 的集合，故

Menger 定理扩张引理

    下面我们给出 Menger 定理的扩张引理。

设 `G` 是 `k` 连通图，`S` 是由 `G` 中任意 `k` 个顶点构成的集合。若图 `H` 是由 `G` 通过添加一个新点 `w` 以及连接 `w` 到 `S` 中所有顶点得到的新图，则 `H` 是 `k` 连通的。

    证明:

    首先, 分离 `G` 中两个不相邻顶点至少要 `k` 个点。

    其次，分离 `w` 与 `G` 中不在 `S` 中顶点需要 `k` 个顶点。

    因此 `H` 是 `k` 连通的。

设 `G` 是 `k` 连通图，`u`,`v_1`,`v_2`,`...`,`v_k` 为 `G` 中 `k+1` 个不同顶点，则 `G` 中有 `k` 条内部不交路 `(u,v_i)` `(1\lei\lek)`。(p.s. menger_3 说的是 `k` 连通图中的任意两个点之间存在至少 `k` 条内部不交路，而且是个充要条件; 本定理说的是，对于 `k` 连通图来说，从某点 `u` 出发到其它 `k` 个点 `v_i` 的路都是内部不交的，而且只是一个必要条件)

    证明:

    在 `G` 外添加一点 `w`，让 `w` 与 `v_i` 邻接 `(1 \le i \le k)` 得 `H`，如下图所示:

    由 menger_4 可得，`H` 是 `k` 连通。于是由 menger_3，`u` 与 `w` 间存在 `k` 条内部不交的 `u`,`w` 路，所以 `G` 中有 `k` 条内部不交路 `(u,v_i)` `(1 \le i \le v_i)`。

边连通性的 Menger 定理

    对于边连通性，也存在着类似的结论：

一个非平凡的图 `G` 是 `k` `(k \ge 2)` 边连通的，当且仅当 `G` 的任意两个顶点间至少存在 `k` 条边不重的 `(u,v)` 路。

    基于上述定理，我们可以有如下推论：

对于一个阶至少为 `3` 的无环图 `G`，下面四个命题等价:

1. `G` 连通且无割点;
2. `G` 是 `2` 连通的;
3. `G` 中任意两点位于同一个圈上;
4. `G` 无孤立点，且任意两条边在同一个圈上;

    证明:

     `1 \leftrightarrow 2`: `G` 连通且无割点，则至少需要删去 `2` 个点才可能将 `G` 分离，故 `G` 是 `2` 连通的，反之成立。

     `2 \leftrightarrow 3`: `G` 是 `2` 连通的即 `G` 本身是块，由之前文章证明过的 定理 可得该结论成立。

     `3 \rightarrow 4`: `G` 显然无孤立点，设 `e_1=uv` 与 `e_2=xy` 是 `G` 的任意两条边。由 `2 \leftrightarrow 3` 可得 `G` 是 `2` 连通的。在 `e_1` 和 `e_2` 的端点上分别添加一个邻点 `w` 和 `z` 得到图 `H`，如上图所示。由 menger_4 可知图 `H` 是 `2` 连通的，则再由 `2 \leftrightarrow 3` 可得，`w` 和 `z` 在同一个圈上。由上图容易观察得出，`e_1` 和 `e_2` 也在同一个圈上。

     `4 \rightarrow 3`: 设 `u` 与 `v` 是无环图 `G` 的任意两个顶点，由于 `G` 无孤立点，所以可设 `e_1`, `e_2` 分别与 `u`, `v` 相关联。由条件知，`e_1`, `e_2` 在同一个圈上，所以 `u` 与 `v` 在同一个圈上。