图论相关

生成树

本文不会使用拟阵相关知识。

引理 1

对于一张图 $G$，以及她的两颗生成树 $T_1,T_2$，对于任意一条边 $e\in(T_1-T_2)$，必定存在一条边 $e'\in(T_2-T1)$，满足 $T_1-\{e\}+\{e'\}$ 和 $T_2-\{e'\}+\{e\}$ 都是 $G$ 的生成树。
证明：
先考虑第二个条件，显然，把 $e=(u,v)$ 加入 $T_2$ 后会与 $T2$ 中 $u$ 到 $v$ 的路径 $p$ 形成一个环，而 $e'$ 一定属于 $p$。
然后考虑第一个条件，将 $e$ 从 $T_1$ 中去掉之后会形成两个连通块，而因为 $p$ 连接了两个连通块，所以 $p$ 至少有一条边会横跨两个连通块，显然这样的边是合法的。

引理 2

对于任意一颗最小生成树 $T$，她的第 $i$ 小的边是所有生成树里最小的。
考虑另一颗生成树 $T'$，我们找到引理 1 中的 $e$ 和 $e'$，由于 $T$ 是最小生成树，所以 $w(e)\le w(e')$，然后将 $T'$ 变为 $T'-\{e'\}+\{e\}$。
然后不断执行这个操作直到最终 $T'$ 变为 $T$，由于操作中只会把大的边变小，所以 $T'$ 里第 $i$ 小的边都大于等 $T$ 中的第 $i$ 小。 由此可知，所有最小生成树的边权的集合都相同。

引理 3

对于所有的最小生成树，边权小于 $w$ 的所有边的连通性是一样的，很明显如果连通性不一样，就可以并起来，那么第 $i$ 小的边就不是所有生成树中最小的，与引理 2 矛盾。

最小生成树

根据引理 3，很明显 Kruskal 的做法就是正确的。

严格次小生成树

结论：严格次小生成树可以通过任意一颗最小生成树删掉一条边，再加入一条边而生成。

证明：
考虑一颗最小生成树 $T$ 以及满足 $|T\cap T'|$ 最大的严格次小生成树 $T'$。
所有的边对 $\{e,e'\}$（含义同引理 1），若 $w(e)=w(e')$，我们可以通过把 $T'$ 中的 $e'$ 替换为 $e$，而找到一颗 $|T\cap T'|$ 更大的严格次小生成树，与条件矛盾。
因此 $w(e)< w(e')$，那么把 $T'$ 中 $e'$ 替换为 $e$ 就可以变为 $T$。

神秘题

题意

对于一个图，对于所有的 $1\le k\le deg_1$，求出 $1$ 的度数为 $k$ 的最小生成树权值。