Week 3: Minimum Spanning Trees e Definition of mst Generic Mst algorithm Kruskal's algorithm Prim's algorithm
1 Week 3: Minimum Spanning Trees •Definition of MST •Generic MST algorithm •Kruskal's algorithm •Prim's algorithm
Problem: Laying Telephone Wire Central office
2 Problem: Laying Telephone Wire Central office
Wiring: Naive Approach 可 Central office Expensive
3 Wiring: Naïve Approach Central office Expensive!
Wiring: Better Approach 可 Central office Minimize the total length of wire connecting the customers
4 Wiring: Better Approach Central office Minimize the total length of wire connecting the customers
Definition of mst Input: connected, and undirected Graph G=V,E) Each edge (u, v)in e carries a weight w(u, v) Also referred to as cost (length of edge) to connect u and v Output: a subset Tof e that connects all of the vertices in V and whose total weight is minimized Since the total weight is minimized the subset T must be acyclic(no circuit Thus, T'is a tree. We call it a spanning tree The problem of determining the tree t is called the minimum-spanning-tree problem
5 Definition of MST • Input: connected, and undirected Graph G=(V,E) – Each edge (u,v) in E carries a weight w(u,v) • Also referred to as cost (length of edge) to connect u and v. • Output: A subset T of E that connects all of the vertices in V and whose total weight is minimized. • Since the total weight is minimized, the subset T must be acyclic (no circuit). – Thus, T is a tree. We call it a spanning tree. • The problem of determining the tree T is called the minimum-spanning-tree problem
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:
