最小生成树
基本树变换
定义:设\(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