Discrete Mathematical Structures

Course Code: 24BSE2113-C

ics
at
m
Laboratory Manual
he
at
M
te
re
sc
Di

Prince Achankunju

August 31, 2025

Contents

Introducing Python Libraries for Discrete Mathematical Structures . . . . . 2

Constructing a Truth Table of Different Compound Statements in Propositional Logic 8

Verification of Tautology and Contradiction in Propositional Logic . . . . . 12

Plotting the Graph of Elementary Mathematical Functions . . . . . . . . . . 16

ics
Hasse Diagram of Posets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

at
Plotting Different Types of Directed and Undirected Graphs with Proper

Labelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

m
Matrix Representation of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
he
Minimum Spanning Tree Algorithm – Prim’s and Kruskal’s Algorithm . . . 34
at

Shortest path problems - Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . 43

Graph Coloring using Greedy Algorithm . . . . . . . . . . . . . . . . . . . . . . 48

M
te
re
sc
Di

1
 Exercise No: 1

Introducing Python Libraries for Discrete Mathematical

Structures

Python offers several libraries that are effective in solving problems related to discrete mathe-

matical structures. These libraries provide tools for handling combinatorics, graph theory, logic,

sets, and more. Below is an overview of relevant libraries and their usage:

1. NumPy

ics
Purpose: Numerical computations, matrix operations, and combinatorial functions.

at
Why NumPy?

NumPy (Numerical Python) is a powerful library used to perform mathematical and logical
m
operations on large arrays and matrices. It is essential for implementing algorithms related to
he
sets, logic, relations, and other discrete structures.
at

ˆ Calculating permutations and combinations

M

ˆ Logical operations (AND, OR, NOT)

te

ˆ Set operations (union, intersection)

re

ˆ Representing matrices and relations

sc

Example 1: Combinations using math.comb

Di

This example calculates the number of combinations of r elements from a set of n elements

using comb(n, r).

1 import numpy as np
2 from math import comb
3 n, r = 5, 3 # Calculate combinations
4 print ( f " Combinations C ({ n } ,{ r }) : { comb (n , r ) } " )

Output:

Combinations C(5,3): 10

2
 Example 2: Logical Operations Using NumPy Arrays

In discrete mathematics, logic operations like AND, OR are applied to truth values. NumPy

allows us to perform these operations efficiently over arrays.

1 # Define Boolean arrays ( similar to truth values )

2 A = np . array ([ True , False , True ])
3 B = np . array ([ False , True , True ])
4 print ( f " Logical AND : { np . logical_and (A , B ) } " ) # Logical AND between A
and B
5 print ( f " Logical OR : { np . logical_or (A , B ) } " ) # Logical OR between A
and B

ics
Output:

at
Logical AND: [False False True]

Logical OR: [ True True True]

m
Example 3: Set Operations (Union and Intersection)
he
Sets are a fundamental part of discrete structures. NumPy provides operations to handle sets
at

efficiently.
M

1 # Define two sets using arrays

2 set_A = np . array ([1 , 2 , 3])
set_B = np . array ([3 , 4 , 5])
te

4 union = np . union1d ( set_A , set_B ) # Union : Elements present in either A

re

or B
sc

5 intersection = np . intersect1d ( set_A , set_B ) # Intersection : Elements

common to both A and B
Di

6 print ( " Union : " , union )

7 print ( " Intersection : " , intersection )

Output:

Union: [1 2 3 4 5]

Intersection: [3]

2. SymPy

Purpose: Symbolic mathematics, logic manipulation, and discrete algebra.

3
 Applications:

ˆ Logical equivalences

ˆ Truth tables

ˆ Propositional calculus

1 from sympy import symbols , And , Or , Not , simplify

2 p , q = symbols ( ’p q ’) # Propositions
3 expr = And (p , Or ( Not ( p ) , q ) )

s
4 simplified_expr = simplify ( expr )

ic
5 print ( f " Simplified Expression : { simplified_expr } " )

at
1 from sympy . logic . boolalg import truth_table
2 # Truth Table
3

4
tt = truth_table ( expr , [p , q ])
for row in tt :
em
th
5 print ( row )
Ma

1 from sympy import simplify_logic

2 # Logical expression simplification
A , B = symbols ( ’A B ’)
te

4 expr = ( A & ~ B ) | (~ A & B ) # XOR

re

5 simplified_expr = simplify_logic ( expr )

6 print ( " Simplified Expression : " , simplified_expr )
sc

3. NetworkX
Di

Purpose: Graph theory and network analysis.

Applications:

ˆ Representing and analyzing graphs

ˆ Shortest path and connectivity

ˆ Eulerian and Hamiltonian circuits

4
1 import networkx as nx
2 G = nx . Graph () # Create a graph
3 G . add_edges_from ([(1 , 2) , (2 , 3) , (3 , 4) , (4 , 1) ])
4 # Check connectivity
5 print ( f " Is graph connected ? { nx . is_connected ( G ) } " )
6 # Find shortest path
7 path = nx . shortest_path (G , source =1 , target =3)
8 print ( f " Shortest path from 1 to 3: { path } " )

s
ic
4. Matplotlib

Purpose: Visualization of discrete structures.

at
Applications:

ˆ Visualizing graphs
em
th
ˆ Displaying logical relationships
Ma

1 import networkx as nx
2 import matplotlib . pyplot as plt
te

3 # Directed graph
4 G = nx . DiGraph ()
re

5 G . add_edges_from ([(1 , 2) , (2 , 3) , (3 , 1) ])
nx . draw (G , with_labels = True )
sc

7 plt . title ( " Graph Representation " )

Di

8 plt . show ()

1 # Cycle graph
2 G = nx . cycle_graph (5)
3 nx . draw (G , with_labels = True , node_color = ’ skyblue ’ , font_weight = ’ bold
’)
4 plt . title ( " Cycle Graph " )
5 plt . show ()

5
1 # Venn diagram using pie chart
2 labels = [ ’ Set A ’ , ’ Set B ’]
3 sizes = [3 , 2]
4 plt . pie ( sizes , labels = labels , autopct = ’ %1.1 f %% ’)
5 plt . title ( " Venn Representation of Sets " )
6 plt . show ()

5. itertools

s
Purpose: Handling combinatorics and permutations.

ic
Applications:

at
ˆ Generating permutations, combinations, and Cartesian products

ˆ Arrangements and selections

em
th
1 from itertools import permutations , combinations
2
Ma

3 # Permutations
4 perm = list ( permutations ([1 , 2 , 3]) )
5 print ( f " Permutations : { perm } " )
te

7 # Combinations
re

8 comb = list ( combinations ([1 , 2 , 3] , 2) )

9 print ( f " Combinations : { comb } " )
sc
Di

6. SciPy

Purpose: Advanced numerical computations and discrete optimization.

Applications:

ˆ Solving recurrence relations

ˆ Optimization problems in discrete settings

6
1 from scipy . optimize import linprog
2 # Linear programming
3 c = [ -1 , -2] # Objective coefficients
4 A = [[2 , 1] , [1 , 2]] # Constraint coefficients
5 b = [20 , 20]
6 result = linprog (c , A_ub =A , b_ub =b , method = ’ highs ’)
7 print ( f " Optimal solution : { result . x } , Maximum value : { - result . fun } " )

7. PyEDA

ics
Purpose: Boolean algebra and truth tables.

Applications:

at
ˆ Solving Boolean equations

ˆ Generating Karnaugh maps m

he
# Install pyeda if not already installed
at
1

2 ! pip install pyeda

M

3 from pyeda . inter import expr

4 # Boolean expressions
te

5 expr1 = expr ( " a & b | ~ a & c " )

print ( " Expression : " , expr1 )
re

7 print ( " Simplified : " , expr1 . simplify () )

sc
Di

7
 Exercise No: 2

Constructing a Truth Table of Different Compound Statements

in Propositional Logic

Aim:

To develop a Python program that generates and displays truth tables for multiple logical

expressions involving Boolean variables.

ics
Objectives:

at
ˆ Understand the representation of logical expressions as Python functions.

m
ˆ Implement a function to generate all possible combinations of truth values for given vari-
he
ables.

ˆ Evaluate multiple logical expressions for each combination of inputs.

at

ˆ Display the resulting truth table in a readable tabular format.

M

ˆ Render mathematical logical formulas using LaTeX for clarity.

te
re

Algorithm:
sc

1. Import necessary libraries: Use pandas for table creation and IPython.display for
Di

LaTeX rendering in notebooks.

2. Define function: generate truth table(expressions) to handle multiple logical ex-

pressions dynamically.

3. Extract Variables: From the first logical expression’s function, extract the list of vari-

able names using Python’s func. code .co varnames. Assumes all expressions use the

same set of variables.

8
4. Calculate Number of Rows

ˆ Let n be the number of Boolean variables.

ˆ Compute the total number of rows as 2n , which represents all possible combinations

of input values.

5. Generate Truth Value Combinations

ˆ For each variable var at position j (0-indexed):

– Generate a list of Boolean values of length 2n such that the truth value toggles

s
every 2n−j−1 rows.

ic
ˆ For example, the first variable toggles every half of the rows, the second every quarter,

at
and so on.

ˆ Store these lists in a dictionary with variable names as keys.

6. Create Initial Data Table

em
th
ˆ Combine all generated truth value lists into a data structure (e.g., a dictionary).
Ma

ˆ This structure will represent the variable columns of the truth table.

7. Evaluate Logical Expressions: For each logical expression (name, func) in the input:
te

ˆ For each row (combination of variable truth values), call func with the corresponding
re

arguments.

ˆ Store the result in the data structure under the column labeled with name.
sc

8. Return or Display Result

Di

ˆ Convert the final data structure into a formatted table using a Python tool like

pandas.DataFrame.

ˆ Return or display the truth table in readable tabular format.

9
 Pseudocode (Python):

1 import pandas as pd
2 from IPython . display import display , Math
3

4 def g e n e r a t e _ t r u t h _ t a b l e (* expressions ) :
5 variables = list ( expressions [0][1]. __code__ . co_varnames ) # Extract
variable names
6 n = len ( variables ) # Number of variables

s
7 rows = 2 ** n # Number of rows (2^ n )

ic
8

9 # Generate all possible combinations of truth values for variables

at
10 data = { var : [( i // (2 ** ( n - j - 1) ) ) % 2 == 1 for i in range ( rows

m
) ] for j , var in enumerate ( variables ) }
11 he
12 # Apply each logical expression function
13 for name , func in expressions :
at
14 data [ name ] = [ func (**{ var : row [ var ] for var in variables }) for row
in pd . DataFrame ( data ) . to_dict ( ’ records ’) ]
M

15

16 return pd . DataFrame ( data )

17
e

# Define compound logical expressions

et

18

19 truth_table = g e n e r a t e _ t r u t h _ t a b l e (
cr

20 ( " A ∧ ( B ∨ C ) " , lambda A , B , C : A and ( B or C ) ) , # Logical AND and

OR
is

21 ( " ( A → B ) ∧ ( B → C ) " , lambda A , B , C : ( not A or B ) and ( not B or C ) )

D

, # Logical AND of implications

22 ( "¬A ∨ ¬B " , lambda A , B , C : not A or not B ) # Logical OR of
negations
23 )
24

25 # Display the truth table

26 display ( truth_table )

10
Result and Discussion:

The generated truth table accurately evaluates three compound logical expressions involving

variables A, B, and C:

ˆ The expression A ∧ (B ∨ C) returns True only when A is True and at least one of B or C

is True.

ˆ The implication-based expression (A → B) ∧ (B → C) holds True in most cases except

when one implication fails, particularly when A = True, B = False or B = True, C =

False.

ics
ˆ The expression ¬A ∨ ¬B is False only when both A and B are True, as expected from

De Morgan’s law.

at
m
The logic is implemented correctly and matches classical truth table behavior. The program

dynamically handles combinations and expression evaluations.

he
at

Application:
M

In digital circuit design, a three-input logic gate is defined with the function f (A, B, C) =
te

A ∧ (B ∨ C). A fault is suspected when the gate does not output True for some expected input
re

combinations. Using the provided truth table generation algorithm, construct the truth table

for the function. Identify input conditions under which the gate should ideally output True,
sc

and compare it with observed outputs to detect inconsistencies.

Di

11
 Exercise No: 3

Verification of Tautology and Contradiction in Propositional

Logic

Aim

To verify whether a given propositional logic statement is a tautology, contradiction, or satisfi-

able using truth table evaluation in Python.

Objectives

ics
ˆ To analyze the logical validity of a compound proposition.

at
ˆ To evaluate the proposition using a truth table.

m
ˆ To determine whether it is a tautology, contradiction, or satisfiable.
he
Proposition:: ((P ∨ Q) ∧ (¬Q ∨ R)) → ((P ∧ R) ∨ ¬Q)
at
M

Algorithm
te

1. Import required libraries: pandas and IPython.display.

re

2. Declare propositional variables: P , Q, R.

sc

3. Construct the logical expression.

Di

ˆ LHS: (P ∨ Q) ∧ (¬Q ∨ R)

ˆ RHS: (P ∧ R) ∨ ¬Q

ˆ Full: LHS → RHS

4. Generate all 23 = 8 combinations of truth values.

5. Evaluate each row.

6. Check if the full expression is always True (tautology), always False (contradiction), or

mixed (satisfiable).

12
 Python Code

1 import pandas as pd
2 from IPython . display import display
3 def g e n e r a t e _ t r u t h _ t a b l e (* expressions ) :
4 # Extract variable names from the first expression
5 variables = list ( expressions [0][1]. __code__ . co_varnames )
6 n = len ( variables ) # Number of variables
7 rows = 2 ** n # Number of rows (2^ n )
8 # Generate all possible combinations of truth values

s
9 data = { var : [( i // (2 ** ( n - j - 1) ) ) % 2 == 1 for i in range ( rows

ic
) ] for j , var in enumerate ( variables ) }
# Apply logical expressions

at
10

11 for name , func in expressions :

12

em
data [ name ] = [ func (**{ var : row [ var ] for var in variables }) for row
in pd . DataFrame ( data ) . to_dict ( ’ records ’) ]
th
13 return pd . DataFrame ( data )
14 # Define the logical proposition
Ma

15 truth_table = g e n e r a t e _ t r u t h _ t a b l e (
16 ( " ( P ∨ Q ) ∧ (¬Q ∨ R ) " , lambda P , Q , R : ( P or Q ) and ( not Q or R ) ) ,
# Left - hand side of the implication
te

17 ( " ( P ∧ R ) ∨ (¬Q ) " , lambda P , Q , R : ( P and R ) or ( not Q ) ) ,

# Right - hand side of the implication
re

18 ( " (( P ∨ Q ) ∧ (¬Q ∨ R ) ) → (( P ∧ R ) ∨ (¬Q ) ) " , lambda P , Q , R : not (( P

or Q ) and ( not Q or R ) ) or (( P and R ) or ( not Q ) ) ) ) # Full
sc

proposition
# Display the truth table
Di

19

20 display ( truth_table )
21 # Check if the proposition is a tautology
22 pr op os it io n_ co lu mn = truth_table [ " (( P ∨ Q ) ∧ (¬Q ∨ R ) ) → (( P ∧ R ) ∨ (¬
Q))"]
23 if all ( p ro po si ti on _c ol um n ) :
24 print ( " The proposition is a Tautology . " )
25 elif not any ( p ro po si ti on _c ol um n ) :
26 print ( " The proposition is a Contradiction . " )

13
27 else :
28 print ( " The proposition is Satisfiable . " )

Example 2: Additional Verification

Check whether the proposition:

(P ∨ Q) ∧ (¬P ∨ Q) is a tautology.

s
ic
1 import pandas as pd
2 from IPython . display import display

at
3

4 def g e n e r a t e _ t r u t h _ t a b l e (* expressions ) :
5

6
em
# Extract variable names from the first expression
variables = list ( expressions [0][1]. __code__ . co_varnames )
th
7 n = len ( variables ) # Number of variables
8 rows = 2 ** n # Number of rows (2^ n )
Ma

10 # Generate all possible combinations of truth values

11 data = { var : [( i // (2 ** ( n - j - 1) ) ) % 2 == 1 for i in range ( rows
te

) ] for j , var in enumerate ( variables ) }

12
re

13 # Apply logical expressions

sc

14 for name , func in expressions :

15 data [ name ] = [ func (**{ var : row [ var ] for var in variables }) for row
Di

in pd . DataFrame ( data ) . to_dict ( ’ records ’) ]

16

17 return pd . DataFrame ( data )

18

19 # Define the logical proposition

20 truth_table = g e n e r a t e _ t r u t h _ t a b l e (
21 ( " ( P ∨ Q ) ∧ (¬P ∨ Q ) " , lambda P , Q : ( P or Q ) and ( not P or Q ) )
22 )
23 # Display the truth table

14
24 display ( truth_table )
25 # Check if the proposition is a tautology
26 pr op os it io n_ co lu mn = truth_table [ " ( P ∨ Q ) ∧ (¬P ∨ Q ) " ]
27 if all ( p ro po si ti on _c ol um n ) :
28 print ( " The proposition is a Tautology . " )
29 elif not any ( p ro po si ti on _c ol um n ) :
30 print ( " The proposition is a Contradiction . " )
31 else :
32 print ( " The proposition is Satisfiable . " )

ics
Result and Discussion

at
The analysis of the compound proposition ((P ∨ Q) ∧ (¬Q ∨ R)) → ((P ∧ R) ∨ ¬Q) using

m
Python and SymPy reveals that it evaluates to true for all possible combinations of truth

values assigned to the variables P, Q, and R. The generated truth table confirms that the final
he
column contains only True values, indicating the expression is always valid regardless of input.
at

Therefore, the proposition is a tautology, demonstrating its logical consistency and universal
M

truth in propositional.
te

Application Problem:
re

Analyze whether the above proposition is a tautology, contradiction, or satisfiable. Interpret

sc

the result in terms of network reliability—i.e., under what conditions can we ensure that at
Di

least one backup or recovery system (Q or R) will function if either the primary is online or

recovery is triggered in the absence of it? Use Python to construct the truth table and justify

your conclusion.

15
 Exercise No: 4

Plotting the Graph of Elementary Mathematical Functions

Aim

To plot and visualize basic mathematical functions including quadratic, sine, cosine, exponential,

and logarithmic functions using Python libraries.

Objectives

ˆ To understand the behavior of elementary mathematical functions.

ics
ˆ To demonstrate the functions graphically using NumPy and Matplotlib.

at
Algorithm

m
1. Import Libraries: Import numpy as np and matplotlib.pyplot as plt.
he
2. Define Ranges of x-values:
at

ˆ Quadratic and Exponential: x1 = np.linspace(−10, 10, 400)

M

ˆ Sine and Cosine: x2 = np.linspace(0, 2π, 400)

ˆ Logarithmic: x3 = np.linspace(0.1, 10, 400)

te

3. Compute Function Values:

re
sc

ˆ Quadratic: y1 = x1 ∗ ∗2

ˆ Sine: y2 = sin(x2 )
Di

ˆ Cosine: y3 = cos(x2 )

ˆ Exponential: y4 = exp(x1 )

ˆ Logarithmic: y5 = ln(x3 )

4. Create Subplots: Use plt.subplots() to create a grid layout.

5. Plot Each Function: Plot each (x, y) pair in separate subplots.

6. Add Labels and Titles: Set axis labels and function titles.

16
 7. Adjust Layout: Use plt.tight layout() to optimize spacing.

8. Display Plot: Use plt.show() to render the graphs.

Python Code

1 import numpy as np
2 import matplotlib . pyplot as plt
3

4 # Define the range of x values for each function

5 x1 = np . linspace ( -10 , 10 , 400) # Range for quadratic and exponential

s
functions

ic
6 x2 = np . linspace (0 , 2 * np . pi , 400) # Range for sine and cosine functions
7 x3 = np . linspace (0.1 , 10 , 400) # Range for logarithmic function

at
8

9 # Define the mathematical functions

10

11
y1 = x1 **2
y2 = np . sin ( x2 )
em
# Quadratic function f ( x ) = x ^2
# Sine function f ( x ) = sin ( x )
th
12 y3 = np . cos ( x2 ) # Cosine function f ( x ) = cos ( x )
13 y4 = np . exp ( x1 ) # Exponential function f ( x ) = e ^ x
Ma

14 y5 = np . log ( x3 ) # Logarithmic function f ( x ) = ln ( x )

15

16 # Create a figure with subplots

te

17 fig , ax = plt . subplots (3 , 2 , figsize =(12 , 10) )

18
re

19 # Plot each function

20 ax [0 , 0]. plot ( x1 , y1 , label = r ’ $ f ( x ) = x ^2 $ ’ , color = ’b ’)
sc

21 ax [0 , 0]. set_title ( ’ Quadratic Function : $ f ( x ) = x ^2 $ ’)

22 ax [0 , 0]. set_xlabel ( ’x ’)
Di

23 ax [0 , 0]. set_ylabel ( ’f ( x ) ’)
24 ax [0 , 0]. grid ( True )
25 ax [0 , 0]. legend ()
26

27 ax [0 , 1]. plot ( x2 , y2 , label = r ’ $ f ( x ) = \ sin ( x ) $ ’ , color = ’r ’)

28 ax [0 , 1]. set_title ( ’ Sine Function : $ f ( x ) = \ sin ( x ) $ ’)
29 ax [0 , 1]. set_xlabel ( ’x ’)
30 ax [0 , 1]. set_ylabel ( ’f ( x ) ’)
31 ax [0 , 1]. grid ( True )

17
32 ax [0 , 1]. legend ()
33

34 ax [1 , 0]. plot ( x2 , y3 , label = r ’ $ f ( x ) = \ cos ( x ) $ ’ , color = ’g ’)

35 ax [1 , 0]. set_title ( ’ Cosine Function : $ f ( x ) = \ cos ( x ) $ ’)
36 ax [1 , 0]. set_xlabel ( ’x ’)
37 ax [1 , 0]. set_ylabel ( ’f ( x ) ’)
38 ax [1 , 0]. grid ( True )
39 ax [1 , 0]. legend ()
40

41 ax [1 , 1]. plot ( x1 , y4 , label = r ’ $ f ( x ) = e ^ x $ ’ , color = ’m ’)

42 ax [1 , 1]. set_title ( ’ Exponential Function : $ f ( x ) = e ^ x $ ’)
43 ax [1 , 1]. set_xlabel ( ’x ’)

ics
44 ax [1 , 1]. set_ylabel ( ’f ( x ) ’)
45 ax [1 , 1]. grid ( True )

at
46 ax [1 , 1]. legend ()
47

48
m
ax [2 , 0]. plot ( x3 , y5 , label = r ’ $ f ( x ) = \ ln ( x ) $ ’ , color = ’c ’)
he
49 ax [2 , 0]. set_title ( ’ Logarithmic Function : $ f ( x ) = \ ln ( x ) $ ’)
50 ax [2 , 0]. set_xlabel ( ’x ’)
at

51 ax [2 , 0]. set_ylabel ( ’f ( x ) ’)
M

52 ax [2 , 0]. grid ( True )

53 ax [2 , 0]. legend ()
54
te

55 # Hide the last subplot (2 , 1) as it ’s not needed

re

56 ax [2 , 1]. axis ( ’ off ’)

57 # Adjust layout to prevent overlap
sc

58 plt . tight_layout ()
Di

59 # Show the plot

60 plt . show ()

Result and Discussion

ˆ Quadratic Function: A symmetric parabola opening upwards.

ˆ Sine Function: Oscillates between -1 and 1 with a period of 2π.

ˆ Cosine Function: Similar to sine, but phase-shifted by π

2.

18
 ˆ Exponential Function: Shows exponential growth for x > 0 and decay for x < 0.

ˆ Logarithmic Function: Increases slowly for x > 0 and undefined for x ≤ 0.

Application Problem

In a real-time system simulation, the function

4
f (x) = 2x3 − 3x2 + 5 sin(x) +
x+1

models the response time of a processor node under varying system load x, where x ∈ (−0.9, 10]

to avoid division by zero. Plotting this function allows system designers to analyze critical

ics
response delays and optimize performance under different load conditions.

at
m
he
at
M
te
re
sc
Di

19
 Exercise No: 5

Hasse Diagram of Posets

Aim

To visualize partially ordered sets (Posets) using Hasse diagrams for better understanding of

order relations like divisibility and subset relations.

Objectives

ˆ To construct and visualize the Hasse diagram for:

ics
– A set of numbers with the divisibility relation.

– A set of subsets with the subset relation.

at
ˆ To understand hierarchical representation in partially ordered sets.

m
ˆ To implement Hasse diagram construction using Python libraries: networkx and matplotlib.
he
at

Algorithm
M

1. Setup the Environment:

ˆ Install required libraries: networkx, matplotlib

te

ˆ pip install matplotlib networkx

re

2. Define the Poset:

sc

ˆ For Divisibility Poset: Let S = {1, 2, 3, 4, 6, 12}

Di

ˆ Define relation a ≤ b if a | b. Construct edges for each pair where divisibility holds.

ˆ For Subset Poset: Let S = {a, b, c}

ˆ Define relation A ≤ B if A ⊆ B. Construct edges between directly related subsets.

3. Construct the Graph:

ˆ Use nx.DiGraph() to create a directed graph.

ˆ Add edges representing the partial order (covering relations only, i.e., omit transitive

edges for proper Hasse diagram).

20
 ˆ Convert set elements to tuples (for hashability) if needed.

4. Layout the Diagram:

ˆ Use spring layout() or manually define positions.

5. Draw the Diagram:

ˆ Use nx.draw() with appropriate node and edge settings.

ˆ Add title and use plt.show() to display.

s
6. Interpret the Diagram:

ic
ˆ Lower elements at the bottom.

at
ˆ Edges point upward to indicate the order relation.

ˆ No edge is drawn for transitive relations (i.e., transitively implied paths are omitted

Python Code
em
th
Divisibility Poset
Ma

1 import matplotlib . pyplot as plt

2 import networkx as nx
te

4 G = nx . DiGraph ()
re

5 G . add_edges_from ([(1 , 2) , (1 , 3) , (1 , 4) , (1 , 6) , (1 , 12) ,

6 (2 , 4) , (2 , 6) , (2 , 12) , (3 , 6) , (3 , 12) ,
sc

7 (4 , 12) , (6 , 12) ])
8
Di

9 pos = nx . spring_layout ( G )
10 plt . figure ( figsize =(8 , 6) )
11 nx . draw (G , pos , with_labels = True , node_size =3000 , node_color = "
lightblue " , font_size =12 , font_weight = " bold " , arrows = True )
12 plt . title ( " Hasse Diagram of Divisibility Poset " , fontsize =14)
13 plt . show ()

21
 Subset Poset of {a, b, c}

1 import itertools
2 import networkx as nx
3

4 def hasse_edges (S , relation ) :

5 """
6 Compute Hasse edges for a poset .
7 - S : list of elements
8 - relation (a , b ) : returns True if a < b in the poset

s
9 """

ic
10 edges = []
11 for a , b in itertools . permutations (S , 2) :

at
12 if relation (a , b ) : # a < b
# Check if there ’s no c with a < c < b
13

14
em
if not any ( relation (a , c ) and relation (c , b ) for c in S if c not in
th
(a , b ) ) :
15 edges . append (( a , b ) )
Ma

16 return edges
17

18 # Example : divisibility poset

te

19 S = [1 , 2 , 3 , 4 , 6 , 12]
20 relation = lambda a , b : ( b % a == 0 and a != b )
re

21

22 H_edges = hasse_edges (S , relation )

sc

23 print ( " Hasse edges : " , H_edges )

24
Di

25 # Build Hasse diagram

26 H = nx . DiGraph ()
27 H . add_nodes_from ( S )
28 H . add_edges_from ( H_edges )
29

30 # Levels : based on logarithm of value ( approx " height ")

31 levels = { n : int ( nx . s h o r t e s t _ p a t h _ l e n g t h (H , 1 , n ) ) for n in S }
32

22
33 # Position nodes : arrange by level
34 pos = { n : (i , levels [ n ]) for i , n in enumerate ( sorted (S , key = lambda
x : ( levels [ x ] , x ) ) ) }
35

36 # Draw
37 plt . figure ( figsize =(6 , 6) )
38 nx . draw (H , pos , with_labels = True , node_size =1500 , node_color = "
lightgreen " ,
39 font_size =12 , font_weight = " bold " , arrows = False )

s
40 plt . title ( " Hasse Diagram of Divisibility Poset {1 ,2 ,3 ,4 ,6 ,12} " )

ic
41 plt . show ()

at
Tree Structure as Hasse Diagram

2
import networkx as nx
import matplotlib . pyplot as plt
em
th
3

4 def draw_exact_tree ( tree_structure ) :

Ma

5 G = nx . DiGraph ()
6 G . add_edges_from ( tree_structure )
te

8 pos = {
re

9 1: (0 , 3) ,
10 2: ( -1 , 2) ,
sc

11 3: (1 , 2) ,
12 4: ( -1.5 , 1) ,
Di

13 5: ( -0.5 , 1) ,
14 6: (0.5 , 1) ,
15 7: (1.5 , 1)
16 }
17

18 plt . figure ( figsize =(8 , 6) )

19 nx . draw (G , pos , with_labels = True , node_size =3000 , node_color = ’
lightgreen ’ , font_size =12 , font_weight = " bold " , arrows = True )

23
20 plt . title ( " Exact Tree Structure as Hasse Diagram " , fontsize =16)
21 plt . show ()
22

23 tree_structure = [(1 , 2) , (1 , 3) , (2 , 4) , (2 , 5) , (3 , 6) , (3 , 7) ]
24 draw_exact_tree ( tree_structure )

Result and Discussion

The Hasse diagrams effectively demonstrate the hierarchical structure of partial orders:

ˆ Divisibility Poset: The diagram clearly shows how each number in {1, 2, 3, 4, 6, 12} is

ics
related via divisibility. Transitive edges are omitted to highlight the minimal covering

relations.

at
ˆ Subset Poset: The diagram illustrates how subsets of {a, b, c} are ordered by inclusion,

forming a lattice structure. m

he
ˆ Tree Structure: Represents a hierarchical dependency structure, useful for modeling
at

parent-child or prerequisite-task relationships.

M

Application Problem
te

You are given a set of tasks and their dependencies in the form of directed edges, where each
re

edge (A, B) means Task A must be completed before Task B.

sc

ˆ Tasks: {1, 2, 3, 4, 5, 6, 7}
Di

ˆ Dependencies: [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]

Draw the corresponding Hasse diagram to determine a valid task execution order and un-

derstand the critical path of dependencies.

24
 Exercise No: 6

Plotting Different Types of Directed and Undirected Graphs

with Proper Labelling

Aim

To construct and visualize different types of directed and undirected graphs using Python

libraries (NetworkX and Matplotlib), and label their nodes and edges for clear representation.

ics
Objectives

at
ˆ To understand the structure and difference between directed and undirected graphs.

m
ˆ To use NetworkX for creating graphs and Matplotlib for visualization.
he
ˆ To apply proper labeling and styling for clarity in graphical representation.
at

ˆ To compare simple and complex graph structures using different layouts and visual fea-
M

tures.
te

Algorithm for Plotting a Directed Graph

re

1. Import required libraries: networkx and matplotlib.pyplot.

sc

2. Create a directed graph object using DG = nx.DiGraph().

Di

3. Add nodes and directed edges using DG.add edges from() with ordered pairs.

4. Choose layout for positioning: e.g., pos = nx.spring layout(DG).

5. Draw the graph using nx.draw() with parameters:

ˆ with labels=True for node labels.

ˆ arrows=True for directed edges.

ˆ Customize node size, node color, font size, etc.

25
 6. Set the plot title using plt.title().

7. Display the plot using plt.show().

Pseudocode for Directed Graph

1 import networkx as nx
2 import matplotlib . pyplot as plt
3 # Creating a directed graph
DG = nx . DiGraph ()

s
4

ic
5 # Add nodes and edges
6 DG . add_edges_from ([(1 , 2) , (2 , 3) , (3 , 4) , (4 , 5) , (5 , 1) ])

at
7 # Plotting the directed graph with proper labeling
8 plt . figure ( figsize =(8 , 6) )

m
9 nx . draw ( DG , with_labels = True , node_size =3000 , node_color = ’ lightblue ’
he
, font_size =14 , font_weight = ’ bold ’ , arrows = True )
10 # Title for the plot
at
11 plt . title ( ’ Directed Graph Example ’ , fontsize =16)
12 plt . show ()
M

Algorithm for Plotting an Undirected Graph

e
et

1. Import required libraries: networkx and matplotlib.pyplot.

cr

2. Create an undirected graph object using UG = nx.Graph().

3. Add nodes and undirected edges using UG.add edges from().

is

4. Choose a layout for positioning: e.g., nx.spring layout(UG).

D

5. Draw the graph using nx.draw() with:

ˆ with labels=True, node and font styling.

ˆ No need for arrows in undirected graphs.

6. Add title using plt.title().

7. Display with plt.show().

26
 Pseudocode for Undirected Graph

1 # Creating an undirected graph

2 UG = nx . Graph ()
3 # Add nodes and edges
4 UG . add_edges_from ([(1 , 2) , (2 , 3) , (3 , 4) , (4 , 5) , (5 , 1) ])
5 # Plotting the undirected graph with proper labeling
6 plt . figure ( figsize =(8 , 6) )
7 nx . draw ( UG , with_labels = True , node_size =3000 , node_color = ’ lightgreen
’ , font_size =14 , font_weight = ’ bold ’)
8 # Title for the plot

ics
9 plt . title ( ’ Undirected Graph Example ’ , fontsize =16)
10 plt . show ()

at
Result and Discussion m
he
The implemented algorithms successfully demonstrate the creation and visualization of both
at

directed and undirected graphs using NetworkX and Matplotlib.

M

ˆ The directed graph displays connections with arrows, indicating one-way relationships

(e.g., data flow).

te
re

ˆ The undirected graph uses plain edges to represent mutual or bidirectional connections.
sc

ˆ Layout functions like spring layout enhance visual clarity and spacing between nodes.
Di

ˆ Custom node sizes, colors, and font styles improve readability and presentation.

These visualizations are vital in understanding network-based models across various com-

puter science domains, such as social networks, dependency graphs, and process workflows.

Application Problem

Problem: In a software development project, several tasks must be completed in a specific

order. Each task depends on one or more previous tasks.

27
 Model: Represent tasks and dependencies using a directed graph to visualize task flow and

detect circular dependencies.

Dependencies:

ˆ Task A → Task B, Task A → Task C,

ˆ Task B → Task D, Task C → Task D,

ˆ Task D → Task E

By visualizing the directed graph of task dependencies, developers can detect potential

cycles (which would indicate flawed task planning) and identify critical paths necessary for

ics
timely project completion.

at
m
he
at
M
te
re
sc
Di

28
 Exercise No: 7

Matrix Representation of Graphs

Aim

To represent a weighted, directed graph using both an adjacency matrix and an incidence

matrix, and implement this representation using Python.

s
Objectives

ic
ˆ Understand how graphs can be represented using matrices.

at
ˆ Implement the adjacency matrix for a weighted, directed graph.

em
ˆ Construct the incidence matrix using the convention of −w for outgoing and +w for

incoming edges.
th
ˆ Analyse the connectivity and directionality of the graph through matrix representations.
Ma

Algorithm: Matrix Representation of an Undirected Graph

te

1. Input the number of vertices n and edges (u, v, w).

re

2. Initialize:
sc

ˆ n × n adjacency matrix with zeros.

ˆ n × m incidence matrix with zeros, where m is the number of edges.

Di

3. For each edge (u, v, w):

ˆ Set adj[u][v] = w and adj[v][u] = w.

ˆ Set inc[u][i] = w, inc[v][i] = w.

4. Display the matrices.

29
 Pseudocode (Undirected Graph)

1 # Matrix Representation of a Graph

2 import numpy as np
3 # Define a graph with 4 vertices and edges
4 # Graph :
5 # 0 -- 1
6 # | |
7 # 2 -- 3
8 # Edges : (0 -1) , (0 -2) , (1 -3) , (2 -3)
9 # Adjacency Matrix Representation

ics
10 adj_matrix = np . array ([
11 [0 , 1 , 1 , 0] , # Vertex 0 connections

at
12 [1 , 0 , 0 , 1] , # Vertex 1 connections
[1 , 0 , 0 , 1] , # Vertex 2 connections
13

14 [0 , 1 , 1 , 0] # Vertex 3 connections m
he
15 ])
at
16

17 print ( " Adjacency Matrix : " )

M

18 print ( adj_matrix )
19
te

20 # Incidence Matrix Representation

# Edges : (0 -1) , (0 -2) , (1 -3) , (2 -3)
re

21

22 inc_matrix = np . array ([
sc

23 [1 , 1 , 0 , 0] , # Vertex 0
Di

24 [1 , 0 , 1 , 0] , # Vertex 1
25 [0 , 1 , 0 , 1] , # Vertex 2
26 [0 , 0 , 1 , 1] # Vertex 3
27 ])
28 print ( " \ nIncidence Matrix : " )
29 print ( inc_matrix )

30
 Algorithm: Matrix Representation of a Directed Weighted Graph

1. Input the number of vertices n and edges (u, v, w).

2. Initialize:

ˆ n × n adjacency matrix with zeros.

ˆ n × m incidence matrix with zeros.

3. For each edge (u, v, w):

s
ˆ Set adj[u][v] = w.

ic
ˆ Set inc[u][i] = −w, inc[v][i] = w.

at
4. Display the matrices.

Pseudocode (Directed Graph) em

th
1 import numpy as np
Ma

3 # Define the graph with 4 vertices and directed edges

4 # Edges : (0 -> 1 , weight 5) , (1 -> 2 , weight 3) ,
te

5 # (2 -> 3 , weight 4) , (0 -> 2 , weight 6) , (1 -> 3 , weight 2)

6
re

7 # Adjacency Matrix
8 adj_matrix = np . array ([
sc

9 [0 , 5 , 6 , 0] , # Connections from vertex 0

10 [0 , 0 , 3 , 2] , # Connections from vertex 1
Di

11 [0 , 0 , 0 , 4] , # Connections from vertex 2

12 [0 , 0 , 0 , 0] # Connections from vertex 3
13 ])
14

15 print ( " Adjacency Matrix : " )

16 print ( adj_matrix )
17

18 # Incidence Matrix

31
19 # Edges : E1 (0 -> 1 , weight 5) , E2 (1 -> 2 , weight 3) ,
20 # E3 (2 -> 3 , weight 4) , E4 (0 -> 2 , weight 6) , E5 (1 -> 3 ,
weight 2)
21 inc_matrix = np . array ([
22 [ -5 , 0, 0 , -6 , 0] , # Vertex 0 ( outgoing edges : E1 , E4 )
23 [ 5 , -3 , 0, 0 , -2] , # Vertex 1 ( incoming : E1 , outgoing : E2 , E5 )
24 [ 0, 3 , -4 , 6, 0] , # Vertex 2 ( incoming : E2 , outgoing : E3 )
25 [ 0, 0, 4, 0, 2] # Vertex 3 ( incoming : E3 , E5 )
26 ])
27 print ( " \ nIncidence Matrix : " )
28 print ( inc_matrix )

ics
29 # Analyze the graph
30 print ( " \ nAnalysis : " )

at
31 # In - degree and Out - degree
32 in_degrees = np . sum ( inc_matrix > 0 , axis =1)
m
out_degrees = np . sum ( inc_matrix < 0 , axis =1)
he
33

34 print ( " In - degrees of vertices : " , in_degrees )

at

35 print ( " Out - degrees of vertices : " , out_degrees )

36
M

37 # Path from vertex 0 to vertex 3 ( check adjacency matrix )

38 print ( " Is there a path from vertex 0 to vertex 3? " , adj_matrix [0][1]
te

or adj_matrix [0][2] or adj_matrix [1][3])

re

39

# Total weight of edges

sc

40

41 total_weight = np . sum ( np . abs ( inc_matrix ) ) // 2 # Sum of absolute

Di

values divided by 2
42 print ( " Total weight of all edges : " , total_weight )

Result and Discussion

ˆ The adjacency and incidence matrices accurately represent both undirected and directed

graphs.

ˆ In undirected graphs, both matrices are symmetric, reflecting mutual connections.

32
 ˆ In directed graphs, the adjacency matrix is asymmetric and the incidence matrix distin-

guishes direction using signed weights (−w for source, +w for destination).

ˆ These matrix forms are useful for algorithmic graph processing and provide insight into

connectivity, direction, and weight structure.

Application Problem: Router Network

Problem Statement: A company has four routers (0 to 3) connected in a directed network

to route data packets. The bandwidths (in Mbps) are:

ics
ˆ 0 → 1 : 10 Mbps

ˆ 0 → 2 : 20 Mbps

at
ˆ 1 → 3 : 15 Mbps
m
he
ˆ 2 → 3 : 25 Mbps
at
M
te
re
sc
Di

33
 Exercise No: 8

Minimum Spanning Tree Algorithm – Prim’s and Kruskal’s

Algorithm

Aim

Implementation of Minimum Spanning Tree Algorithms: Prim’s and Kruskal’s Algorithms.

Objectives

s
ic
To implement and compare Prim’s and Kruskal’s algorithms for finding the Minimum Spanning

at
Tree (MST) of a weighted connected graph using Python.

Common Functions in heapq em

th
ˆ heapq.heappush(heap, item): Adds an item to the heap while maintaining the heap

property.
Ma

1 import heapq
2 heap = []
te

3 heapq . heappush ( heap , 5)

4 heapq . heappush ( heap , 3)
re

5 heapq . heappush ( heap , 8)

sc

6 print ( heap ) # Output : [3 , 5 , 8]

Di

ˆ heapq.heappop(heap): Removes and returns the smallest element from the heap.

1 smallest = heapq . heappop ( heap )

2 print ( smallest ) # Output : 3
3 print ( heap ) # Output : [5 , 8]

ˆ heapq.heappushpop(heap, item): Adds a new item to the heap and then removes and

returns the smallest item in a single operation.

34
1 heap = [3 , 5 , 8]
2 result = heapq . heappushpop ( heap , 4)
3 print ( result ) # Output : 3
4 print ( heap ) # Output : [4 , 5 , 8]

ˆ heapq.heapreplace(heap, item): Removes and returns the smallest element, then adds

the new item.

1 heap = [3 , 5 , 8]
2 result = heapq . heapreplace ( heap , 4)

ics
3 print ( result ) # Output : 3
4 print ( heap ) # Output : [4 , 5 , 8]

at
m
ˆ heapq.heapify(iterable): Converts a list into a valid heap in-place.
he
1 nums = [5 , 3 , 8 , 1]
at

2 heapq . heapify ( nums )

print ( nums ) # Output : [1 , 3 , 8 , 5]
M

ˆ heapq.nlargest(n, iterable, key=None): Returns the n largest elements.

te
re

ˆ heapq.nsmallest(n, iterable, key=None): Returns the n smallest elements.

sc

1 nums = [5 , 3 , 8 , 1]
Di

2 largest = heapq . nlargest (2 , nums )

3 print ( largest ) # Output : [8 , 5]
4

5 smallest = heapq . nsmallest (2 , nums )

6 print ( smallest ) # Output : [1 , 3]

Applications of heapq

ˆ Priority Queues: Efficiently manage tasks based on priority.

35
 ˆ Dijkstra’s Algorithm: Find the shortest path in a graph.

ˆ Prim’s Algorithm: Find the Minimum Spanning Tree of a graph.

ˆ Top-k Problems: Retrieve the smallest or largest k elements efficiently.

Algorithm

Prim’s Algorithm

1. Start with an arbitrary node and mark it as visited.

2. Initialize a min-heap (priority queue) with all edges from this node.

ics
3. While the MST does not contain all nodes:

at
ˆ Pick the edge with the minimum weight from the heap.

ˆ If the destination node is not visited: m

he
– Add the edge to the MST.
at

– Mark the destination node as visited.

M

– Add all edges from this node to the heap (only those leading to unvisited nodes).

4. Repeat until all nodes are in the MST.

te
re

Kruskal’s Algorithm
sc

1. Sort all edges in ascending order by weight.

Di

2. Initialize a Disjoint Set Union (DSU) for all vertices.

3. Initialize an empty list for the MST.

4. For each edge in the sorted list:

ˆ If the vertices are in different sets (no cycle will be formed):

– Add the edge to the MST.

– Union the two sets.

5. Repeat until the MST has (V - 1) edges.

36
 Pseudocode

1 import heapq
2 import matplotlib . pyplot as plt
3 import networkx as nx
4

5 # - - - - - - - - - - - - - - - - - - - Prim ’s Algorithm - - - - - - - - - - - - - - - - - - -
6 def prim_mst ( graph , start =0) :
7 n = len ( graph ) # Step 1: Count the number of vertices
8 visited = [ False ] * n # Step 2: Track visited nodes

s
9 mst_edges = [] # Step 3: Store MST edges

ic
10 total_weight = 0 # Step 4: Store total weight of MST

at
11

12 # Step 5: Min - heap to select smallest edge at each step ( weight ,

13
to_node , from_node )
min_heap = [(0 , start , -1) ]
em
# Step 6: Start from the source node (
th
start )
14
Ma

15 # Step 7: Process heap until all nodes are visited

16 while min_heap :
17 weight , u , prev = heapq . heappop ( min_heap ) # Step 8: Get edge with
te

min weight
18 if visited [ u ]: # Step 9: Skip if already visited
re

19 continue
20 visited [ u ] = True # Step 10: Mark node as visited
sc

21 total_weight += weight # Step 11: Add edge weight to total

Di

22

23 if prev != -1: # Step 12: If not the starting node , add edge to MST
24 mst_edges . append (( prev , u , weight ) )
25

26 # Step 13: Push all valid ( non - visited ) neighboring edges into heap
27 for v , w in enumerate ( graph [ u ]) :
28 if not visited [ v ] and w > 0:
29 heapq . heappush ( min_heap , (w , v , u ) )
30

37
31 return mst_edges , total_weight
32

33 # - - - - - - - - - - - - - - - - - - - Kruskal ’s Algorithm - - - - - - - - - - - - - - - - - - -
34 class DisjointSet :
35 def __init__ ( self , n ) :
36 self . parent = list ( range ( n ) ) # Step 1: Initialize parent to self
37 self . rank = [0] * n # Step 2: Initialize rank for union by
rank
38

s
39 def find ( self , u ) :

ic
40 if self . parent [ u ] != u : # Step 3: Path compression
41 self . parent [ u ] = self . find ( self . parent [ u ])

at
42 return self . parent [ u ]
43

44

45
def union ( self , u , v ) :
root_u = self . find ( u )
em
th
46 root_v = self . find ( v )
47
Ma

48 if root_u != root_v : # Step 4: Union by rank to keep tree shallow

49 if self . rank [ root_u ] > self . rank [ root_v ]:
self . parent [ root_v ] = root_u
te

50

51 elif self . rank [ root_u ] < self . rank [ root_v ]:

re

52 self . parent [ root_u ] = root_v

53 else :
sc

54 self . parent [ root_v ] = root_u

55 self . rank [ root_u ] += 1
Di

56

57 def kruskal_mst ( edges , n ) :

58 ds = DisjointSet ( n ) # Step 1: Create disjoint set for ’n ’ vertices
59 mst_edges = [] # Step 2: List to store MST edges
60 total_weight = 0 # Step 3: Track total MST weight
61

62 # Step 4: Sort all edges by weight

63 edges . sort ( key = lambda x : x [2])

38
64

65 # Step 5: Iterate through sorted edges

66 for u , v , weight in edges :
67 # Step 6: Add edge if it doesn ’t form a cycle
68 if ds . find ( u ) != ds . find ( v ) :
69 ds . union (u , v )
70 mst_edges . append (( u , v , weight ) )
71 total_weight += weight
72

s
73 return mst_edges , total_weight

ic
74

75 # - - - - - - - - - - - - - - - - - - - Visualization Function - - - - - - - - - - - - - - - - - - -

at
76 def pl ot _g ra ph _an d_ ms t ( graph , mst_edges , title ) :
77 G = nx . Graph ()
78

79 # Step 1: Build graph from adjacency matrix

em
th
80 for i , row in enumerate ( graph ) :
81 for j , weight in enumerate ( row ) :
Ma

82 if weight > 0:
83 G . add_edge (i , j , weight = weight )
te

84

85 pos = nx . spring_layout (G , seed =42) # Step 2: Layout positions

re

86

87 # Step 3: Draw base graph

sc

88 plt . figure ( figsize =(10 , 8) )

89 nx . draw (G , pos , with_labels = True , node_color = ’ lightblue ’ , node_size
Di

=500 , font_size =10)

90 nx . d r a w _ n e t w o r k x _ e d g e _ l a b e l s (G , pos , edge_labels ={( u , v ) : d [ ’ weight ’
] for u , v , d in G . edges ( data = True ) })
91

92 # Step 4: Highlight MST edges in red

93 mst_edges_set = set (( u , v ) for u , v , _ in mst_edges )
94 mst_edges_set |= set (( v , u ) for u , v , _ in mst_edges )

39
 95 nx . d ra w _ ne t w or k x _e d g es (G , pos , edgelist = mst_edges_set , edge_color = ’
red ’ , width =2)
96

97 plt . title ( title )

98 plt . show ()
99

100 # - - - - - - - - - - - - - - - - - - - Example Input and Execution

-------------------
101

s
102 # Step 1: Adjacency matrix for Prim ’s algorithm

ic
103 graph = [
104 [0 , 2 , 0 , 6 , 0] ,

at
105 [2 , 0 , 3 , 8 , 5] ,
106 [0 , 3 , 0 , 0 , 7] ,
107

108
[6 , 8 , 0 , 0 , 9] ,
[0 , 5 , 7 , 9 , 0]
em
th
109 ]
110
Ma

111 # Step 2: Run Prim ’s Algorithm

112 prim_mst_edges , p rim_to tal_we ight = prim_mst ( graph )
print ( " Prim ’s MST Edges : " , prim_mst_edges )
te

113

114 print ( " Total Weight : " , prim_ total_ weight )

re

115 pl ot _g ra ph _a nd _m st ( graph , prim_mst_edges , " Prim ’s Algorithm MST " )

116
sc

117 # Step 3: Edge list for Kruskal ’s algorithm

118 edges = [
Di

119 (0 , 1 , 2) , (1 , 2 , 3) , (0 , 3 , 6) ,
120 (1 , 3 , 8) , (1 , 4 , 5) , (2 , 4 , 7) ,
121 (3 , 4 , 9)
122 ]
123 n = 5
124 # Step 4: Convert edges to adjacency matrix for plotting
125 adj_matrix = [[0] * n for _ in range ( n ) ]
126 for u , v , w in edges :

40
127 adj_matrix [ u ][ v ] = w
128 adj_matrix [ v ][ u ] = w
129 # Step 5: Run Kruskal ’s Algorithm
130 kruskal_mst_edges , k r u s k a l _ t o t a l _ w e i g h t = kruskal_mst ( edges , n )
131 print ( " Kruskal ’s MST Edges : " , krusk al_mst _edges )
132 print ( " Total Weight : " , k r u s k a l _ t o t a l _ w e i g h t )
133 pl ot _g ra ph _a nd _m st ( adj_matrix , kruskal_mst_edges , " Kruskal ’s
Algorithm MST " )

Result and Discussion

ics
Both Prim’s and Kruskal’s algorithms successfully identified the Minimum Spanning Tree (MST)

at
of the given graph, yielding identical total weights of 16, confirming the correctness of the

m
implementations. Prim’s algorithm incrementally built the MST by selecting the smallest edge

connecting the growing tree to a new vertex, while Kruskal’s algorithm sorted all edges by weight
he
and added them one by one without forming cycles. The resulting MST edges highlight the
at

optimal connections minimizing overall edge cost. Visualization clearly distinguished the MST
M

edges in red over the original graph, demonstrating the practical applicability of both algorithms

for network design problems such as efficient road or communication link construction.
te
re

Application Problem
sc

Scenario: A government wants to build roads to connect several cities. The goal is to ensure
Di

that every city is reachable from any other city, but to minimize the total construction cost.

Input:

ˆ A list of cities (nodes).

ˆ Possible roads between cities with their construction costs (weighted edges).

Task: Find the set of roads to build such that:

ˆ All cities are connected (the network is spanning).

ˆ The total cost of building roads is minimized.

41
ˆ No cycles exist (to avoid redundant roads).

ics
at
m
he
at
M
te
re
sc
Di

42
 Exercise No: 9

Shortest path problems - Dijkstra’s Algorithm

Aim:

Write a Python program that uses Dijkstra’s algorithm to compute the shortest path from a

given source node to all other nodes in a weighted, connected, and directed graph.

Objectives:

ˆ Implement Dijkstra’s Algorithm in Python to find the shortest path.

ˆ Visualize the graph and shortest path distances.

ics
Algorithms

at
Inputs:

m
ˆ A graph represented as an adjacency list: each node maps to a list of tuples (neighbor,

weight) representing edges.

he
ˆ A start/source node.
at
M

Steps:

1. Initialization:
te

ˆ Create a distance array, initialized to infinity (∞) for all nodes except the start node,
re

which is set to 0.
sc

ˆ Create a priority queue (min-heap) and insert the start node with distance 0.
Di

ˆ Maintain an array (previous nodes) to track the path.

2. Main loop:

ˆ Extract the node with the smallest current distance from the priority queue.

ˆ For each neighbor of this node, calculate the tentative distance through the current

node.

ˆ If this distance is smaller than the currently recorded distance for the neighbor,

update the distance and record the current node as the neighbor’s predecessor.

43
 ˆ Push the updated distance and neighbor into the priority queue.

3. Repeat until the priority queue is empty (all shortest distances found).

4. Path reconstruction:

ˆ To get the shortest path to any node, trace back from the target node through

previous nodes until the start node is reached.

Pseudocode

1 import heapq

s
2 import networkx as nx

ic
3 import matplotlib . pyplot as plt

at
4

5 # - - - - - - - - - - - - - - - - - - - Dijkstra ’s Algorithm - - - - - - - - - - - - - - - - - - -
6

7
def dijkstra ( graph , start ) :
n = len ( graph )
em
# Step 1: Total number of nodes
th
8 distances = [ float ( ’ inf ’) ] * n # Step 2: Initialize distances to
infinity
Ma

9 distances [ start ] = 0 # Step 3: Distance to source is 0

10 priority_queue = [(0 , start ) ] # Step 4: Min - heap for selecting
shortest tentative distance
te

11 previous_nodes = [ None ] * n # Step 5: Track path back to source

12
re

13 # Step 6: Continue while there are unvisited nodes in the priority

queue
sc

14 while priority_queue :
current_distance , current_node = heapq . heappop ( priority_queue )
Di

15

16

17 # Step 7: Skip processing if we have already found a shorter path

18 if current_distance > distances [ current_node ]:
19 continue
20

21 # Step 8: Check neighbors of the current node

22 for neighbor , weight in graph [ current_node ]:

44
23 distance = current_distance + weight # Tentative distance via
current node
24

25 # Step 9: Update if a shorter path is found

26 if distance < distances [ neighbor ]:
27 distances [ neighbor ] = distance
28 previous_nodes [ neighbor ] = current_node
29 heapq . heappush ( priority_queue , ( distance , neighbor ) ) # Add to heap
30

s
31 return distances , previous_nodes

ic
32

33 # - - - - - - - - - - - - - - - - - - - Visualization - - - - - - - - - - - - - - - - - - -

at
34 def plot_graph ( graph , shortest_distances , start_node ) :
35 G = nx . DiGraph ()
36

37 # Step 1: Add nodes and edges to NetworkX graph

em
th
38 for node , neighbors in graph . items () :
39 for neighbor , weight in neighbors :
Ma

40 G . add_edge ( node , neighbor , weight = weight )

41

pos = nx . spring_layout ( G ) # Step 2: Layout for nodes

te

42

43
re

44 # Step 3: Draw nodes and edges

45 edge_labels = {( u , v ) : d [ ’ weight ’] for u , v , d in G . edges ( data = True )
sc

}
46 nx . draw (G , pos , with_labels = True , node_size =700 , node_color = ’ skyblue
Di

’ , font_size =14 , font_weight = ’ bold ’)

47 nx . d r a w _ n e t w o r k x _ e d g e _ l a b e l s (G , pos , edge_labels = edge_labels )
48

49 # Step 4: Highlight shortest paths in red

50 for i , distance in enumerate ( sh or te st _d is tan ce s ) :
51 if i != start_node and distance < float ( ’ inf ’) :
52 path = reconstruct_path (i , start_node , previous_nodes )
53 highlight_edges = [( path [ j ] , path [ j + 1]) for j in range ( len ( path ) -

45
 1) ]
54 nx . d ra w _ ne t w or k x _e d g es (G , pos , edgelist = highlight_edges , edge_color =
’ red ’ , width =2.5)
55

56 plt . title ( f " Graph with Shortest Paths from Node { start_node } " )
57 plt . show ()
58

59 # - - - - - - - - - - - - - - - - - - - Path Reconstruction - - - - - - - - - - - - - - - - - - -
60 def reconstruct_path ( target_node , start_node , previous_nodes ) :

s
61 path = []

ic
62 current = target_node
63 # Step 1: Backtrack from target to start using previous_nodes

at
64 while current is not None :
65 path . append ( current )
66

67
current = previous_nodes [ current ]
path . reverse ()
em
# Step 2: Reverse to get path from start to target
th
68 return path
69
Ma

70 # - - - - - - - - - - - - - - - - - - - Example Graph - - - - - - - - - - - - - - - - - - -
71 # Step 1: Graph is defined using adjacency list
graph = {
te

72

73 0: [(1 , 4) , (2 , 1) ] ,
re

74 1: [(3 , 1) ] ,
75 2: [(1 , 2) , (3 , 5) ] ,
sc

76 3: []
77 }
Di

78

79 # Step 2: Run Dijkstra from source node 0

80 source_node = 0
81 shortest_distances , previous_nodes = dijkstra ( graph , source_node )
82

83 # Step 3: Display shortest distances

84 print ( " Shortest distances from node " , source_node , " to all other
nodes : " , sh or te st _d is ta nc es )

46
85

86 # Step 4: Visualize the graph and shortest paths

87 plot_graph ( graph , shortest_distances , source_node )

Result and Discussion:

The implemented Dijkstra’s algorithm efficiently computes the shortest paths from the source

node to all other nodes in the weighted directed graph, as demonstrated by the resulting short-

est distance array. The algorithm correctly updates distances using a priority queue, ensuring

optimal path selection with time complexity suitable for sparse graphs. Visualization high-

lights these shortest paths clearly, confirming that the algorithm identifies minimum cumula-

ics
tive weights along the routes. This approach is practical for routing and network optimization

problems where finding efficient paths is crucial.

at
Application Problem:

m
A delivery company operates in a city represented as a network of intersections (nodes) con-

nected by roads (edges), where each road has an associated travel time in minutes. The company
he
wants to find the shortest travel time routes from its central warehouse (node 0) to all other
at

delivery locations.
M

From To Travel Time (minutes)

0 1 4
te

0 2 1
re

1 3 1
sc

2 1 2

2 3 5
Di

47
 Exercise No: 10

Graph Coloring using Greedy Algorithm

Aim:

To assign colors to the nodes of a graph such that no two adjacent nodes share the same color,

using the minimum possible number of colors.

Objectives:

ˆ Assign colors to each vertex of a graph such that no two adjacent vertices share the same

s
color.

ic
ˆ Minimize the total number of colors used (though greedy does not always guarantee the

at
minimum).

ˆ Provide a fast and simple heuristic for graph coloring problems.

em
ˆ Facilitate applications in scheduling, register allocation, frequency assignment, and re-
th
source allocation where conflict-free assignments are needed.
Ma

ˆ Ensure that coloring is done efficiently in polynomial time suitable for large graphs.

Algorithm:
te

Input: A graph G = (V, E) where V is the set of vertices and E is the set of edges.

Output: A color assignment for each vertex such that no two adjacent vertices have the same
re

colour.
sc

1. Initialize an empty dictionary color assignment to store the color assigned to each node.
Di

2. For each node u in the graph G (in any order):

ˆ Find the colours assigned to all adjacent nodes (neighbors) of u.

ˆ Select the smallest non-negative integer color that is not used by any of the neighbors.

ˆ Assign this color to node u in color assignment.

3. Repeat until all nodes have been assigned a color.

4. Return the color assignment dictionary.

48
 Pseudocode

1 import networkx as nx
2 import matplotlib . pyplot as plt
3

4 # - - - - - - - - - - - - - - - - - - - Graph Coloring Function - - - - - - - - - - - - - - - - - - -

5 def g r e e d y _ g r a p h _ c o l o r i n g ( graph ) :
6 # Step 1: Initialize a dictionary to store colors for each node
7 color_assignment = {}
8

s
9 # Step 2: Loop through each node in the graph

ic
10 for node in graph . nodes () :
11 # Step 3: Get the colors of all adjacent ( neighboring ) nodes

at
12 adjacent_colors = { color_assignment . get ( neighbor ) for neighbor in
graph . neighbors ( node ) }
13

14
em
# Step 4: Assign the smallest possible color ( integer ) that isn ’t
th
taken by a neighbor
15 color = 0
Ma

16 while color in adjacent_colors :

17 color += 1
te

18 color_assignment [ node ] = color

19
re

20 return color_assignment
21
sc

22 # - - - - - - - - - - - - - - - - - - - Visualization Function - - - - - - - - - - - - - - - - - - -
23 def pl ot _c ol or ed_ gr ap h ( graph , color_assignment ) :
Di

24 # Step 1: Choose positions for the nodes

25 pos = nx . spring_layout ( graph )
26

27 # Step 2: Retrieve assigned colors from the dictionary

28 colors = [ color_assignment [ node ] for node in graph . nodes () ]
29

30 # Step 3: Draw the graph with node colors based on the color
assignment

49
31 nx . draw (
32 graph , pos , with_labels = True ,
33 node_color = colors , cmap = plt . cm . rainbow ,
34 node_size =700 , font_size =14 , font_weight = ’ bold ’ ,
35 edge_color = ’ black ’
36 )
37

38 plt . title ( " Graph Coloring using Greedy Algorithm " )

39 plt . show ()
40

41 # - - - - - - - - - - - - - - - - - - - Create Sample Graph - - - - - - - - - - - - - - - - - - -

ics
42 # Step 1: Define edges of the graph ( conflicting pairs )
43 edges = [(0 , 1) , (0 , 2) , (1 , 2) , (1 , 3) , (2 , 3) , (3 , 4) ]

at
44

45 # Step 2: Create a NetworkX graph and add edges

G = nx . Graph () m
he
46

47 G . add_edges_from ( edges )
at

48

49 # - - - - - - - - - - - - - - - - - - - Run Greedy Coloring - - - - - - - - - - - - - - - - - - -

M

50 color_assignment = g r e e d y _ g r a p h _ c o l o r i n g ( G )
51
te

52 # Step 3: Print color assignment result

re

53 print ( " Node Color Assignment : " , color_assignment )

sc

54

55 # Step 4: Plot the colored graph

Di

56 pl ot _c ol or ed _g ra ph (G , color_assignment )

Result and Discussion:

The greedy graph coloring algorithm successfully assigned colors to each node of the sample

graph such that no two adjacent nodes share the same color, using only three colors in this case.

The approach efficiently produced a valid coloring by iteratively selecting the smallest available

color for each node based on its neighbors’ colors. Although the greedy method does not always

guarantee the absolute minimum number of colors, it provides a quick and practical solution

suitable for many real-world problems like scheduling and resource allocation. The visualized

50
graph clearly highlights the distinct color assignments, demonstrating the effectiveness of the

algorithm in resolving conflicts with minimal computational complexity.

Application Problem:

A university needs to schedule exams for 5 courses: C0, C1, C2, C3, and C4. Some courses

have students enrolled in both, so their exams cannot be scheduled at the same time to avoid

conflicts. The conflict pairs (edges) between courses are:

ˆ C0 and C1

ˆ C0 and C2

ˆ C1 and C2

ics
ˆ C1 and C3

at
ˆ C2 and C3

ˆ C3 and C4
m
he
The goal is to assign exam time slots to each course such that no two conflicting courses share
at

the same time slot, minimizing the total number of time slots used.
M
te
re
sc
Di

51