全网首个严格证明的双连通图的基本性质

· · 个人记录

双连通图的性质和证明

性质

首先讨论边双, 任选两点 u, v, 一条边 e, 一定能找到至少一条简单路径 (不经过同一条边两次), 经过 e 连接 u, v.

然后讨论点双, 任选三点 u, v, w, 一定能找到至少一条简单路径 (不经过同一个点两次), 经过 w 连接 u, v.

边双连通

说明: 在边双图的讨论中, 两条路径不相交指这两条路径不存在公共边.

对于边双的性质, 可以转化为找两条不相交的, 不经过 e 的路径, 使得对于 e 的两个端点 e1, e2, 连接 e1 和 v, e2 和 u, 或者是连接 e1 和 u, e2 和 v.

我们知道定义: 边双图任意两点间至少可以找到两条互不相交的路径.

因为路径在连通图一定能找到, 我们需要保证的是这些路径不交. 首先我们可以避免 e, 因为如果有一条 u 到 e1 的路径经过了 e, 我们可以选择将这条路径去掉 e, 使其变成 u 到 e2 的路径, 如果这时 v 到 e1 的一条路径也经过 e, 我们可以直接选择 v 到 e1 的另一条路径, 根据定义, 可以找到对应路径使得它和上一条路径不相交, 这样就不会有公共边 e 了.

一定存在简单环 u/v - e1 - e2

这是最坏的情况, 因为其它情况会存在两条不经过 e 的路径, 这样可以构造一条 u - e2 的路径, 它和一条不经过 e 的简单路径 u - e1 - e 构成一个简单环.

证明这个结论, 我们讨论随便找一条 u - e2 的路径, 如果包含 e, 则找另一条, 这时得到的路径可能和 u - e1 的路径有交, 将两条路径的公共部分 u - x 记为 UX1, 将剩下的部分记为 XE1 和 XE2, 这三部分无交.

取 u 到 x 的另一条路径记为 UX2, 假设路径上从 u 出发沿 UX2 经过的第一条 XE1/XE2 的公共边的靠近 u 的端点为 a, 则记 UX2 的 u - a 段为 UA, a - e1/e2 段为 AE1/AE2, 这时找到简单环 UX1 - XE1/XE2 - e - AE2/AE1 - UA.

对 v 也有同样的结论.

所以我们现在记两个简单环中, 经过 e 的, 连接 u/v - e1/e2 路径为 UE1/UE2/VE1/VE2, 因为是简单环, 所以 UE1 和 UE2 无交, VE1 和 VE2 无交, 他们都和 e 无交.

存在 UE1 和 VE2 无交或 UE2 和 VE1 无交

则直接找到可行路径 UE1 - e - VE2 或 UE2 - e - VE1.

仅满足 UE1 和 VE1 无交 (省略讨论 UE2 和 VE2 无交仍不失一般性)

设 UE1 和 VE2 的靠近 u 的交边的靠近 u 的交点是 a, 记 UE1 的 a - u 段为 AU, VE2 的 a - e2 段位 AE2.

因为 UE1 和 VE1 无交, 所以 AU 和 VE1 无交.

因为 VE2 和 VE1 无交, 所以 AE2 和 VE1 无交.

因为 AU 和 AE2 由 a 分开, 且 UE1 的 AU 段和 VE2 无交, 所以 AU 和 AE2 无交.

因为 VE2 和 UE1 都不包含 e, 所以 AU 和 AE2 都和 e 无交.

又因为 e 和 VE1 无交, 找到合法路径 AU - AE2 - e - VE1.

UE1 和 VE1, VE2 有交, UE2 也和 VE1 和 VE2 有交

设从 u 出发, UE1 和 VE2 或 VE1 第一次相交的交边的靠近 u 的端点为 b.

如果 UE1 第一次是和 VE2 相交, 则直接将 b 当成 a, 按仅 UE1 和 VE1 无交的情况讨论即可. 接下来只讨论第一次相交是和 VE1 的情况.

设 UE1 的 u - b 段为 BU, VE1 的 b - e1 段为 BE1 则.

因为从 u 出发, VE2 和 UE1 第一次相交在 b 之后, 所以 VE2 和 BU 无交.

因为从 u 出发, VE1 和 UE1 第一次相交在 b, 所以 BE1 和 BU 无交.

因为 VE1 和 VE2 无交, 所以 VE2 和 BE1 无交.

因为 UE1, VE1 都和 e 无交, 所以 BU, BE1 都和 e 无交.

因为 e 和 VE2 无交, 则找到合法路径 BU - BE1 - e - VE2.

点双连通

因为不能找出三个点, 所以我们不讨论两个点的点双图这种特殊情况.

