Q1: Are the following two graphs the same? Discuss whether the problem above is an NP, NP-hard, NP-complete or P class problem.
Two graphs are said to be isomorphic or similar if they follow the following conditions:
- Both of them possess an equal number of vertices
- Both of them possess an equal number of edges
- Both of them have the same degree sequence
- Both of them have the same number of the circuit of a particular length.
Naming the graph on the left-hand side of the image as G1 and the graph on the right-hand side of the image as G2 for simplicity.
The degree of a vertex is defined as the number of edges incident to the vertex.
Both the graphs G1 and G2 have the same number of vertices i.e, 4 (a,b,c,d)
Graph G1 posses 5 edges (ab,bc,cd,da,bd) and graph G2 also posses 5 edges (ab,bc,da,ac,bd)
For Graph G1,
degree (a)=2, degree(b)=3, degree(c)=2, degree(d)=3
So, the degree sequence for graph G1=<2,2,3,3>
For Graph G2,
degree (a)=3, degree(b)=3, degree(c)=2, degree(d)=2
So, the degree sequence for graph G1=<2,2,3,3>
Graph G1 has 2 cycles of size 3(abd,bcd).
Graph G2 also has 2 cycles of size 3(abd,acb).
As both the graphs G1, G2 follows all the conditions of isomorphism, so the graphs G1 and G2 are isomorphic and hence the same.
Step by step
Solved in 3 steps
