determine if two graphs are isomorphic
(optional) name to assign mapping of graph 1 to graph 2
The IsIsomorphic command accepts either two undirected graphs or two directed graphs as input. It returns true if the graphs are isomorphic to each other, and false otherwise. If the graphs are weighted graphs, the edge weights are ignored.
If a third argument phi is provided, it is assigned to a list of equations of the form v1=v2, where the v1 and v2 correspond to the vertices of graph 1 and graph 2 respectively, that provide a mapping of vertices that shows the graphs are isomorphic.
The method used is a backtracking algorithm that provides reasonable efficiency even for large graphs. (In general the graph isomorphism problem is exponential in the number of vertices.) The algorithm uses the all pairs distance matrix to prune the search tree.
An undirected graph example (G1 and G3 are isomorphic).
G1 ≔ Graph⁡Trail⁡1,2,3,4,5,6,1,3
G1≔Graph 1: an undirected graph with 6 vertices and 7 edge(s)
G2 ≔ Graph⁡Trail⁡1,2,3,4,5,6,1,4
G2≔Graph 2: an undirected graph with 6 vertices and 7 edge(s)
G3 ≔ Graph⁡Trail⁡1,2,3,4,5,6,1,5
G3≔Graph 3: an undirected graph with 6 vertices and 7 edge(s)
A directed graph example (D1 and D3 are isomorphic).
D1 ≔ Graph⁡directed,Trail⁡1,2,3,1,4,5
D1≔Graph 4: a directed graph with 5 vertices and 5 arc(s)
D2 ≔ Graph⁡directed,Trail⁡1,2,3,4,5,3
D2≔Graph 5: a directed graph with 5 vertices and 5 arc(s)
D3 ≔ Graph⁡directed,Trail⁡3,4,5,3,1,2
D3≔Graph 6: a directed graph with 5 vertices and 5 arc(s)
Create isomorphic permutation of Petersen graph, and check
P1 ≔ SpecialGraphsPetersenGraph⁡
P1≔Graph 7: an undirected graph with 10 vertices and 15 edge(s)
P2 ≔ IsomorphicCopy⁡P1
P2≔Graph 8: an undirected graph with 10 vertices and 15 edge(s)
Apply permutation to permuted graph to obtain original Petersen graph and compare adjacency matrices
P2 ≔ IsomorphicCopy⁡P2,map⁡rhs,mp
P2≔Graph 9: an undirected graph with 10 vertices and 15 edge(s)
A1 ≔ AdjacencyMatrix⁡P1
A2 ≔ AdjacencyMatrix⁡P2
The GraphTheory[IsIsomorphic] command was updated in Maple 18.
The G1 and G2 parameters were updated in Maple 18.
Download Help Document