Note: This page has been translated by MathWorks. Please click here

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.

Find isomorphism between two graphs

`[`

* Isomorphic*,

`Map`

`G1`

`G2`

[

`Isomorphic`

`Map`

`G1`

`G2`

`DirectedValue`

`G1` | N-by-N sparse matrix that represents a directed or undirected
graph. Nonzero entries in matrix indicate
the presence of an edge.`G1` |

`G2` | N-by-N sparse matrix that represents a directed or undirected
graph. must be the same (directed or
undirected) as `G2` .`G1` |

`DirectedValue` | Property that indicates whether the graphs are directed or
undirected. Enter `false` when both and `G1` are
undirected graphs. In this case, the upper triangles of the sparse
matrices `G2` and `G1` are
ignored. Default is `G2` `true` , meaning that both graphs
are directed. |

For introductory information on graph theory functions, see Graph Theory Functions.

`[`

returns logical 1 (* Isomorphic*,

`Map`

`G1`

`G2`

`true`

) in `Isomorphic`

`G1`

`G2`

`false`

) otherwise.
A graph isomorphism is a 1-to-1 mapping of the nodes in the graph `G1`

`G2`

`G1`

`G2`

`Isomorphic`

`Isomorphic`

`true`

, `Map`

`G2`

`G1`

`Isomorphic`

`false`

, `Map`

`O(N!)`

,
where `N`

is the number of nodes.`[`

indicates whether the graphs are directed or undirected. Set * Isomorphic*,

`Map`

`G1`

`G2`

`DirectedValue`

`DirectedValue`

`false`

when
both `G1`

`G2`

`G1`

`G2`

`true`

, meaning that both graphs
are directed.Create and view a directed graph with 8 nodes and 11 edges.

m('ABCDEFGH') = [1 2 3 4 5 6 7 8]; g1 = sparse(m('ABDCDCGEFFG'),m('BCBDGEEFHGH'),true,8,8) g1 = (1,2) 1 (4,2) 1 (2,3) 1 (3,4) 1 (3,5) 1 (7,5) 1 (5,6) 1 (4,7) 1 (6,7) 1 (6,8) 1 (7,8) 1 view(biograph(g1,'ABCDEFGH'))

Set a random permutation vector and then create and view a new permuted graph.

`p = randperm(8) p = 7 8 2 3 6 4 1 5 g2 = g1(p,p); view(biograph(g2,'12345678'))`

Check if the two graphs are isomorphic.

[F,Map] = graphisomorphism(g2,g1) F = 1 Map = 7 8 2 3 6 4 1 5

Note that the

`Map`

row vector containing the node indices that map from`g2`

to`g1`

is the same as the permutation vector you created in step 2.Reverse the direction of the D-G edge in the first graph, and then check for isomorphism again.

g1(m('DG'),m('GD')) = g1(m('GD'),m('DG')); view(biograph(g1,'ABCDEFGH'))

[F,M] = graphisomorphism(g2,g1) F = 0 M = []

Convert the graphs to undirected graphs, and then check for isomorphism.

`[F,M] = graphisomorphism(g2+g2',g1+g1','directed',false) F = 1 M = 7 8 2 3 6 4 1 5`

[1] Fortin, S. (1996). The Graph Isomorphism Problem. Technical Report, 96-20, Dept. of Computer Science, University of Alberta, Edomonton, Alberta, Canada.

[2] McKay, B.D. (1981). Practical Graph Isomorphism.
Congressus Numerantium *30*, 45-87.

[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).

`graphallshortestpaths`

| `graphconncomp`

| `graphisdag`

| `graphisspantree`

| `graphmaxflow`

| `graphminspantree`

| `graphpred2path`

| `graphshortestpath`

| `graphtopoorder`

| `graphtraverse`

| `isomorphism`

Was this topic helpful?