Electronic Circuits 己fm 图 mmON
11 Electronic Circuits:
Here is an example of a connected graph and its minimum spanning tree 8 4 10 Notice that the tree is not unique replacing(b, c)with (a, h) yields another spanning tree with the same minimum weight 12
12 Here is an example of a connected graph and its minimum spanning tree: a b h c d e g f i 4 8 7 9 10 14 4 2 2 6 1 7 11 8 Notice that the tree is not unique: replacing (b,c) with (a,h) yields another spanning tree with the same minimum weight
Growing a mst(Generic algorithm) GENERIC MST(G, w) A while a does not form a spanning tree do 345 find an edge(u,v) that is safe for a A:=A∪{(uv)} return a Set a is always a subset of some minimum spanning tree This property is called the invariant Property An edge(u, v) is a safe edge for a if adding the edge to A does not destroy the invariant A safe edge is just the correct edge to choose to add to 13
13 Growing a MST(Generic Algorithm) • Set A is always a subset of some minimum spanning tree. This property is called the invariant Property. • An edge (u, v) is a safe edge for A if adding the edge to A does not destroy the invariant. • A safe edge is just the CORRECT edge to choose to add to T. GENERIC_MST(G,w) 1 A:={} 2 while A does not form a spanning tree do 3 find an edge (u,v) that is safe for A 4 A:=A∪{(u,v)} 5 return A
7 S↑a)11 14 ↑S VS↓ 2 ↓V-s This figure shows a cut(S,v-S)of the graph The edge (d, c)is the unique light edg crossing the cut
14 V-S↓ a b h c d e g f i 4 8 7 9 10 14 4 2 2 6 1 7 11 8 S↑ ↑ S ↓ V-S • This figure shows a cut (S,V-S) of the graph. • The edge (d,c) is the unique light edge crossing the cut
S afe edge We need some definitions and a theorem A cut(,v-s)of an undirected graph G=(V, E)is partition of v An edge crosses the cut(S,v-s)if one of its endpoints is in S and th le other is in v-S An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut 15
15 Safe edge We need some definitions and a theorem. • A cut (S,V-S) of an undirected graph G=(V,E) is a partition of V. • An edge crosses the cut (S,V-S) if one of its endpoints is in S and the other is in V-S. • An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut