Welcome to my Presentation
Greedy Algorithm
Kruskal’s Algorithm
Perfect Graph Theorem
Subject Name :Advance Graph Theory
Subject Code:CSE-504
Submitted By Submitted To
MD.FAZLAY MD.ABDUL
RABBY BASET
Roll:21
Batch:28 Associate Prof.
Dept. of CSE
Dhaka International
University
GREEDY ALGORITHM
A greedy Algorithm always makes the choice that looks best at that moment.
It is one of the strategy for solving problem.
This method used for solving optimization problem.
* optimization problem:
Optimization problem which demand either minimum result or maximum result.
Within 30 minute
A B
Bus 32minute
Car 15minute
Train 40minute
Rickshaw 23minute Feasible solution
Walk 1 hour
Optimal solution
Feasible Solution:
A solution which are satisfying the condition given in the problem that called
Feasible solution thaw there are given problem there are many solution.
So we can say that –
Greedy algorithm is the solving optimization problem.
Greedy Algorithm works on following property:
1.Greedy choice property:
It makes the locally optimal choice in the problem
that this choice lead to globally optimal solution.
2.Optimal Substructure:
Optimal solution contain optimal sub solution.
kRuskal’s
algorithm
Edge based
algorithm
Kruskal’s algorithm is a famous greedy algorithm.
It is used for finding the minimum Spanning Tree of the given graph.
*Spanning Tree:
A spanning Tree of a graph is just a sub graph that contain all the
vertices and is a Tree.
*Tree:
Acyclic graph where have no cycle.
To apply Kruskal’s Algorithm the given graph must be -
Weight
Connected
Undirected
Kruskal’s Algorithm Implementation:
Step 1: Sort the all edge from low weight to high weight.
Step 2: # Take the edge with the lower weight and use it to connect the
Vertices of graph.
#If adding an edge create a cycle then reject that edge and
go for the next least weight edge.
Step 3: Keep adding edges until all the vertices are connected and a
Minimum spanning tree is obtained.
Problem:
Construct the minimum spanning tree for the given graph using Kruskal’s Algorithm-:
28
D E
10 16
14
A B C
24 18
25 12
F G
22
28
D E
10 16
14
A B C
24 18
25 12
F G
22
STEP
:1
D E
A B C
F G
28
D E
10 16
14
A B C
24 18
25 12
F G
22
STEP
:2
D E
10
A B C
F G
28
D E
10 16
14
A B C
24 18
25 12
F G
22
STEP
:3
D E
10
A B C
12
F G
28
D E
10 16
14
A B C
24 18
25 12
F G
22
STEP
:4
D E
10
14
A B C
12
F G
28
D E
10 16
14
A B C
24 18
25 12
F G
22
STEP
:5
D E
10 16
14
A B C
12
F G
28
D E
10 16
14
A B C
24 18
25 12
F G
22
Avoiding Cycle Matters..
D E
10 16
14
A B C
18
12
F G
28
D E
10 16
14
A B C
24 18
25 12
F G
22
STEP
:6
D E
10 16
14
A B C
12
F G
22
D E
10 16
14
A B C
24 18
25 12
F G
22
Avoiding Cycle Matters..
D E
10 16
14
A B C
24
12
F G
22
28
D E
10 16
14
A B C
24 18
25 12
F G
22
STEP
:7
D E
10 16
14
A B C
25 12
F G
22
D E
10 16
14
A B C
25 12
F G
22
Since all the vertices have been connected
/ included in the MST, so we stop.
Weight of the MST
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units
Perfect Graph theorem
Perfect Graph:
A perfect graph is an undirected graph with the property that in every one of it’s
Induced subgraphs,the size of largest clique equals the minimum number of colors
In a coloring of the sub graph.
A graph G is perfect, if for every sub graph H of G . W(H)=X(H
W(H) means ‘clique number’
X(H) means ‘chromatic number’
Here,
W(H)=3
X((H)=3
W(H)=X(H)
*clique number:
The clique number of a graph Denoted W(G),is the number of vertices in
a maximum clique of G.
Equivalently, It is the size of largest clique or maximal of G.
Number of clique =4
Color (red,yellow,blue,black)=4
So ,it is perfect graph..
Thank You!
