最小生成树

基本树变换
定义：设\(T_1,T_2\)是连通图G的一颗生成树，若\(T_1,T_2\)恰有k条边不同，则称\(T_1,T_2\)的距离为\(d(T_1,T_2)=k.\)

定义：设\(d(T_1,T_2)=1.\) 若\(T_1-T_2=e_1,T_2-T_1=e_2\)， 则\(T_2=T_1\oplus\{e_1,e_2\}\)称为\(T_1\)到\(T_2\)的基本树变换。
在基本树变换下，必有\(e_1\in C_{e_2}\)，否则\(C_{e_2}\subseteq T_2\)，矛盾。

定理1. 设\(T\)是连通图G的一颗生成树。则G的任意其它生成树都可由T经过有限次基本树变换得到。

最小生成树算法
Kruskal算法：
初始化\(T=\emptyset\)。
每次操作
选择\(E\)中不属于\(T\)的最小边e，如果e与T不形成回路则加入T中；
从E中删去e。
当\(|T|=n-1\)时终止。

证明：假设Kruskal算法得到的\(T^*\)不是最小树，其边的添加顺序为\(e_1,e_2,\cdots,e_{n-1}\)。对任何一个最小生成树\(T\)，令\(i(T)\)是首个不在T中的\(e_i\)的下标。
取\(T_0=\arg\max i(T)\)，此处的想法是找一个与\(e_1,e_2,\cdots,e_{n-1}\)的前缀重合最多的最小生成树，再利用\(T^*\)的定义找到一个前缀相同更多的最小生成树，从而得到矛盾。
设\(t=t(T_0)\)，则\(e_1,\cdots,e_{t-1}\in T_0, e_t\not\in T_0\)。根据\(T_0\)的选法，任何一颗最小生成树都不能同时包含\(e_1,\cdots,e_{t}\)。
但是，因为\(e_t\)是\(T_0\)的弦，取\(e\in C_{e_t}-T^*\)，做基本树变换\(T'=T\oplus \{e,e_t\}\)。则\(w(T')=w(T_0)-w(e)+w(e_t)\)。因为\(\{e_1,\cdots, e_{t-1}, e\}\)不包含回路，所以根据\(T^*\)的构造过程，有\(w(e)\ge w(e_t)\)。因此\(w(T')\le w(T_0)\)，即\(T'\)也是最小生成树，且包含\(e_1,\cdots,e_{t}\)，矛盾。

Prim算法：
任选结点\(v_0\)，初始化\(T=\emptyset, U=\{v_0\}\)。
每次操作
选择\(u\)为不在U中，且与U中任意点距离最短的点；
将u加入U中，并将u与原U内的最短边加入T中；
更新U中点与其它点的最短距离。
当\(|T|=n-1\)时终止。

    所属分类：离散数学     发表于2022-08-23