带权连通图上，贪心构造最小权生成树
桥：
对于一个连通图 \(G\) ，若存在一条边 \(\alpha\) ，使得删掉这条边后，得到两个联通分量，则这条边 \(\alpha\) 叫做联通图 \(G\) 的桥。
途径，迹，路径，环：
\(walk \rightarrow trail, path \rightarrow cycle\) 。
walk：设 \(G = (V, E)\) 是一般图。形如 \(\{x_0, x_1\}, \{x_1, x_2\}, \cdots, \{x_{m - 1}, x_{m}\}\) 的 \(m\) 个边的序列称为长度为 \(m\) 的一个途径 （\(walk\)） 。当且仅当 \(x_0 = x_m\) 则称这条途径是闭的，否则是开的。
trail：如果一条 \(walk\) 中的每条边都不同，则这条 \(walk\) 可以称为迹（\(trail\)）。
path：如果一条 \(walk\) 中的每个顶点都不相同（除了可能存在相同的 \(x_0 = x_m\)，并且显然每个顶点不同也会满足每条边不同），则这条 \(walk\) 可以称为路径 （\(path\)）。当且仅当 \(x_0 = x_m\) 则称这条路径是闭的，否则是开的。并且，封闭的路径称为环（\(cycle\)）。
引理 \(1\) ：阶 \(n \geq 3\) 的连通图 \(G\) 中的一条边 \(\alpha = \{x, y\}\) ，它是桥当且仅当它不在 \(G\) 的任何环里。
证明：
如果 \(\alpha\) 是桥，则删除 \(\alpha\) 后会得到两个联通分量 \(G^{'}_1. G^{'}_2\) 。如果 \(G\) 中存在环，要么只在 \(G^{'}_1\) 或 \(G^{'}_2\) 中，要么不妨让起点在 \(G^{'}_1\) 中，会从 \(G^{'}_1\) 到 \(G^{'}_2\) 并再次回到 \(G^{'}_1\) ，这会导致 \(\alpha\) 被经过两次，这与环不经过重复边矛盾。
如果 \(\alpha\) 不是桥，则删除 \(\alpha\) 后依然得到一个联通图 \(G^{'}\) ，找到任意一条 \(x\) 到 \(y\) 的路径，这一定不会包含 \(\alpha\) 。那么这条路径加上 \(\alpha\) 则是 \(G\) 中的一个环。
\(\square\)
引理 \(2\) ：\(n\) 阶连通图的边数 \(\geq n - 1\) 。特别的，\(n - 1\) 可以取等。并且边数为 \(n - 1\) 阶的 \(n\) 阶连通图满足每条边都是一个桥。
证明：
对于一个图 \(G = (V, E = \emptyset)\) ，设 \(|V| = n\) 。显然一开始有 \(n\) 个联通分量，考虑逐渐往 \(E\) 中加入边，每两个分量被合并必然存在一条边 \(\alpha\) 连接这两个分量。当只剩下一个分量，必然有 \(|E| \geq n - 1\) 。
特别的，如果每次都选择两个分量并用一条边连接，则最终 \(|E| = n - 1\) ，显然 \(E\) 中所有边都是桥。
\(\square\)
树：我们把每条边都是桥的连通图称为树。
引理 \(3\) ：\(n \geq 1\) 阶的连通图是树，当且仅当它的边数是 \(n - 1\) 。
证明：
由引理 \(2\) ，已知 \(n \geq 1\) 阶的边数为 \(n - 1\) 的连通图是树。我们只需证明 \(n\) 阶树 \(G\) 恰好有 \(n - 1\) 条边。
我们假设并作数学归纳。
若 \(n = 1\) ，\(G\) 的边数显然为 \(0\) ，结论显然处成立。
若 \(n \geq 2\) ，令 \(\alpha\) 是 \(G\) 中的任意一条边，\(G^{'}\) 是 \(G\) 中只去掉边 \(\alpha\) 后得到的非联通图。因为 \(\alpha\) 是桥，则 \(G^{'}\) 必然恰好有两个联通分量 \(G^{'}_1, G^{'}_2\) 。分别设他们有 \(k\) 和 \(l\) 个顶点 ，显然满足 \(k, l > 0\) 和 \(k + l = n\) 。
首先连通图 \(G^{'}_1\) 中的每一条边都是桥，否则假设一条边不是桥，将其从 \(G^{'}_1\) 中去掉，得到的依然是一个连通图，这意味着 \(G\) 中的一条边不是桥，和 \(G\) 是树矛盾。同理，连通图 \(G^{'}_2\) 中的每一条边都是桥。因此，\(G^{'}_1\) 和 \(G^{'}_2\) 是树。
由归纳假设 \(G^{'}_1\) 有 \(k - 1\) 条边，\(G^{'}_2\) 有 $ l - 1$ 条边。则 \(G\) 有 \((k - 1) + (l - 1) + 1 = k + l - 1 = n - 1\) 条边。
\(\square\)
引理 \(4\) ：设 \(G\) 是连通图，\(\alpha = \{x, y\}\) 是 \(G\) 的一条边，则 \(\alpha\) 是桥当且仅当 \(G\) 的任何环都不包含 \(\alpha\) 。
证明：
假设 \(\alpha\) 是桥，则 \(G\) 由 \(\alpha\) 连接到一起的两个联通分量组成，由引理 \(1\) ，任何环都不包含 \(\alpha\) 。
假设 \(\alpha\) 不是桥，让 \(G\) 去掉 \(\alpha\) 后得到一个联通图是 \(G^{'}\) 。显然 \(G^{'}\) 中 \(x, y\) 是联通的且不经过 \(\alpha\) 。
在 \(G^{'}\) 中任选一条 \(x\) 到 \(y\) 的路径，加上 \(\alpha\) 就是一条可以从起点出发，不经过重复边，并最终返回的路径，这即一个环的定义。那么这是一个包含 \(\alpha\) 的环。
\(\square\)
引理 \(5\) ：设 \(G\) 是 \(n\) 阶连通图，则 \(G\) 是树当且仅当 \(G\) 中不存在环。
证明：
树是每一条边都是桥的联通图。由引理 \(4\) ，树的任何一条边都不在环里，那么树中不存在环。
假设 \(G\) 是一个不存在环的 \(n\) 阶连通图，由引理 \(4\) ，连通图 \(G\) 中的每一条边都是桥，这是树。
\(\square\)
子图，导出子图，生成子图：
对于图 \(G = (V, E)\) ，设 \(U \in V, F \in E\) ，则 \(G^{'} = (U, F)\) 是 \(G\) 的子图。
对于 \(F, U\) ，如果 \(U\) 包含连接 \(F\) 的所有边，则 \(G^{'}\) 能称作 \(G\) 的一般导出子图。
对于 \(U\) ，如果 \(U = V\) ，则 \(G^{'}\) 能称作 \(G\) 的生成子图。
生成树：
对于子图 \(G = (V, E)\) ，存在 \(G^{'}\) 是 \(G\) 的生成子图且是一棵树，则 \(G^{'}\) 能称作 \(G\) 的生成树。
引理 \(6\) ：设 \(T\) 是非树连通图 \(G\) 的一棵生成树，\(\alpha = \{a, b\}\) 是不属于 \(T\) 但属于 \(G\) 的一条边。则 \(T\) 中存在一条边 \(\beta\) 满足：向 \(T\) 中加入边 \(\alpha\) ，并去掉边 \(\beta\) 后，得到的图 \(T^{'}\) 仍是 \(G\) 的生成树。（注：GESP202509L8T2 使用了这个定理）
证明：
设 \(G\) 有 \(n\) 个顶点，则生成树 \(T\) 也有 \(n\) 个顶点。设 \(T^{'}\) 由 \(T\) 中加入边 \(\alpha\) 得到。因为 \(T^{'}\) 不是树，由引理 \(5\) ，\(T^{'}\) 中存在一个环 \(\gamma\) 。任选 \(\beta\) 是 \(\gamma\) 中不同于 \(\alpha\) 的一条边，让 \(T^{''}\) 由 \(T^{'}\) 删除这条边得到。由引理 \(1\) ，\(\gamma\) 中的每条边都不是 \(T^{'}\) 的桥，那么删去 \(\gamma\) 中的任意一条边，\(T^{'}\) 得到的 \(T^{''}\) 依然是一个连通图。显然 \(T^{''}\) 有 \(n\) 个顶点，\(n - 1\) 条边。由引理 \(3\) ，\(T^{''}\) 是树。由于 \(T^{''}\) 是 \(G\) 的生成子图，我们通过 \(G\) 的生成树 \(T\) 得到另一个图 \(T^{''}\) 依然是生成树。
\(\square\)
定理 \(1\) ：
设 \(G = (V, E)\) 是带权联通图，权函数为 \(c\) 。
- 令边集 \(F = \emptyset\) 。
- 若存在不属于 \(F\) 的边 \(\alpha\) 使得 \(F \cup \{\alpha\}\) 不含 \(G\) 中的环，确定一个权最小的 \(\alpha\) 放入 \(F\) 。
令 \(T = (V, F)\) ，则 \(T\) 是 \(G\) 上的一棵最小权生成树。
证明：
从有 \(|V|\) 个联通分量的生成图 \((V, F = \emptyset)\) 开始，选择一条不产生环的边 \(\alpha\) 能连接两个联通分量中的顶点。最终选入 \(|V| - 1\) 条边，剩余一个联通分量，显然 \(T = (V, F)\) 是一棵生成树。
设 \(F\) 中的边是 \(\alpha_1, \alpha_2, \cdots, \alpha_{|V| - 1}\) ，并且且它们会按照这样的顺序选入，令 \(T^{*} = (V, F^{*})\) 是与 \(T\) 有着最多公共边的一棵最小权生成树。如果能证明 \(F^{*} = F\) ，则能证明 \(T\) 是一棵最小生成树。
考虑假设 \(F^{*} \neq F\) ，那么设 \(\alpha_k\) 是 \(F\) 中放入的第一条不是 \(F^{*}\) 中的边。
根据引理 \(6\) ，\(T^{*}\) 中一定存在一条边 \(\beta\) ，满足 \(T^{*}\) 加入 \(\alpha_k\) 并加入 \(\beta\) 后能得到一棵生成树 \(T^{**}\) ，并且 \(\beta\) 可以是 \(T^{*}\) 中加入 \(\alpha_{k}\) 后产生的环内的一条非 \(\alpha_{k}\) 的边。因为 \(T\) 是树，所以这个环存在一条边不属于 \(T\) ，显然也不会是 \(\alpha_{k}\) ，那么我们选择这条边作为 \(\beta\) 。
于是有 \(c(T^{**}) = c(T^{*}) - c(\beta) + c(\alpha_{k})\) ，由 \(T^{*}\) 是一棵最小生成树显然有 \(c(\beta) \leq c(\alpha_{k})\) 。
考虑 \(\alpha_1, \alpha_2, \cdots, \alpha_{k - 1}, \alpha_{k}\) 是按顺序选入不会出现环的且权值最小的边，那么选择完 \(\alpha_{k - 1}\) 后剩余的所有满足选入后不会出现环的边一定满足权值 \(\geq \alpha\) 。显然 \(\alpha_1, \alpha_2, \cdots, \alpha_{k - 1}, \beta\) 中没有环，因为这个边集是树 \(T^{**}\) 的边子集，那么 \(c(\beta) \geq c(\alpha_k)\) 。
于是 \(c(\beta) = c(\alpha_k)\) ，于是 \(T^{**}\) 是一棵最小生成树，且比 \(T^{*}\) 有着比 \(T\) 更多的公共边，这和 \(T^{*}\) 的定义是矛盾的，这说明 \(F^{*} \neq F\) 是不正确的。
\(\square\)