Lesson 2
-
【结论证明】任意一个无向图，都可以通过最少添加 \(\left\lceil \dfrac{p}{2}\right\rceil\) 条边使得图变成边双联通分量。
证明可参考 此博客。其实就是构造一个方案，用叶子两两连边，注意选的根需要度数不为 1。
-
【例题】Edge in MST：无向图，对于每条边，判断“一定在/可能在/不可能在 MST 中”。
考虑分阶段生成 MST。对于边权为 \(w\) 的边，此时已经选完边权 \(<w\) 的边，并且把图缩成了若干个不相干的点。故，如果这条边存在于“点”中，则必定“不可能在 MST 中”；若这条边连接两个不同的点且为桥，则必定“一定在 MST 中”；反之，不为桥且连接不同两点，则“可能在 MST 中”。
-
【例题】Fairy：给定无向图，对于每条边，判断删掉之后图是否为二分图。
【前置定理】 图 G 可二着色（二分图定义），当且仅当 G 无奇圈。
【证明】 找出 G 的 dfs 树，黑白染色，无奇圈当且仅当所有返祖边两端节点异色。【前置定理】 给定两个部分重叠的环 C 和 C'，定义 \(C\oplus C'\) 为保留只在 C/C' 中出现的边，即删去同时存在于两环的边。则 \(C\oplus C'\) 后的图中，任意一个节点的度数都为偶数，即 \(C\oplus C'\) 可分为若干个环。
【证明】 考虑一条被保留的边 \((u,v)\)，若 \(u\notin C\cap C'\) 且 \(v\notin C\cap C'\)，那么其两端度数必为 2。若 \(x \in C\cap C',x\in\{u,v\}\) 且 \(x\) 只能取一个点，即这条边只存在于一个环，考虑 \(x\) 在删边之前的度数，若为 4，则 2 进 2 出，重边不会在 \(x\) 这里出现，删边后 \(x\) 度数依旧为 4；若为 3，则 2 进 1 出，出边必为重边，删边后 \(x\) 度数为 2；若为 2，则 2 进 0 出，即每一条进边同时也是出边，与前提矛盾。证毕。（因为这是我自己胡的，所以有点凌乱。）按照前置定理的做法，找出图的 dfs 树。对于返祖边，它显然是好判断的。我们只需要考虑树边删掉的情况。另外，如果原图已经是二分图，删掉任意一条边，依旧是二分图。
结论：如果树边 e 删掉之后，图是二分图，其充分必要条件为 ① e 在所有奇圈中；② e 不在任何偶圈中。
①证明：
如果这条树边 e 不满足存在于所有奇圈之中，显然删掉 e 之后依然至少有一个奇圈不被影响。
而如果删掉 e 后能改变所有奇圈，那么 e 一定在所有奇圈之中。②证明：
[充分性]即证若 e 在某个偶圈 C 中，则 G-e 一定有奇圈。不妨假设 e 还存在于一个奇圈 C' 中。此时 \(C\oplus C'\) 的边数为奇数，因为 奇 + 偶 - 2 * x = 奇。又由前置定理知，此时在 \(C\oplus C'\) 中，必定有一个长度为奇数的环。证毕。
[必要性]