# Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English verison of the page.

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

# isomorphism (biograph)

Find isomorphism between two biograph objects

## Syntax

```[Isomorphic, Map] = isomorphism(BGObj1, BGObj2) [Isomorphic, Map] = isomorphism(BGObj1, BGObj2,'Directed', DirectedValue) ```

## Arguments

 `BGObj1` Biograph object created by `biograph` (object constructor). `BGObj2` Biograph object created by `biograph` (object constructor). `DirectedValue` Property that indicates whether the graphs are directed or undirected. Enter `false` when both `BGObj1` and `BGObj2` produce undirected graphs. In this case, the upper triangles of the sparse matrices extracted from `BGObj1` and `BGObj2` are ignored. Default is `true`, meaning that both graphs are directed.

## Description

### Tip

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

```[Isomorphic, Map] = isomorphism(BGObj1, BGObj2)``` returns logical 1 (`true`) in `Isomorphic` if two N-by-N adjacency matrices extracted from biograph objects `BGObj1` and `BGObj2` are isomorphic graphs, and logical 0 (`false`) otherwise. A graph isomorphism is a 1-to-1 mapping of the nodes in the graph from `BGObj1` and the nodes in the graph from `BGObj2` such that adjacencies are preserved. Return value `Isomorphic` is Boolean. When `Isomorphic` is `true`, `Map` is a row vector containing the node indices that map from `BGObj2` to `BGObj1`. When `Isomorphic` is `false`, the worst-case time complexity is `O(N!)`, where `N` is the number of nodes.

```[Isomorphic, Map] = isomorphism(BGObj1, BGObj2,'Directed', DirectedValue)``` indicates whether the graphs are directed or undirected. Set `DirectedValue` to `false` when both `BGObj1` and `BGObj2` produce undirected graphs. In this case, the upper triangles of the sparse matrices extracted from `BGObj1` and `BGObj2` are ignored. The default is `true`, meaning that both graphs are directed.

## References

[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).