程序代写代做代考 algorithm Weighted Graphs

Weighted Graphs

Dr Timothy Kimber

February 2018

Introduction Weighted Graphs and Trees

More Terminology

Each edge in a weighted graph has an associated cost or weight

We denote the weight of the edge {u, v} by w(u, v)

Algorithms (580) Weighted Graphs February 2018 2 / 55

Introduction Weighted Graphs and Trees

More Terminology

Definition (Tree)

A tree is a pair (G , r) where G is a connected, acyclic graph and r is a
vertex of G , called the root.

A nonrooted tree is a connected, acyclic graph

Algorithms (580) Weighted Graphs February 2018 3 / 55

Introduction Weighted Graphs and Trees

More Terminology

Definition (Spanning Tree)

Given a graph G = (V ,EG ), a tree T = (V ,ET ) such that ET ⊆ EG is a
spanning tree for G .

Given some network (road, phone, water …) a minimum spanning tree
(MST) is an important attribute

Lowest cost way to connect all points

Algorithms (580) Weighted Graphs February 2018 4 / 55

Minimum Spanning Trees

Minimum Spanning Tree

Minimium Spanning Tree Problem

Given graph G = (V ,E ), find a new graph T such that T is an MST of G .

Algorithms (580) Weighted Graphs February 2018 5 / 55

Minimum Spanning Trees Problem Analysis

Analysis

Question

Given graph G = (V ,E ), if you were to generate potential solutions for
the MST problem, and then test them:

What would you generate?

What constraints apply?

Algorithms (580) Weighted Graphs February 2018 6 / 55

Minimum Spanning Trees Problem Analysis

Analysis

An MST for G will comprise

Given this ET will connect all vertices of G

If such a tree also has minimal weight it is an MST

Algorithms (580) Weighted Graphs February 2018 7 / 55

Minimum Spanning Trees Problem Analysis

Analysis

Exercise

Give a case-by-case definition of a function min edges that returns a
minimal weight set of n edges selected from array E.

What are the inputs?

What are the base cases?

How many instances of this problem are there?

Algorithms (580) Weighted Graphs February 2018 8 / 55

Minimum Spanning Trees Problem Analysis

Analysis

A minimal weight set of n edges, chosen from E[1,…,i] is:

(Does the problem have optimal substructure?)

min edges(|E |, |V | − 1) has |E | × (|V | − 1) subproblems
Unfortunately, min edges might not produce MST. Why?

Algorithms (580) Weighted Graphs February 2018 9 / 55

Minimum Spanning Trees Problem Analysis

Analysis

Update to tree edges and only return a set of edges that forms a tree

tree edges(Input: integer i , set ET )

tree edges(i ,ET ) =

ET if |ET | = |V | − 1
min wt[tree edges(i − 1, {E [i ]} ∪ ET ),
tree edges(i − 1,ET )] otherwise

Subproblem now completes the tree (using reduced set of edges)

If {E[i]} ∪ ET not a tree, do not use E[i]
If |ET |+ (i − 1) < |V | − 1, insufficient edges tree edges(|E |,∅) still has |E | × (|V | − 1) subproblems Algorithms (580) Weighted Graphs February 2018 10 / 55 Minimum Spanning Trees Problem Analysis A New Strategy Have seen that the problem involves this choice Add edge i Do not add edge i Have assumed edge i could be any edge, but Maybe this time a greedy approach will actually work! A greedy algorithm picks the ‘obvious’ first step This is called making a greedy choice It leaves just one subproblem to solve So, we identify edge g , the greedy edge, and continue with ET ∪ {E [g ]} Algorithms (580) Weighted Graphs February 2018 11 / 55 Minimum Spanning Trees Greedy Algorithms The Greedy Choice Algorithms (580) Weighted Graphs February 2018 12 / 55 Minimum Spanning Trees Greedy Algorithms The Greedy Choice Algorithms (580) Weighted Graphs February 2018 12 / 55 Minimum Spanning Trees Greedy Algorithms The Greedy Choice Algorithms (580) Weighted Graphs February 2018 12 / 55 Minimum Spanning Trees Greedy Algorithms The Greedy Choice What greedy choices are there when computing an MST? Algorithms (580) Weighted Graphs February 2018 13 / 55 Minimum Spanning Trees Greedy Algorithms The Greedy Choice Greed is only good sometimes We have to show that the choice must lead to a correct solution (As you have seen, much easier to prove if greed is bad) Theorem Let G be a connected, weighted graph. If em is an edge of least weight in G , then em is in some minimum spanning tree for G . The general method of proving that the greedy choice is OK is: 1 Suppose you have an optimal solution to the problem 2 Show that it is still optimal when the greedy choice is included Algorithms (580) Weighted Graphs February 2018 14 / 55 Minimum Spanning Trees Greedy Algorithms Proof T is some MST for G If em is in T , the theorem is true Suppose em is not in T Let em = {u, v}, let the path from u to v in T include the edge {v , x}, and let the weights of {u, v} and {v , x} be wm and w Algorithms (580) Weighted Graphs February 2018 15 / 55 Minimum Spanning Trees Greedy Algorithms Proof Now construct T ′ by removing {v , x} from T and adding {u, v} Since T is a spanning tree, T ′ is a spanning tree Since T is an MST and wm ≤ w , T ′ is an MST em is in T ′ QED Algorithms (580) Weighted Graphs February 2018 16 / 55 Minimum Spanning Trees Greedy Algorithms Proof Can we keep adding the next least weight edge? Algorithms (580) Weighted Graphs February 2018 17 / 55 Minimum Spanning Trees Greedy Algorithms More Greed Our greedy choice can be made more general Theorem Let G = (V ,E ) be a connected, weighted graph. Let ET be a subset of E that is part of an MST for G , and let P be a connected component in the graph (V ,ET ). If EPQ is the set of edges {u, v} where exactly one of {u, v} is in P, and em is an edge of least weight in EPQ then em is in a minimum spanning tree for G . Algorithms (580) Weighted Graphs February 2018 18 / 55 Minimum Spanning Trees Greedy Algorithms Proof The proof is similar Let T be the MST that contains ET If em is in T , the theorem is true Suppose em is not in T Let em = {u, v}, let the first edge on the path from u to v in T that is in EPQ be {x , y}, and let the weights of {u, v} and {x , y} be wm and w Algorithms (580) Weighted Graphs February 2018 19 / 55 Minimum Spanning Trees Greedy Algorithms Proof Now construct T ′ by removing {x , y} from T and adding {u, v} Since T is a spanning tree, T ′ is a spanning tree Since T is an MST and wm ≤ w , T ′ is an MST em is in T ′ QED Algorithms (580) Weighted Graphs February 2018 20 / 55