6.4最小树问题

第四节最小树问题最小树及其性质求最小树的Kruskal算法算法步骤算法复杂性求最小树的Dijkstra算法算法步骤算法复杂性最小树及其性质证明定理6.4.1设T是G的一个支撑树，则T是G的最小树当且仅当对任意边e∈T*有W(e)=maxW(e')其中C(e)⊆T+e为一个唯一的回路。证明：必要性设T是G的最小树。首先因为e∈T*，所以有W(e)≤maxW(e')假若W(e)maxW(e')则存在一条边∈C(e)，使得W()W(e)，那么T'=T+e-也是G的支撑树，但是W(T')W(T)，这与T为最小树矛盾。eeee'∈C(e)e'∈C(e)e'∈C(e)支撑树T的权(或长)：W(T)=∑W(e)最小树：G中权最小的支撑树定理6.4.1设T是G的一个支撑树，则T是G的最小树当且仅当对任意边e∈T*有e∈E′W(e)=maxW(e′)e′∈C(e)最小树及其性质续定理6.4.3设T是G的支撑树，则T是G的唯一最小树当且仅当对任意边e∈G\T,e是C(e)中的唯一最大边。定理6.4.4设T是G的支撑树,则T是G的唯一最小树当且仅当对任意边e∈T,e是Ω(e)中的唯一最小边。证明定理6.4.2设T是G的支撑树，则T是G的最小树当且仅当对任意边e∈T有W(e)=minW(e′)其中Ω(e)⊆T*+e为一个唯一割集。e'∈Ω(e)证明:必要性设T为最小树.首先,因为e∈Ω(e),所以有W(e)≥minW(e′)e′∈Ω(e)W(e)＞minW(e′)e′∈Ω(e)假若则存在一边e'∈Ω(e),使得W(e')W(e)于是T'=T+e'-e也是一个支撑树，且W(T')W(T)。这与T为G的最小树矛盾。定理6.4.2设T是G的支撑树，则T是G的最小树当且仅当对任意边e∈T有W(e)=minW(e′)其中Ω(e)⊆T*+e为一个唯一割集。e'∈Ω(e)求最小树的Kruskal算法的步骤第1步开始把边按权的大小由小到大排列，即将图的边排序为a1,a2,…,am，使W(a1)≤W(a2)≤…≤W(am)置S=Φ，i=0，j=1。第2步若|S|=i=n-1，则停止。这时G[S]=T即为所求；否则，转向第3步。第3步若G[S∪{aj}]不构成回路，则置ei+1=aj，S=S∪{ei+1}，i:=i+1，j:=j+1，转向第2步；否则，置j:=j+1，转向第2步。例用Kruskal算法求解下图所示网络的最小树，其中每条边上的数表示该边的权值。1543212224443Kruskal算法的复杂性首先，在第1步中把边按权的大小由小到大排列起来，这约需mlog2m次比较(m为此网络的边数)其次，第2步最多循环n次在第3步中，判定加边后是否构成回路总共约需m次比较，而加边后点的重新标号最多需n(n-1)次比较所以，总的计算量为mlog2m+n+m+n(n-1)~O(n2log2n)Dijkstra算法的步骤第1步置uj=w1j，T=φ，R={1}，S={2,3,…,n}例求下图的最小树1543212224443第2步取uk=min{uj},置T=T∪{eik},R=R∪{k}，S=S\{k}j∈S第3步若S=φ,则停止；否则，置uj=min{uj,wkj},j∈S,返回第2步Dijkstra算法的复杂性执行第2步时，第一次是(n-2)次比较，第二次为(n-3)次比较，第三次为(n-4)次比较，…，因此总的比较为(n-1)(n-2)/2次执行第3步时，第一次是(n-2)次比较，第二次为(n-3)次比较，第三次为(n-4)次比较，…，因此总的比较为(n-1)(n-2)次所以，总的计算量约为O(n2)