Design and Algorithms Isomorphic Graph Two graphs are isomor

Design and Algorithms Isomorphic Graph

Two graphs are isomorphic when the vertices of one can be re-labeled to match the vertices of the other in a way that preserves adjacency. More formally, a graph G_1 is isomorphic to a graph G_2 if there exists a one-to-one function f, called an isomorphism, from V_1 (the vertex set of G_1) onto V_2 such that (u_1, v_1) is an element of E_1 (the edge set of G_1) if and only if (u_2, v_2) is an element of E_2. GRAPH-ISO = { | G_1 and G_2 are two isomorphic graphs}. Prove that GRAPH-ISO is in NP. Example below. An isomorphism between G and H f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7

Solution

A finite simple graph G consists of a set of vertices V, with |V| = n, and a set of edges E, such that each edge is an unordered pair of distinct vertices. The definition of a simple graph G forbids loops (edges joining a vertex to itself) and multiple edges (many edges joining a pair of vertices), whence the set E must also be finite, with |E| = m. We label the vertices of G with the integers 1, 2, ..., n. If the unordered pair of vertices {u, v} is an edge in G, we say that u is adjacent to v and write uv E. Adjacency is a symmetric relationship: uv E if and only if vu E. The degree of a vertex v is the number of vertices that are adjacent to v. A (u, v)-path P in G is a sequence of distinct vertices u = v1, v2, ..., vk = v such that vivi+1 E for i = 1, 2, ..., k-1. If such a (u, v)-path P exists, then the vertices u and v are said to be connected by a path of length k-1.
Given any pair of vertices (u, v) in G, we define the distance

d(u, v)   =   0, if u = v,
d(u, v)   =   the length of a shortest (u, v)-path, if u and v are connected, and
d(u, v)   =   , otherwise.
We now introduce the key ingredients of semiotic theory. For any pair of vertices (u, v) in G, the collateral graph G\\uv is defined as follows:
•   If uv E, then G\\uv is obtained by deleting the edge uv from G while preserving all the vertices of G. We use the binary sign + to distinguish the distance function in this case.
•   If uv E, then G\\uv = G. We use the binary sign to distinguish the distance function in this case.
The pair graph Guv for any pair of vertices (u, v) in G is defined as follows:
•   w is a vertex of Guv if and only if w belongs to a shortest (u, v)-path in G\\uv, and
•   wx is an edge of Guv if and only if wx is also an edge of G.
For any pair of vertices (u, v) in G, we write the (u, v)-sign, denoted by the symbol suv, as follows:

suv   =   ±   duv   .   nuv   .   muv
where
•   the leading binary sign is positive if uv E, or negative if uv E;
•   duv is the distance d(u, v) in the collateral graph G\\uv ;
•   nuv is the number of vertices of the pair graph Guv;
•   muv is the number of edges of the pair graph Guv.
The sign matrix S of the graph G is written as an n × n array with the (u, v)-sign suv as the entry in row u and column v,

S   =   [   suv   ]   .
The adjacency matrix of G is an n × n matrix with the entry in row u and column v equal to 1 if uv E and equal to 0 if uv E. Thus, the adjacency matrix of the graph G can be recovered from the leading binary signs of the entries of the sign matrix S. Note that for a simple graph G, both the adjacency matrix and the sign matrix S are symmetric.
We shall now define a canonical form S* of the sign matrix by ordering the rows and columns of S in a certain way. First, write the set of all distinct (u, v)-signs suv in lexicographic order s1, s2, ..., sr. Then, for each row i of the sign matrix, i = 1, 2, ..., n, compute the sign frequency vector

fi   =   (   fi(1), fi(2), ..., fi(r)   )
where fi(k) is the number of times the sign sk occurs in row i. Since S is symmetric, the sign frequency vector for column i is the same as the sign frequency vector for row i, for i = 1, 2, ..., n. Now, write the sign frequency vectors f1, f2, ..., fn in lexicographic order fi1, fi2, ..., fin. Reorder the rows and columns of the sign matrix according to the permutation i1, i2, ..., in of the vertices 1, 2, ..., n of G to obtain the canonical form S* of the sign matrix.
The vertices of G are partitioned into equivalence classes consisting of vertices with the same sign frequency vectors. Thus, the canonical form S* of the sign matrix is uniquely defined only upto permutations of vertices within each equivalence class.
Graphs GA and GB are said to be isomorphic if there exists a bijection

: VA VB
from the vertices of graph GA to the vertices of graph GB, such that uv is an edge in graph GA if and only if (u)(v) is an edge in graph GB. The graph isomorphism problem is to determine whether two given graphs are isomorphic or not.
An algorithm is a problem-solving method suitable for implementation as a computer program. While designing algorithms we are typically faced with a number of different approaches. For small problems, it hardly matters which approach we use, as long as it is one that solves the problem correctly. However, there are many problems for which the only known algorithms take so long to compute the solution that they are practically useless. For instance, the naïve approach of computing all n! possible permutations of the n vertices to show that a pair of graphs GA and GB are not isomorphic is impractical even for small inputs.
A polynomial-time algorithm is one whose number of computational steps is always bounded by a polynomial function of the size of the input. Thus, a polynomial-time algorithm is one that is actually useful in practice. The class of all problems that have polynomial-time algorithms is denoted by P. If graphs GAand GB are isomorphic then they must have the same sign frequency vectors in lexicographic order fi1, fi2, ..., fin and we shall show that our algorithm obtains identical canonical forms of their sign matrices SA* and SB* in polynomial-time, thus exhibiting an explicit isomorphism function . Conversely, we shall show that our algorithm determines in polynomial-time that the sign matrices SA* and SB* cannot be expressed in identical canonical forms if and only if the graphs GA and GB are not isomorphic. Thus, we have a polynomial-time algorithm for solving the graph isomorphism problem, showing that the graph isomorphism problem is in P.

3. Algorithm
We are now ready to present a formal description of the algorithm. After that, the steps of the algorithm will be illustrated by an example. We begin by defining four procedures.
3.1. Procedure. This procedure is Dijkstra\'s algorithm [3]. Given a graph G and a vertex u, we compute shortest (u, v)-paths to all vertices v of G. Define a(u, v) = 1 if uv E and a(u, v) = if uv E. We maintain a set Vknown of vertices to which the shortest (u, v)-path is known and a tentative distance d\'(u, w) for each vertex w outside Vknown.
•   Initialization: Set Vknown = {u}, d(u, u) = 0 and d\'(u, w) = a(u, w) for each vertex w outside Vknown.
•   Iteration: Select a vertex wmin outside Vknown such that d\'(u, wmin) is a minimum. Add wmin to Vknown and update the tentative distance d\'(u, w) = min{d\'(u, w), d(u, w)+a(u, w)} for each vertex w outside Vknown.
•   Termination: Iterate until Vknown contains all the vertices of G or until d\'(u, w) = for each vertex w outside Vknown. In the later case, no further vertex can be selected and the remaining vertices are not connected to the vertex u.
3.2. Procedure. Given a graph G and vertices u and v, we compute the distance d(u, v) in the collateral graph G\\uv and the pair graph Guv.
•   Using Procedure 3.1, compute shortest (u, x)-paths to all vertices x of G\\uv.
•   Using Procedure 3.1, compute shortest (v, y)-paths to all vertices y of G\\uv.
•   In particular, the length of any shortest (u, v)-path in G\\uv is the distance d(u, v).
•   If u = u1, u2, ..., ur and v = v1, v2, ..., vs are shortest paths found above such that ur = vs and the sum of the lengths of the two paths is the distance d(u, v) in the collateral graph G\\uv, then the union of vertices of the two paths are vertices of the pair graph Guv. Every vertex w of the pair graph Guv is obtained this way, because any shortest (u, v)-path containing w is obtained by connecting some shortest (u, w)-path with some shortest (w, v)-path in G\\uv. Thus, at least one pair of shortest paths found above must satisfy ur = vs = w, for each vertex w of the pair graph Guv.
3.3. Procedure. Given a graph G, we compute the sign matrix S and its canonical form S*.
•   Using Procedure 3.2, for every pair of vertices u and v, we compute the distance d(u, v) in the collateral graph G\\uv and the pair graph Guv.
•   The entry in row u and column v of the sign matrix S is suv = ± duv.nuv.muv, where the leading binary sign is positive if uv E, and negative if uv E; duv is the distance d(u, v) in the collateral graph G\\uv; nuv is the number of vertices of the pair graph Guv; and muv is the number of edges of the pair graph Guv.
•   Write the set of all distinct signs suv in lexicographic order s1, s2, ..., sr.
•   For each row i of the sign matrix S, i = 1, 2, ..., n, compute the sign frequency vector fi = ( fi(1), fi(2), ..., fi(r)), where fi(k) is the number of times the sign skoccurs in row i. Since S is symmetric, the sign frequency vector for column i is the same as the sign frequency vector for row i, for i = 1, 2, ..., n.
•   Write the sign frequency vectors f1, f2, ..., fn in lexicographic order fi1, fi2, ..., fin.
•   Reorder the rows and columns of the sign matrix according to the permutation i1, i2, ..., in of the vertices 1, 2, ..., n of G to obtain the canonical form S*.
3.4. Procedure. Given graphs GA and GB such that the sign frequency vectors in lexicographic order for SA* and SB* are the same, ( fAi1, fAi2, ..., fAin ) = ( fBi\'1, fBi\'2, ..., fBi\'n ), we compute a reordering i\'\'1, i\'\'2, ..., i\'\'n of the vertices of GB such that either the first entry of SB* that does not match the corresponding entry of SA* occurs at the greatest possible index in row major order or SA* = SB*.
•   Set A = SA* and B = SB*.
•   Read the matrices A and B in row major order (read each row from left to right and read the rows from top to bottom). If all corresponding entries Aij and Bij of A and B match, then stop. Else, find the first entry Bij in B that does not match the corresponding entry Aij in A. Find k > i such that interchanging rows (k, j) and columns (k, j) of B ensures that the first mismatch occurs later than Bij in row major order (or there is no mismatch at all). If no such kexists, then stop. Repeat this process until the corresponding k cannot be found or all corresponding entries of A and B match.
•   We obtain a reordering i\'\'1, i\'\'2, ..., i\'\'n of the vertices of GB such that either the first entry of B that does not match the corresponding entry of A occurs at the greatest possible index in row major order or A = B.

3.5. Algorithm. Given graphs GA and GB, we determine whether GA and GB are isomorphic or not. If GA and GB are isomorphic, we exhibit an explicit isomorphism function.
•   Using Procedure 3.3, we compute the canonical forms of the sign matrices SA* and SB*. If the sign frequency vectors in lexicographic order for SA* and SB* are different, then GA and GB are not isomorphic and we stop.
•   Else, the sign frequency vectors in lexicographic order for SA* and SB* are the same, ( fAi1, fAi2, ..., fAin ) = ( fBi\'1, fBi\'2, ..., fBi\'n ).
o   For k = 1, 2, ..., n :
   Set A = SA* and B = SB*.
   Interchange rows (1, k) and columns (1, k) of B.
   Using Procedure 3.4, if A = B then stop. Else, start with the next value of k. If k = n then stop.
o   If A B, then GA and GB are not isomorphic. Else A = B, GA and GB are isomorphic and the reordering i\'\'1, i\'\'2, ..., i\'\'n of the vertices of GB to obtain SB* = B provides an explicit isomorphism function (i1) = i\'\'1, (i2) = i\'\'2, ..., (in) = i\'\'n.

One of the simplest ideas is that of Graph Invariants using which you can quickly test for non-isomorphism.

Graph invariants are properties associated with a graph that do not change across all possible isomorphisms of the graph. In other words, if a set of graphs are isomorphic, then they all have the same values for certain properties which are called invariants. To put it in another way: if two graphs have one or more of their invariants different, they are, well, non-isomorphic.

Examples of graph invariants are the following:

•   no of nodes
•   no of edges
•   the degree distribution (or degree sequence)
•   vertex (or edge) chromatic number: the minimum no. of colours needed to colour all vertices (edges) such that adjacent vertices (edges) do not have the same colour
•   vertex (or edge) covering number: the minimum no. of vertices (edges) needed to cover all edges (vertices)

As you can see, graph invariants can be either single numbers (scalars) or simple vectors. A graph invariant describes a graph in terms of simple quantities. Given a graph, it has a unique number of nodes, number of edges, degree sequence etc. Therefore, it is straightforward to compare them and establish non-isomorphism.

Thus, in case you want to use the brute-force approach, optimize it by first running the pairs of graphs through at least the simplest of the invariance tests.

It should be noted that the incidence and adjacency matrices are not graph invariants. This is because, when isomorphism is computed, if for every pair of adjacent nodes in graph-1, you can find a pair of adjacent nodes in graph-2, and vice versa (i.e., a bijection), the two graphs are isomorphic; labels are not important.

It is perhaps obvious already, but let me state this clearly. While, for a given graph, there are unique invariants, the converse need not hold. If that were the case, graph isomorphism would have had a polynomial time algorithm. We can easily find two or more graphs that have the same degree sequence, but are non-isomorphic.

First Make Adjacency matrix for both graphs.
These matrices would be square and symmetrical. (If No multiple or directed edges)
The main diagonal would be all zeroes (if no loops)
if number of 1s and 0s are not the same in both matrices then its not isomorphic surely. If they are same then it may be isomorphic.
Take any one of the matrices.
Now you can swap 2 coloumns of this matrix but when you do that you must also swap the same rows.
So while swapping row2 and row3, you should immediately swap col2 and col3 as well. Order of swapping doesnt matter. Since its square matrix, all columns will have corresponding rows.
Doing this would simply swap the vertex\'s position in adjacency matrix and so changing the mapping of each vertex.
By use of our pattern finding ability we can choose which rows and columns to swap so that one matrix would look exactly like the other. You would get it in max 3-4 swaps.
Its quite easy since they are square symmetrical.
If they are not isomorphic then you might try to swap rows and cols endlessly trying to match the pattern but by little intuition you can avoid that.
They are isomorphic if adjacency matrix look same. This matrix would give you the mappings.
So its like trying to find a mapping from all possible mappings of one graph, that look exactly like the other adjacency matrix by cleaverly swapping position of vertices (by swaping rows and cols). Does not work so good for huge graphs.