For (part a) describe the process of verification in terms of the adjacency matr

Question

For (part a) describe the process of verification in terms of the adjacency matrices for G and H.

Graph Isomorphism: The brute forth method goes through all possible labelings and checks whether each gives an isomorphism. Suppose H is a graph that also has n vertices. Given a labeling of both G and H with 1 to n, describe (formally or informally) an algorithm that checks whether the labeling is a valid isomorphism. Give the time complexity O(g) of your algorithm. Use part (a) to determine the brute-force time complexity of whether two graphs are isomorphic.

Explanation / Answer

Given the adjacency matrices of G & H, called A(G) and A(H) respectively. Each matrix is an n x n matrix.

(a) Alg to check whether the labeling is a valid isomorphism.

Given A(H). Compare all possible permutations of A(G) with A(H) and check for equality (compare line by line to see if values are same). A permutation of A(G) is defined as a rearrangement of the columns along with reflected change in the columns.

Time Complexity:

To check for equality between A(H) and a permutation of A(G) requires O(n^2) time. There are n! possible permutations of A(G). Hence, the time complexity is O(n! n^2).

(b) We have to check which of the labelings results in an isomorphic graph to initial graph H.. There are n! possible labelings. We already know that the time complexity to compare one such labeling with H is O(n! n^2). We must compare n! such graphs. Hence the time complexity is O( (n!)^2 n^2).

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.