Please be thorough. I really apreciate your time in advance. Graph Isomorphism:
ID: 2900745 • Letter: P
Question
Please be thorough. I really apreciate your time in advance.
Graph Isomorphism: The brute forth method goes through all possible labelings and checks whether each gives an isomorphism. Suppose II is a graph that also has n vertices. Given a labeling of both G and II 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
Step 1. To each node y E V, associate a list (al , ..- , ai) where ai equals the
exact number of nodes, x~ E V ~suchthat (y, xz) E E (1 _< j _< i). Note that
~=1 a1 = d(y), the degree of vertex y.
Step 2. We now define a refinement of the jth cell.
(i) Perform an ordering of the nodes in the cell by examining the lists associated
with the nodes of V j. Order the nodes by lexicographically ordering their lists.
(ii) If all the nodes have the same list, no refinement is done.
(iii) If the lists are not identical, use the ordering of the nodes of V ~ to refine
V j as follows: Assume that node y precedes all other nodes of V~; then the first
subcell of V j consists of node y and all other nodes of V j which have the same list
as y. Remove these nodes from V i, and from the remaining nodes choose the node
that precedes all other remaining nodes.
Step 3. Apply step 2 to all i cells. If at least one of the cells is refined, then we
reindex all the cells and go to step 1. This reindexing is carried out as follows:
Assume that cells 1 to j - 1 are not refined, but cell j is; cells 1 to j - 1 retain
their previous cell indices. Index the 1 subcells of cell j as j, j + 1,