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