Data Science Module: Comprehensive Graph Theory Assignment Solution

This assignment solution covers a range of graph theory concepts. It begins by identifying the shortest path in a graph and calculating its total weight. The solution then determines whether a given graph is strongly connected and proposes a modification to achieve strong connectivity. Further, it addresses graph isomorphism, providing mappings between nodes. Clustering coefficients are calculated for specific nodes, and the strong triadic closure property is analyzed. The solution also lists maximal cliques within a graph and determines its diameter. Finally, it analyzes shortest paths and flow amounts in a graph using breadth-first search.

Q1 Answer:
The shortest path from A to H is ABEFH. Where total weight is 2+2+2+2 = 8.
The diameter of this graph is (ACDEIHJK) is 8 and the total weight is 1+4+4+5+4+1+2 = 21
The shortest path which has the length of the diameter is (ACDEFHJK).
Q2 Answer:
A strongly connected graph is a graph in which we can access all the vertices or node in one single
path. That means there should exist at least one single path through which we can access or go to
every node of the graph. So for the above graph, there is no path to access the node G. So the above
graph is not a strongly connected graph.
So if we reverse the path between GK then we can able to access the G node in one single path
(ABEIKGFDC). So by reversing the path between GK, we can make the graph a strongly connected
graph.
Q3.1 Answer:
Yes, the graphs are isomorphic.
The mapping between nodes.
Q3.1 Answer:
Yes, the graphs are isomorphic
The mapping between nodes.

Q4 Answer:
Clustering co-efficients of A
Number of friends is(n) = 4 Where friends are B,E,I,J
Number of friends pair is(m) = 2 Where friends pair are BE and IE
Clustering co-efficients of A is
C(A) = m/((n * (n -1))/2) = 2/((4 * (4 -1))/2) = 1/3
Clustering co-efficients of G
Number of friends is(n) = 5 Where friends are J,F,C,H,K
Number of friends pair is(m) = 5 Where friends pair are JF,FC,CH,HK,KJ
Clustering co-efficients of G is
C(G) = m/((n * (n -1))/2) = 5/((5 * (5 -1))/2) = 1/2
Q5 Answer:
Node D violate the Strong triadic closure property here. Since D has two weak ties with E and B and
there is no common friends D and E or D and B are exist.
Q6 Answer:
List of maximal cliques are
1. ACLD
2. ABD
3. BDG
4. BEG
5. GEF

6. GFH
7. EFHI
8. IHJ
So there are 8 maximal cliques.
Q7 Answer:
The diameter of this graph is (ACEFHG) is 6
Number of shortest path(s) from A to G is 1 which is (ABG)
Queue Status
1. A
2. BCE
3. CEDG
4. EDG
5. DGF
6. DGF
7. DGF
8. GFH

9. FH
10. H
Number of the shortest path from A to B is 1 (AB)
Amount of flow from A to B is 1.
Number of the shortest path from A to C is 1 (AC)
Amount of flow from A to C is 1.
Number of the shortest path from A to E is 1 (AE)
Amount of flow from A to E is 1.
Number of the shortest path from A to D is 2 (ABD,ACD)
Amount of flow from A to D is 3.
Number of the shortest path from A to G is 1 (ABG)
Amount of flow from A to G is 3.
Number of shortest path from A to F is 1 (AEF)
Amount of flow from A to F is 2.
Number of shortest path from A to H is 3 (AEFH,ACDH and ABGH)
Amount of flow from A to G is 3.