CSE212 – Discrete Mathematics
Summer 2025 Assignment
Student Name: Efaz Ahmed
Student ID: 242-15-755
Subject Code: CSE212
Subject Name: Discrete Mathematics
Semester: Summer 2025
Part 1: The Foundation - Representations and Properties
Question 1: The Social Network Analyst
Network Model: Friend Circle from University Study Group
a) Graph Model Definition:
● Vertices: Represent 8 students in a study group
○ A: Alif (Computer Science)
○ B: Badrul (Mathematics)
○ C: Chomok (Physics)
○ D: Dany (Engineering)
○ E: Emam (Statistics)
○ F: Faruk (Chemistry)
○ G: Gian (Biology)
○ H: Hanif (Economics)
● Edges: Represent direct friendships/regular study partnerships between students
Graph Structure:
Edges: {A,B}, {A,C}, {A,E}, {B,D}, {B,F}, {C,D}, {C,G}, {D,E}, {D,F}, {E,H}, {F,G}, {G,H}
b) Three Representations:
i. Adjacency List:
A: [B, C, E]
B: [A, D, F]
C: [A, D, G]
D: [B, C, E, F]
E: [A, D, H]
F: [B, D, G]
G: [C, F, H]
H: [E, G]
ii. Adjacency Matrix:
A B C D E F G H
A 0 1 1 0 1 0 0 0
B 1 0 0 1 0 1 0 0
C 1 0 0 1 0 0 1 0
D 0 1 1 0 1 1 0 0
E 1 0 0 1 0 0 0 1
F 0 1 0 1 0 0 1 0
G 0 0 1 0 0 1 0 1
H 0 0 0 0 1 0 1 0
iii. Incidence Matrix:
Edges: e1(A,B), e2(A,C), e3(A,E), e4(B,D), e5(B,F), e6(C,D), e7(C,G), e8(D,E), e9(D,F),
e10(E,H), e11(F,G), e12(G,H)
e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12
A 1 1 1 0 0 0 0 0 0 0 0 0
B 1 0 0 1 1 0 0 0 0 0 0 0
C 0 1 0 0 0 1 1 0 0 0 0 0
D 0 0 0 1 0 1 0 1 1 0 0 0
E 0 0 1 0 0 0 0 1 0 1 0 0
F 0 0 0 0 1 0 0 0 1 0 1 0
G 0 0 0 0 0 0 1 0 0 0 1 1
H 0 0 0 0 0 0 0 0 0 1 0 1
c) Detailed Analysis Comparison:
Memory Usage:
● Adjacency List: O(V + E) = O(8 + 12) = 20 units. Most memory efficient for sparse
graphs.
● Adjacency Matrix: O(V²) = O(64) = 64 units. Less efficient for sparse graphs, but
constant space.
● Incidence Matrix: O(V × E) = O(8 × 12) = 96 units. Least memory efficient.
Finding All Neighbors Efficiency:
● Adjacency List: O(degree(v)) - Most efficient, directly access neighbor list.
● Adjacency Matrix: O(V) - Must scan entire row, slower for sparse graphs.
● Incidence Matrix: O(E) - Must check all edges, least efficient.
Adding/Removing Operations:
● Adding Edge: List O(1), Matrix O(1), Incidence O(V) (new column)
● Removing Edge: List O(degree(v)), Matrix O(1), Incidence O(V)
● Adding Vertex: List O(1), Matrix O(V²) (resize), Incidence O(E) (new row)
● Removing Vertex: List O(V + E), Matrix O(V²), Incidence O(E)
Conclusion: Adjacency list is optimal for this sparse social network scenario.
a) Two Non-Isomorphic Graphs with Same Properties:
Graph G1:
*Node = 6
*Edge = 9
*Degree = 3(all node)
Adjecency Matrix:
u1 u2 u3 u4 u5 u6
u1 0 1 0 1 0 1
u2 1 0 1 0 1 0
u3 0 1 0 1 0 1
u4 1 0 1 0 1 0
u5 0 1 0 1 0 1
u6 1 0 1 0 1 0
Graph G1:
*Node = 6
*Edge = 9
*Degree = 3(all node)
Adjecency Matrix:
v1 v2 v3 v4 v5 v6
v1 0 1 0 1 1 0
v2 1 0 1 0 1 0
v3 0 1 0 1 0 1
v4 1 0 1 0 0 1
v5 1 1 0 0 0 1
v6 0 0 1 1 1 0
The graphs have the same degree sequence, but their adjacency structure differs.
so they are not isomorphic
Part 2: Navigating the Maze - Paths, Circuits, and Trees
Question 3: Urban Planning Challenge
a) Eco-Friendly District Road Network:
Multigraph Design:
Vertices: R (Residential), B (Business), S (School), P (Park), C (Recycling), G (Grocery)
Edges (Roads):
- R-B: 2 roads (main road + express lane)
- B-S: 1 road
- S-P: 2 roads (pedestrian friendly + vehicle road)
- P-C: 1 road
- C-G: 2 roads (service road + public road)
- G-R: 1 road
- R-S: 1 road (direct school route)
- B-P: 1 road (business to recreation)
Verification:
● Degree of each vertex:
○ R: degree 4 (even)
○ B: degree 4 (even)
○ S: degree 4 (even)
○ P: degree 4 (even)
○ C: degree 4 (even)
○ G: degree 4 (even)
Euler Circuit Exists: All vertices have even degree, so Euler circuit exists. No Euler Path:
Since an Euler circuit exists, any Euler path would also be an Euler circuit.
b) Practical Application: The Euler circuit is perfect for waste collection service routing. A
garbage truck can start from the recycling center (C), traverse every road exactly once
collecting waste, and return to the recycling center without retracing any route. This minimizes
fuel consumption and ensures complete coverage of the district.
Part 3: Algorithmic Solutions for a Connected World
Question 4: Building a Communication Network
Network Setup: Zones: A, B, C, D, E, F, G (7 departments) Cable Installation Costs (in
thousands $):
Weighted Graph Edges:
A-B: 5 A-C: 8 A-D: 12
B-C: 3 B-E: 7 B-F: 9
C-D: 4 C-G: 6 D-E: 10
D-F: 15 E-F: 2 E-G: 11
F-G: 8 A-E: 14 C-F: 13
a) Prim's Algorithm Steps:
Initial: Start from vertex A
● Step 1: Add A to MST. Available edges: {A,B:5}, {A,C:8}, {A,D:12}, {A,E:14}
● Step 2: Choose minimum edge A-B (cost 5). MST = {A,B}
● Step 3: Available: {A,C:8}, {A,D:12}, {B,C:3}, {B,E:7}, {B,F:9}, {A,E:14}
● Step 4: Choose B-C (cost 3). MST = {A,B,C}
● Step 5: Available: {A,D:12}, {C,D:4}, {B,E:7}, {B,F:9}, {C,G:6}, {A,E:14}, {C,F:13}
● Step 6: Choose C-D (cost 4). MST = {A,B,C,D}
● Step 7: Choose C-G (cost 6). MST = {A,B,C,D,G}
● Step 8: Choose B-E (cost 7). MST = {A,B,C,D,G,E}
● Step 9: Choose E-F (cost 2). MST = {A,B,C,D,G,E,F}
Prim's MST: Edges {A,B:5}, {B,C:3}, {C,D:4}, {C,G:6}, {B,E:7}, {E,F:2} Total Cost: 27 thousand
dollars
b) Kruskal's Algorithm Steps:
Step 1: Sort all edges by weight: E-F:2, B-C:3, C-D:4, A-B:5, C-G:6, B-E:7, F-G:8, A-C:8, B-F:9,
D-E:10, E-G:11, A-D:12, C-F:13, A-E:14, D-F:15
Step 2: Build MST using Union-Find:
● Add E-F (2): No cycle
● Add B-C (3): No cycle
● Add C-D (4): No cycle
● Add A-B (5): No cycle
● Add C-G (6): No cycle
● Add B-E (7): No cycle
● Skip F-G (8): Would create cycle E-F-G-C-B-E
Kruskal's MST: Same edges as Prim's Total Cost: 27 thousand dollars
c) Analysis: Same MST: Yes, both algorithms produced identical results. Always the case:
No, when edge weights are unique, the MST is unique. When multiple edges have the same
weight, different valid MSTs may exist. Multiple MSTs implication: When edge weights are
tied, multiple optimal solutions exist with the same total cost.
Question 5: The Logistics Mogul
Delivery Network Setup: Hubs: a, b, c, d, e, f, g (7 distribution centers)
Travel Times (minutes):
Directed Graph Edges:
a→b: 8 a→c: 12 a→d: 15
b→c: 4 b→e: 9 b→f: 11
c→d: 6 c→g: 10 d→e: 7
d→f: 13 e→f: 3 e→g: 5
f→g: 4 c→e: 8 a→e: 20
a) Dijkstra's Algorithm (a to g):
Initialization:
● Distance[a] = 0, all others = ∞
● Unvisited = {a, b, c, d, e, f, g}
Iterations:
Iteration 1: Current = a (dist = 0)
● Update: dist[b] = 8, dist[c] = 12, dist[d] = 15, dist[e] = 20
● Visited: {a}
Iteration 2: Current = b (dist = 8)
● Update: dist[c] = min(12, 8+4) = 12, dist[e] = min(20, 8+9) = 17, dist[f] = 8+11 = 19
● Visited: {a, b}
Iteration 3: Current = c (dist = 12)
● Update: dist[d] = min(15, 12+6) = 15, dist[e] = min(17, 12+8) = 17, dist[g] = 12+10 = 22
● Visited: {a, b, c}
Iteration 4: Current = d (dist = 15)
● Update: dist[e] = min(17, 15+7) = 17, dist[f] = min(19, 15+13) = 19
● Visited: {a, b, c, d}
Iteration 5: Current = e (dist = 17)
● Update: dist[f] = min(19, 17+3) = 20, dist[g] = min(22, 17+5) = 22
● Visited: {a, b, c, d, e}
Iteration 6: Current = f (dist = 20)
● Update: dist[g] = min(22, 20+4) = 22
● Visited: {a, b, c, d, e, f}
Iteration 7: Current = g (dist = 22)
● Algorithm complete
Shortest Path: a → b → e → g Total Time: 8 + 9 + 5 = 22 minutes
c) Algorithm Analysis:
Appropriateness: Dijkstra's algorithm is appropriate for this case because:
● All edge weights (travel times) are positive
● We need shortest path from single source
● Graph is weighted and directed
When Dijkstra Fails:
● Negative edge weights: Algorithm assumes all weights are non-negative
● Negative cycles: Can cause infinite improvement loops
Alternatives:
1. Bellman-Ford Algorithm: Handles negative weights, detects negative cycles
2. Floyd-Warshall Algorithm: All-pairs shortest paths
3. Johnson's Algorithm: Efficient for sparse graphs with negative weights
Real-world Consideration: For delivery logistics, negative weights are rare, but traffic
conditions might create scenarios where Dijkstra's greedy approach isn't optimal due to time-
dependent constraints.
Summary and Conclusions
This assignment demonstrates the practical applications of graph theory in real-world scenarios:
1. Social Network Analysis shows how different representations serve different
computational needs
2. Graph Isomorphism reveals the complexity of structural analysis
3. Euler Circuits provide efficient routing solutions for city services
4. MST Algorithms optimize infrastructure development costs
5. Shortest Path Algorithms enhance logistics and delivery efficiency
The choice of algorithm and representation depends heavily on the specific requirements of the
problem domain, highlighting the importance of understanding both theoretical foundations and
practical constraints in discrete mathematics applications.
Note: All graphs can be visualized using standard graph drawing conventions with vertices as
circles and edges as lines/arrows (for directed graphs). Software tools like Graphviz, NetworkX,
or hand-drawn diagrams can be used for clearer visualization.