Scribd
Upload
11 views

Presentation1( Graph Theory and Algorithm)

The document presents algorithms for determining the Minimum Spanning Tree (MST) in graph theory, specifically Kruskal’s, Prim’s, and Reverse-Deletion algorithms. It explains the concepts of undirected graphs, spanning trees, and weighted graphs, and provides step-by-step examples for each algorithm. The document serves as an educational resource for understanding how to find MSTs in connected, weighted graphs.

Uploaded by

Dugasa Bekele
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
11 views

Presentation1( Graph Theory and Algorithm)

The document presents algorithms for determining the Minimum Spanning Tree (MST) in graph theory, specifically Kruskal’s, Prim’s, and Reverse-Deletion algorithms. It explains the concepts of undirected graphs, spanning trees, and weighted graphs, and provides step-by-step examples for each algorithm. The document serves as an educational resource for understanding how to find MSTs in connected, weighted graphs.

Uploaded by

Dugasa Bekele
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 20

Wallaga University

College of Natural and Computational Science


Department of Mathematics

Graph Theory and Algorithm


Presentation Topic :
Algorithms to Determining Minimum Spanning Tree
With Examples

By: Dugassa Bekele

January 16, 2025


Preminary Concepts

 Undirected graph: A graph with edges that do not have an associated direction.

Tree: tree is a connected acyclic graph.


Spanning Tree: is a tree that contains every vertices of a connected graph.
 If graph G is connected graph with n vertices and e edges ,then
the spanning tree of graph G must have:
 n-1 edges and the number of edges deleted from the graph to
obtain the spanning tree is equal to e-n+1.
Cont..
 Weighted Graph: A graph with weight(values) associated with each edges.
 Minimum spanning Tree: The minimum spanning tree of weighted, connected,
undirected graph G is a graph T consists of all vertices of graph G together with
enough edges of such that:
I. T is connected
II. T is acyclic
III. T has Minimal weight
Example: Consider the graph given below:
Algorithms to determine Minimum Spanning Trees

• There are basic algorithms for finding minimum-


weighted spanning tree such as:
Kruskal’s Algorithm
Prim’s Algorithm
Reverse-Deletion Algorithm
Kruskal’s Algorithm: Start with no vertices or edges in the spanning
tree, and repeatedly add the smallest weight edge that does not
create a cycle.
In this algorithm ,we provide the spanning tree to consists of edge
only.
Cont…
Algorithm Of Kruskal’s
1: Input : A connected weighted graph G // G = (V, E,w)
2: Output :A minimum spanning tree T // MST T of G
3: T ← Ø
4: Q ←sorted edges in non-decreasing weights of E
5: while Q = Ø do \\continue until all edges are checked
6: pick an edge (u, v) from Q
7: if (u, v) does not make a cycle with vertices in T then
8: add (u, v) to T
9: end if
10: end while
Thus, finding an edge of smallest weighted can be done just by sorting the edges.
Cont…
Example of Kruskal’s Algorithm
Consider the undirected weighted graph given
below:

 None of the edges are highlighted


Cont…
1. AD and CE are the
smallest edges , with
length 5, and AD has
been arbitrary chosen
and it highlighted
2. CE is now the smallest
edge that does not
form a cycle with length
5, and it is highlighted
as second edge
Cont…
3. The next smallest edge is DF
with length 6 and it is highlighted.

4. The next smallest edges are


AB and BE with the same length 7
and AB is chosen arbitrary and it
is highlighted.
Here the edge BD has been
highlighted by red, b/c if it were
chosen it would form a cycle
(ABD)
Cont…
5. The process continues
highlighted the next smallest edge
BE with length 7.Here many more
edges are highlighted in red at this
stage: BC b/c it forms a cycle BCE, DE
it forms a cycle DEBA, and FE b/c it
forms a cycle FEBAD.
6. Finally, the process finishes with
the edge EG of length 9, and it
highlighted.
Thus, the minimum spanning tree is
obtained with edges highlighted in
green and it has weight 39.
Prim’s Algorithm
 Prim’s Algorithm: start with any one vertex in
the spanning tree, and rapidly add the
smallest weight edge, and the vertex it leads
to, for which the vertex is not already in the
spanning tree.
 In this algorithm, we consists of both vertices
and edges.
Cont…
Algorithm Of Prim’s
1: Input : G(V, E, w)
2: Output : MST T (V, ET ) of G
3: VT ← {s} // s is the vertex selected
4: T ← Ø
5: while VT = V do // continue until all vertices are visited
6: select the edge (u, v) with minimal weight such that u ∈ T
and v ∈ G \ T
7: VT ← VT ∪ {v}
8: ET ← ET ∪ {(u, v)}
9: end while
Cont..
Example Of Prim’s Algorithm

This our original weighted graph given.


Cont…
Cont…
Cont…
Reverse-Deletion Algorithm
Reverse-Deletion Algorithm: we can start with all edges of the
graph and delete edges that will never be included in the MST
until we have a connected graph that has the tree property.
 I t is acyclic or has n − 1 edges.

 We delete edges in the order of decreasing weights as long as

removal of a such edge does not disconnect the graph since


any bridge of the graph should be contained in the MST.
Cont…
Reverse-Delete Algorithm

1: Input: An undirected weighted graph G = (V, E, w)

2: Output: An MST T of G

3: Sort edges of G in non-decreasing order into Q


4: Let T = G
5: Repeat
6: Dequeue the first edge (u, v) from Q

7: Remove (u, v) from T

8: If such removal leaves T disconnected then

9: Join (u, v) to T

10: Until Q = Ø
Cont…
Example Of Reverse-Delete
Cont…
.

THANK YOU FOR ATTENTION!

You might also like