复旦大学：《离散数学》PPT教学课件（赵一鸣）16/28

5.5.2 Minimum spanning trees .o Definition 24: A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges. ☆ Prim algorithms 冷 Kruskal’ s algorithms

5.5.2 Minimum spanning trees ❖ Definition 24: A minimum spanning tree in a connected weighted graph is a spanning tree that has the smallest possible sum of weights of its edges. ❖ Prim algorithms ❖ Kruskal’s algorithms

☆1.Prim' s algorithms &o Let t=e where e is minimum-weighted edge in G ◆fori=lton-2 &o begin e an edge of minimum weight incident to a vertex in T and not forming a simple circuit in T if added to T 令T:=TU{e end

❖ 1.Prim’s algorithms ❖ Let T={e} where e is minimum-weighted edge in G ❖ for i=1 to n-2 ❖ begin ei= an edge of minimum weight incident to a vertex in T and not forming a simple circuit in T if added to T ❖ T:=T∪{ei } ❖ end

6 5 v?C Theorem 5.17: Prim's algorithm produces a minimum spanning tree of a connected weighted graph

Theorem 5.17: Prim’s algorithm produces a minimum spanning tree of a connected weighted graph

令2 Kruskal’ s algorithn 令T=② 今Fori=1ton-1 ☆ begin o e= an edge of minimum weight in E(G)-E(T) and not forming a simple circuit in T if added to T 令T:=TU{e ☆cnd

❖ 2.Kruskal’s algorithm ❖ T=. ❖ For i=1 to n-1 ❖ begin ❖ ei= an edge of minimum weight in E(G)-E(T) and not forming a simple circuit in T if added to T ❖ T:=T∪{ei } ❖ end

3 6 5 5 2 5 5 yi

Theorem 5.18: Kruskal's algorithm produces a minimum spanning tree of a connected weighted graph. g Proof: Let g be a connected weighted graph, and T be the graph which is produced by Kruskal algorithm ☆ By theorem5.14 &T is a spanning tree of g

❖ Theorem 5.18: Kruskal’s algorithm produces a minimum spanning tree of a connected weighted graph. ❖ Proof: Let G be a connected weighted graph, and T be the graph which is produced by Kruskal’s algorithm. ❖ By theorem 5.14 ❖ T is a spanning tree of G

&o Now we prove T is a minimum spanning tree Suppose t that is not a minimum spanning tree. Thus there is a spanning tree s of G such that W(S<w(T). w(e1)sw(e2)≤sw(ek)≤…sw(en1) Suppose ek that is the first edges, ie el,e2,.sek-I are common edges of T and s There is a simple circuit C that is in E(sUek Then there is an edge e of c that e'Es and eT. 令e1e2y…,ek-1,e'∈S, thus e1,e2…,ek-1ande'≠any circuit By Kruskal's algorithm, w(eksw(e)

❖ Now we prove T is a minimum spanning tree ❖ Suppose T that is not a minimum spanning tree. Thus there is a spanning tree S of G such that w(S)<w(T). ❖ w(e1 ) ≤w(e2 ) ≤≤w(ek ) ≤≤w(en-1 ) ❖ Suppose ek that is the first edgeS, i.e. e1 ,e2 ,,ek-1 are common edges of T and S. ❖ There is a simple circuit C that is in E(S∪{ek }. Then there is an edge e' of C that e'S and e'T. ❖ e1 ,e2 ,,ek-1 , e'S, thus e1 ,e2 ,,ek-1 and e'  any circuit. ❖ By Kruskal’s algorithm, w(ek )≤w(e')

&o We have a spanning tree s' which is obtained from SUek by omitting the edge e 令 Because w(e)≤w(e"),w(S")≤w(S), and the number of common edges of s' and T are added 令W(T≤w(S), 令 Suppose:w(S)<w(T) ☆ contradiction %o Rooted tree and binary tree .o Prefix codes and optimal tree

❖ We have a spanning tree S’ which is obtained from S∪ek by omitting the edge e'. ❖ Because w(ek )≤w(e'), w(S')≤w(S), and the number of common edges of S’ and T are added 1. ❖ W(T)≤W(S), ❖ Suppose: W(S)<W(T) ❖ contradiction ❖ Rooted tree and binary tree ❖ Prefix codes and optimal tree

5.5.3 Rooted tree and binary tree 4 Definition 25: A directed graph is a directed tree if the graph is a tree in the underlying undirected graph. .s Definition 26: A rooted tree is a directed tree if there are exactly a vertex that is 0 in-degree, and other vertices that are I in-degree. The vertex of 0 in-degree is called root. And the vertices of 0 out-degree are called leaves. The vertices that are not 0 out-degree are called internal vertices &o There is a unique path from the root to each vertex of the rooted tree by the definition 25

5.5.3 Rooted tree and binary tree ❖ Definition 25: A directed graph is a directed tree if the graph is a tree in the underlying undirected graph. ❖ Definition 26: A rooted tree is a directed tree if there are exactly a vertex that is 0 in-degree, and other vertices that are 1 in-degree. The vertex of 0 in-degree is called root. And the vertices of 0 out-degree are called leaves. The vertices that are not 0 out-degree are called internal vertices. ❖ There is a unique path from the root to each vertex of the rooted tree by the definition 25

. Definition 27: let u be an internal vertex If there is a directed edge(u, w) from u to w. then w is called child of u. and u is called the parent of w. If the vertices W and w2 are child of u, then w, and w2 are called brothers. If there a directed path from u to z then z is called descendant of u and u is called ancestors of w. The level of a vertex v is the length of the unique path from the root to this vertex. The level of the root is defined to be zero. The height of a rooted tree is the maximum of the levels of all vertices .o Note: The parent of w is unique

❖ Definition 27: Let u be an internal vertex. If there is a directed edge (u,w) from u to w, then w is called child of u, and u is called the parent of w. If the vertices w1 and w2 are child of u, then w1 and w2 are called brothers. If there a directed path from u to z, then z is called descendant of u. and u is called ancestors of w. The level of a vertex v is the length of the unique path from the root to this vertex. The level of the root is defined to be zero. The height of a rooted tree is the maximum of the levels of all vertices. ❖ Note: The parent of w is unique