What is a Minimum-Cost Spanning tree · Example he grap. A Has 16 spanning trees. some are D 4 The graph has two minimum-cost spanning trees, each with a B
What is a Minimum-Cost Spanning Tree • Example: The graph Has 16 spanning trees. Some are: The graph has two minimum-cost spanning trees, each with a cost of 6:
Complete Graph All 16 of its Spanning Trees
Complete Graph All 16 of its Spanning Trees
Minimum Spanning trees The Minimum Spanning Tree for a given graph is the Spanning tree of minimum cost for that graph Complete graph Minimum Spanning Tree
Minimum Spanning Trees The Minimum Spanning Tree for a given graph is the Spanning Tree of minimum cost for that graph. 5 7 2 1 3 4 2 1 3 Complete Graph Minimum Spanning Tree
Application of MsT: an example In the design of electronic circuitry, it is often necessary to make a set of pins electrically equivalent by wiring them together To interconnect n pins, we can use n-1 wires, each connecting two pins We want to minimize the total length of the wires Minimum Spanning trees can be used to model this problem
9 Application of MST: an example • In the design of electronic circuitry, it is often necessary to make a set of pins electrically equivalent by wiring them together. • To interconnect n pins, we can use n-1 wires, each connecting two pins. • We want to minimize the total length of the wires. • Minimum Spanning Trees can be used to model this problem
Electronic circuits www.shutterstock.com2603201
10 Electronic Circuits: