双连通图的性质和证明
性质
首先讨论边双, 任选两点 (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).
-
(VC) 和 (WX2) 有交
直接取交点为 (a) 点, 转化为 (VA) 和 (WX1) 无交的情况.
-
(VC) 和 (WX2) 无交
-
(VC) 和 (WC) 有交
记最靠近 (w) 的交点为 (d), 记 (WC) 的 (w - d) 段为 (WD), (VC) 的 (v - d) 段为 (VD), 则 (VD) 和 (WD) 不可能有交, 否则重新将新的交点记作 (d).
因为 (WX1) 和 (WX2) 无交, 所以 (WD) 和 (WX2) 无交.
因为 (VC) 和 (WX2) 无交, 所以 (VD) 和 (WX2) 无交.
因为 (VA) 和 (UX1) 无交, 所以 (VD) 和 (UX1) 无交.
因为 (WX1) 和 (UX1) 无交, 所以 (WD) 和 (UX1) 无交.
又因为 (WX2) 和 (UX1) 无交, 所以找到合法路径: (VD - WD - WX2 - UX1). -
(VC) 和 (WC) 无交
因为 (VA) 和 (UX1) 无交, 所以 (VC) 和 (UX1) 无交.
因为 (WX1) 和 (UX1) 无交, 所以 (WC) 和 (UX1) 无交.
因为 (WX1) 和 (WX2) 无交, 所以 (WC) 和 (WX2) 无交.
又因为 (VC) 和 (WX2) 无交, (WX2) 和 (UX1) 无交, (VC) 和 (WC) 无交, 所以找到合法路径: (VC - WC - WX2 - UX1).
-
(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).