Minimal Spanning Trees in Graph Theory
undefined
Lecture 19
Minimal Spanning Trees
CSCI – 1900 Mathematics for Computer Science
Fall 2014
Bill Pine
CSCI 1900
Lecture 19 - 2
Lecture Introduction
•
Reading
–
Rosen Sections 11.4, 11.5
•
Spanning tree
•
Weighted graphs
•
Minimal spanning tree
–
Two algorithms to generate
•
Prim's algorithm
•
Kruskal's algorithm
CSCI 1900
Lecture 19 - 3
Tree
•
Recall the definition of a tree
–
A connected acyclic graph
•
Any tree with
n
vertices has
n - 1
edges
CSCI 1900
Lecture 19 - 4
Spanning Tree
•
T is a
spanning tree
of graph G, if T is a tree
with
–
The same vertices as G, and
–
A subset of the edges of G
CSCI 1900
Lecture 19 - 5
Notation
•
A
weighted graph
is a graph, whose edges have an
associated real-number weight
•
Example:
•
The weight of the edge {A, B} is also called thedistance between A and B
CSCI 1900
Lecture 19 - 6
Notation
•
Two vertices are
neighbors
if they are
connected by an edge
–
Two vertices are
adjacent
if they are neighbors
•
The
nearest neighbor
of a vertex is the
neighbor with the smallest weight
CSCI 1900
Lecture 19 - 7
Notation (cont)
•
Neighbors of A:
–
B, C
•
Neighbors of C:
–
B, A, D
•
Nearest Neighbor of A:
–
C
•
Nearest Neighbor of C:
–
D
CSCI 1900
Lecture 19 - 8
Minimal Spanning Tree
•
A
minimal spanning tree
is a spanning tree
for which the sum of the weights of all the
edges is as small as possible
CSCI 1900
Lecture 19 - 9
Spanning Trees – Example
C
∑ w
i
= 32
∑ w
i
= 47
∑ w
i
= 52
CSCI 1900
Lecture 19 - 10
Prim’s Algorithm
•
Let
R
be a symmetric, connected relation
with
n
vertices
1.
Chose a vertex v
1
of R
Let V = {v1
} and E ={ }2.
Choose a nearest neighbor v
i
of V that is
adjacent to v
j
, v
j
V, and for which the
edge (v
i
, v
j
) does not form a cycle with
existing elements of E
3.
Repeat step 2 until | E | = n-1
CSCI 1900
Lecture 19 - 11
Prim’s Algorithm (cont)
•
Prim’s algorithm is a member of the class of
algorithms call
greedy algorithms
•
Greedy algorithms take decisions based
upon what is optimal locally
•
Greedy algorithms do not always generate
an overall optimal solution
•
However, Prim’s algorithm can be shown to
be optimal
•
Running time =
Θ( n
2
)
CSCI 1900
Lecture 19 - 12
Prim’s Algorithm
1
2
6
3
1
2
3
a
b
c
d
e
f
g
h
Start with vertex
f
CSCI 1900
Lecture 19 - 13
Kruskal’s Algorithm
•
Let R be a symmetric, connected relation with
n vertices, with S = { e1
, e
2
, …, e
k
}: the set of
weighted edges
1.
Choose an edge e
1
in S of the smallest weight
Let E = {e1
} Replace S with S – {e1
}
2.
Chose an edge e
i
in S of the smallest weight
that does not make a cycle with members of E
Replace E with E
U
{ei
} and S with S – {e1
}
3.
Repeat Step 2 until | E | = n-1
CSCI 1900
Lecture 19 - 14
Kruskal’s Algorithm (cont)
•
Kruskal’s algorithm is also a greedy
algorithm
•
Running time =
Θ(n lg( n ))
CSCI 1900
Lecture 19 - 15
Kruskal’s Algorithm
1
2
6
3
1
2
3
a
b
c
d
e
f
g
h
CSCI 1900
Lecture 19 - 16
Key Concepts Summary
•
Spanning tree
•
Weighted graphs
•
Minimal spanning tree
–
Two algorithms to generate
•
Prim's algorithm
•
Kruskal's algorithm
•
Reading for next time
–
Kolman Section 10.3
Dive into the concept of minimal spanning trees in graph theory with a focus on algorithms like Prim's and Kruskal's. Explore the definition of trees, spanning trees, and weighted graphs. Learn about the importance of finding the minimal spanning tree in a graph and how it contributes to optimization problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture 19 Minimal Spanning Trees CSCI 1900 Mathematics for Computer Science Fall 2014 Bill Pine
Lecture Introduction Reading Rosen Sections 11.4, 11.5 Spanning tree Weighted graphs Minimal spanning tree Two algorithms to generate Prim's algorithm Kruskal's algorithm CSCI 1900 Lecture 19 - 2
Tree Recall the definition of a tree A connected acyclic graph Any tree with n vertices has n - 1 edges CSCI 1900 Lecture 19 - 3
Spanning Tree T is a spanning tree of graph G, if T is a tree with The same vertices as G, and A subset of the edges of G CSCI 1900 Lecture 19 - 4
Notation A weighted graph is a graph, whose edges have an associated real-number weight Example: 30 B 10 C A 15 7 D The weight of the edge {A, B} is also called the distance between A and B CSCI 1900 Lecture 19 - 5
Notation Two vertices are neighbors if they are connected by an edge Two vertices are adjacent if they are neighbors The nearest neighbor of a vertex is the neighbor with the smallest weight CSCI 1900 Lecture 19 - 6
Notation (cont) Neighbors of A: B, C Neighbors of C: B, A, D B 30 10 C A 15 7 D Nearest Neighbor of A: C Nearest Neighbor of C: D CSCI 1900 Lecture 19 - 7
Minimal Spanning Tree A minimal spanning tree is a spanning tree for which the sum of the weights of all the edges is as small as possible CSCI 1900 Lecture 19 - 8
Spanning Trees Example B B 30 10 10 C C A A 15 15 7 7 wi = 32 D D B B 30 30 10 C C A C A 15 7 7 wi = 52 wi = 47 D D CSCI 1900 Lecture 19 - 9
Prims Algorithm Let R be a symmetric, connected relation with n vertices 1. Chose a vertex v1 of R Let V = {v1} and E ={ } 2. Choose a nearest neighbor vi of V that is adjacent to vj, vj V, and for which the edge (vi, vj) does not form a cycle with existing elements of E 3. Repeat step 2 until | E | = n-1 CSCI 1900 Lecture 19 - 10
Prims Algorithm (cont) Prim s algorithm is a member of the class of algorithms call greedy algorithms Greedy algorithms take decisions based upon what is optimal locally Greedy algorithms do not always generate an overall optimal solution However, Prim s algorithm can be shown to be optimal Running time = ( n2 ) CSCI 1900 Lecture 19 - 11
Prims Algorithm f f 6 6 5 7 12 h c h c 13 1 1 1 1 8 e e 11 2 2 b b 10 3 3 g g 7 2 2 d d 5 6 3 3 a a Start with vertex f CSCI 1900 Lecture 19 - 12
Kruskals Algorithm Let R be a symmetric, connected relation with n vertices, with S = { e1, e2, , ek}: the set of weighted edges 1. Choose an edge e1 in S of the smallest weight Let E = {e1} Replace S with S {e1} 2. Chose an edge ei in S of the smallest weight that does not make a cycle with members of E Replace E with E U {ei} and S with S {e1} 3. Repeat Step 2 until | E | = n-1 CSCI 1900 Lecture 19 - 13
Kruskals Algorithm (cont) Kruskal s algorithm is also a greedy algorithm Running time = (n lg( n )) CSCI 1900 Lecture 19 - 14
Kruskals Algorithm f f 6 5 6 7 12 h c h c 13 1 1 1 1 8 e e 11 2 2 b b 10 3 g 3 g 7 2 2 d 5 d 6 3 3 a a CSCI 1900 Lecture 19 - 15
Key Concepts Summary Spanning tree Weighted graphs Minimal spanning tree Two algorithms to generate Prim's algorithm Kruskal's algorithm Reading for next time Kolman Section 10.3 CSCI 1900 Lecture 19 - 16
