最小生成树（PPT课件讲稿）Minimum Spanning Trees

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: