graphisomorphism
(Removed) Find isomorphism between two graphs
graphisomorphism
has been removed. Use isomorphism
instead.
Syntax
[
Isomorphic
, Map
]
= graphisomorphism(G1
, G2
)
[Isomorphic
, Map
]
= graphisomorphism(G1
, G2
,'Directed', DirectedValue
)
Arguments
G1
| N-by-N adjacency matrix that represents a directed or undirected
graph. Nonzero entries in matrix G1
indicate the presence of an edge. |
G2 | N-by-N adjacency matrix that represents a directed or undirected
graph. G2 must be the same (directed or
undirected) as G1 . |
DirectedValue | Property that indicates whether the graphs are directed or
undirected. Enter false when both
G1 and G2
are undirected graphs. In this case, the upper triangles of the
matrices G1 and
G2 are ignored. Default is
true , meaning that both graphs are
directed. |
Description
Tip
For introductory information on graph theory functions, see Graph Theory Functions.
[
returns logical 1 (Isomorphic
, Map
]
= graphisomorphism(G1
, G2
)true
) in Isomorphic
if
G1
and G2
are isomorphic
graphs, and logical 0 (false
) otherwise. A graph isomorphism is a
1-to-1 mapping of the nodes in the graph G1
and the nodes in
the graph G2
such that adjacencies are preserved.
G1
and G2
are both N-by-N
adjacency matrices that represent directed or undirected graphs. Return value
Isomorphic
is Boolean. When
Isomorphic
is true
,
Map
is a row vector containing the node indices that map
from G2
to G1
for one possible
isomorphism. When Isomorphic
is false
,
Map
is empty. The worst-case time complexity is
O(N!)
, where N
is the number of nodes.
[
indicates whether the graphs are directed or undirected. Set
Isomorphic
, Map
]
= graphisomorphism(G1
, G2
,'Directed', DirectedValue
)DirectedValue
to false
when both
G1
and G2
are undirected
graphs. In this case, the upper triangles of the matrices G1
and G2
are ignored. 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).