Transcript Factory Physics?

9.1 Prototype Example
•
•
•
•
Seervada Park
Trams route smallest total distance
Phone lines minimum spanning tree
Tram limitations for environmental
concerns limitations on each road
Maximum Flow problem
• O is origin, T is endpoint
9.1 Prototype Example
9.3 Other Shortest-Path Uses
•
•
•
•
•
•
Minimize Total distance
Minimize Total cost of travel
Minimize Total time of travel
Used in directed networks
To every node methods exist
To and from every node exist, too
9.4 Minimum Spanning Tree
9.4 Minimum Spanning Tree
9.4 Applications
1. Telecommunications networks (fiberoptic, computer, telephone, cable TV)
2. Lightly used transportation networks
3. High voltage power transmission lines
4. Wiring on electrical equipment
5. Design of pipelines to connect locations
9.4 Algorithm Min Span Tree
• It’s a simple greedy algorithm
• Just pick the smallest link and attach to
the tree
9.4 Algorithm Min Span Tree
9.4 Span Tree for Park Ex.
9.4 Span Tree for Park Ex.
9.4 Span Tree for Park Ex.
9.4 Span Tree for Park Ex.
9.4 Span Tree for Park Ex.
9.4 Span Tree for Park Ex.