Lecture15_Graphs & 16_MST
Saturday, October 17, 2020
Graph
5:00 PM
Many problem in graph theory are solved with dynamic program and greedy.
Graph (review)
Definition. A directed graph (digraph) G = (V, E) is an ordered pair consisting of • a set V of vertices (singular: vertex),
• a set E ⊆ V × V of edges.
In an undirected graph G = (V, E), the edge set E consists of unordered pairs of vertices.
In either case, we have |E| = O(V2). Moreover, if G is connected, then |E| >= |V| – 1, which
implies that lg|E| = Θ(lgV). (Review CLRS, Appendix B.) Cartesian product of two sets that used to creat order pairs. A X A, A X B.
• any subset over Cartesian product gives you something we call relations Cartesian product: A X B
Relation: S ⊆ A X B
• each connection each ordered pair is an edge and then that gives us the graphs Edge set is simply a sub set of the Cartesian product of the vertex sets among itself.
Graph representation:
Adjacency-matrix representation
The adjacency matrix of a graph G = (V, E), where V = {1, 2, …, n}, is the matrix A[1 . . n, 1 . . n] given by
Adjacency-list representation
An adjacency list of a vertex v ∈ V is the list Adj[v] of vertices adjacent to v. • Need to go through the list to check if the member exist in the list.
• if you add up all the degrees for all the vertices then what you should be getting is precisely twice the size of the headset
• Running time: summation of degrees
• Prove: by observation. Be add one edge twice: one time for each direction. ➢Adjacency-list saves space!
Minimum spanning trees
Input: A connected, undirected graph G = (V, E) with weight function w : E→R.
• For simplicity, assume that all edge weights are distinct. (CLRS covers the general case.) Output: A spanning tree T — a tree that connects all vertices — of minimum weight:
• The outputted subgraph mush be a tree
Representation of Graph • Adjacency-matrix • Adjacency-list
MST
• Greedy
• Prim
• Kruskal
Adjacency-matrix representation
Adjacency-list representation
Minimum spanning trees
Party Hand shaking problem
For each handshake, two people will report that hand shake
Analysis of Algorithms Page 1
Greedy for MST
• The outputted subgraph mush be a tree
• Why need n – 1 edges? If more than n – 1, we must have a cycle.
Claim:
•T1 must be a MST in the graph G1 •T2 must be a MST in the graph G2
➢G=G1UG2? FALSE
➢We are creating subproblem: G1 & G2, but notice that there is some potential edges
that connecting G1 and G2
Prove: copy-and-phase
Greedy Algorithm
Greedy-choice property: A locally optimal choice is globally optimal.
• Purple edges: A; red edges: V – A. Or vice versa • Proof by contradiction
1. Suppose the lest weight edge (that goes from purple to red) is not part of the MST
2. Let T be a MST, and u, v has the smallest edge that not part of the MST (dash line). Suggesting these is must be an unique single path that goes from u to v.
3. Contradiction
Note that we have assumption the “all weight of edges are distinct”. To expand the theorem to a graph containing equally weighted edges, we change “this edge must be part of the optimal solution” to “it must be part of an optimal solution”.
Prim’s algorithm
• The extract min gives the least cost edge from red vertices to purple vertices
• If the edge weights are not distinct, it can be still unique, but not necessarily unique.
Analysis of Prim
Prim’s Algorithm
Analysis of Algorithms Page 2
Kruskal Algo
Kruskal’s Algorithms
• Uses the disjoint-set data structure • Running time = O(E lg V).
• Union-Find data structure
Recent Algo
Best to date:
• Karger, Klein, and Tarjan [1993]. • Randomized algorithm.
• O(V + E) expected time.
Analysis of Prim
Analysis of Algorithms Page 3
Analysis of Algorithms Page 4