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.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{G1}≔\mathrm{Graph}\left(\mathrm{Trail}\left(1\,2\,3\,4\,5\,6\,1\,3\right)\right)$

$\mathrm{G1}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 7\; edge(s)}$

$\mathrm{G2}≔\mathrm{Graph}\left(\mathrm{Trail}\left(1\,2\,3\,4\,5\,6\,1\,4\right)\right)$

$\mathrm{G2}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 7\; edge(s)}$

$\mathrm{G3}≔\mathrm{Graph}\left(\mathrm{Trail}\left(1\,2\,3\,4\,5\,6\,1\,5\right)\right)$

$\mathrm{G3}≔\mathrm{Graph\; 3:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 7\; edge(s)}$

$\mathrm{DrawGraph}\left(\left[\mathrm{G1}\,\mathrm{G2}\,\mathrm{G3}\right]\,\mathrm{width}=3\,\mathrm{style}=\mathrm{circle}\right)$

$\mathrm{IsIsomorphic}\left(\mathrm{G1}\,\mathrm{G2}\right)$

$\mathrm{false}$

$\mathrm{IsIsomorphic}\left(\mathrm{G1}\,\mathrm{G3}\,'\mathrm{\phi }'\right)$

$\mathrm{true}$

$\mathrm{\phi }$

$\left[1=1\,2=6\,3=5\,4=4\,5=3\,6=2\right]$

$\mathrm{D1}≔\mathrm{Graph}\left(\mathrm{directed}\,\mathrm{Trail}\left(1\,2\,3\,1\,4\,5\right)\right)$

$\mathrm{D1}≔\mathrm{Graph\; 4:\; a\; directed\; graph\; with\; 5\; vertices\; and\; 5\; arc(s)}$

$\mathrm{D2}≔\mathrm{Graph}\left(\mathrm{directed}\,\mathrm{Trail}\left(1\,2\,3\,4\,5\,3\right)\right)$

$\mathrm{D2}≔\mathrm{Graph\; 5:\; a\; directed\; graph\; with\; 5\; vertices\; and\; 5\; arc(s)}$

$\mathrm{D3}≔\mathrm{Graph}\left(\mathrm{directed}\,\mathrm{Trail}\left(3\,4\,5\,3\,1\,2\right)\right)$

$\mathrm{D3}≔\mathrm{Graph\; 6:\; a\; directed\; graph\; with\; 5\; vertices\; and\; 5\; arc(s)}$

$\mathrm{DrawGraph}\left(\left[\mathrm{D1}\,\mathrm{D2}\,\mathrm{D3}\right]\,\mathrm{width}=3\,\mathrm{style}=\mathrm{circle}\right)$

$\mathrm{IsIsomorphic}\left(\mathrm{D1}\,\mathrm{D2}\right)$

$\mathrm{false}$

$\mathrm{IsIsomorphic}\left(\mathrm{D1}\,\mathrm{D3}\,'\mathrm{\phi }'\right)$

$\mathrm{true}$

$\mathrm{\phi }$

$\left[1=3\,2=4\,3=5\,4=1\,5=2\right]$

$\mathrm{P1}≔\mathrm{SpecialGraphs}\left[\mathrm{PetersenGraph}\right]\left(\right)$

$\mathrm{P1}≔\mathrm{Graph\; 7:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edge(s)}$

$\mathrm{P2}≔\mathrm{IsomorphicCopy}\left(\mathrm{P1}\right)$

$\mathrm{P2}≔\mathrm{Graph\; 8:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edge(s)}$

$\mathrm{IsIsomorphic}\left(\mathrm{P1}\,\mathrm{P2}\,'\mathrm{mp}'\right)$

$\mathrm{true}$

$\mathrm{mp}$

$\left[1=1\,2=7\,3=3\,4=2\,5=6\,6=9\,7=8\,8=10\,9=5\,10=4\right]$

$\mathrm{P2}≔\mathrm{IsomorphicCopy}\left(\mathrm{P2}\,\mathrm{map}\left(\mathrm{rhs}\,\mathrm{mp}\right)\right)$

$\mathrm{P2}≔\mathrm{Graph\; 9:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edge(s)}$

$\mathrm{A1}≔\mathrm{AdjacencyMatrix}\left(\mathrm{P1}\right)$

$\mathrm{A1}≔\left[\right]$

$\mathrm{A2}≔\mathrm{AdjacencyMatrix}\left(\mathrm{P2}\right)$

$\mathrm{A2}≔\left[\right]$

$\mathrm{LinearAlgebra}:-\mathrm{Equal}\left(\mathrm{A1}\,\mathrm{A2}\right)$

$\mathrm{true}$

The GraphTheory[IsIsomorphic] command was updated in Maple 18.

The G1 and G2 parameters were updated in Maple 18.