说明: 在点双图的讨论中, 两条路径不相交指这两条路径不存在除端点以外的公共点.

首先找到任意路径连接 u - w 和 v - w, 这时如果两条路径无交, 则性质成立. 如果有交, 一定可以找一个 x 点, 使得两条路径在 w - x 处相交, 我们把这条路径记为 WX1, 且存在一条 u - x - v 的简单路径, 我们把这条简单路径中, u - x 段记为 UX1, v - x 段记为 VX1.

然后讨论 WX1 的情况, 因为我们可以找到至少两条 w - x 的不相交简单路径, 所以最多有一条路径是一条边连接两个点组成的, 如果存在这种路径, 我们把它记为 WX1, 因为不存在除 w, x 外的任何点, 所以它一定和 VX1 和 UX1 无交, 不影响我们在前面对 WX1 记号的定义. 另一条路径记为 WX2, 则 WX2 一定包含至少一个除了 w 和 x 的点.

WX2 和 UX1 有交

则设距离 u 最近的交点为 a, 则 UX1 的 u - a 段记为 UA, 取 WX2 的 w - a 段记作 WA.

WA 和 VX1 有交

设距离 v 最近的交点为 b, 记 v - b 段为 VB, w - b 段为 WB. 如果 VB 和 WB 有交, 则直接取交点为 b, 所以一定有 VB 和 WB 无交. 如果 UX1 和 WB 有交, 则直接取交点为 a, 转化为 WA 和 VX1 无交的情况. 因为 WX2 和 WX1 无交, 则 WX1 和 WB 无交. 因为 UX1 和 VX1 无交, 所以 VB 和 UX1 无交. 因为 WX1 和 VX1 无交, 所以 VB 和 WX1 无交. 又因为 WX1 和 UX1 无交, 所以找到一条合法路径 VB - WB - WX1 - UX1.

WA 和 VX1 无交

如果 UA 和 WA 有交, 直接取交点作为 a, 则存在 UA 和 WA 无交. 因为 WX2 和 WX1 无交, 则 WX1 和 WA 无交. 因为 UX1 和 WX1 无交, 所以 UA 和 WX1 无交. 因为 UX1 和 VX1 无交, 所以 UA 和 VX1 无交. 又因为 WA 和 VX1 无交, WX1 和 VX1 无交, 所以找到一条合法路径, UA - WA - WX1 - VX1.

WX2 和 UX1 无交

假设找一条 v 到 WX2 上除 x 点之外的点 a 的简单路径 VA, 使得这条路径和已有的 VX1 - a 无交, 因为两点间有至少两条无交简单路径, 所以一定能找到一个 VA 满足要求.

VA 和 UX1 有交

设最靠近 u 的交点为 d, 记 UX1 的 u - d 段为 UD, VA 的 d - a 段为 DA. 如果 DA 和 WX1 有交, 取交点为 c, 则转化为 VA 和 UX1 无交, 却和 WX1 有交的情况. 因此这里只讨论 DA 和 WX1 无交的情况. 如果 DA 和 WA 有交, 则直接取交点为 a, 所以一定存在 DA 和 WA 无交. 如果 DA 和 UD 有交, 则直接取交点为 d, 所以一定存在 DA 和 UD 无交. 如果 WX2 和 VX1 有交, 则转化为 WX2 和 UX1 有交的对称问题, 交换对象 U, V, 按 WX2 和 UX1 讨论即可. 故本情况只讨论 WX2 和 VX1 无交的情况. 因为 WX2 和 WX1 无交, 所以 WX1 和 WA 无交. 因为 WX2 和 VX1 无交, 所以 WA 和 VX1 无交. 因为 WX2 和 UX1 无交, 所以 WA 和 UD 无交. 因为 WX1 和 UX1 无交, 所以 WX1 和 UD 无交. 因为 VX1 和 UX1 无交, 所以 VX1 和 UD 无交. 因为 VA 和 VX1 无交, 所以 DA 和 VX1 无交. 又因为, WX2 和 UX1 无交, 所以找到合法路径 UD - DA - WA - WX1 - VX1.

VA 和 UX1 无交

VA 和 WX1 有交

设离 x 最近的交点为 c, 记 VA 的 v - c 段为 VC, WX1 的 w - c 段记 WC.

VA 和 WX1 无交

如果 VA 和 WA 有交, 则直接取交点为 a, 所以一定存在 VA 和 WA 无交.

因为 WX1 和 WX2 无交, 所以 WA 和 WX1 无交. 因为 WX2 和 UX1 无交, 所以 WA 和 UX1 无交. 又因为 VA 和 WX1 无交, VA 和 UX1 无交, WX1 和 UX1 无交, 所以找到合法路径: VA - WA - WX1 - UX1.