 GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/IsIsomorphic

GraphTheory

 IsIsomorphic
 determine if two graphs are isomorphic

 Calling Sequence IsIsomorphic(G1,G2) IsIsomorphic(G1,G2,phi)

Parameters

 G1 - graph 1 G2 - graph 2 phi - (optional) name to assign mapping of graph 1 to graph 2

Description

 • 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.

Examples

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

An undirected graph example (G1 and G3 are isomorphic).

 > $\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 unweighted graph with 6 vertices and 7 edge\left(s\right)}}$ (1)
 > $\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 unweighted graph with 6 vertices and 7 edge\left(s\right)}}$ (2)
 > $\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 unweighted graph with 6 vertices and 7 edge\left(s\right)}}$ (3)
 > $\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}}$ (4)
 > $\mathrm{IsIsomorphic}\left(\mathrm{G1},\mathrm{G3},'\mathrm{\phi }'\right)$
 ${\mathrm{true}}$ (5)
 > $\mathrm{\phi }$
 $\left[{1}{=}{1}{,}{2}{=}{6}{,}{3}{=}{5}{,}{4}{=}{4}{,}{5}{=}{3}{,}{6}{=}{2}\right]$ (6)

A directed graph example (D1 and D3 are isomorphic).

 > $\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 unweighted graph with 5 vertices and 5 arc\left(s\right)}}$ (7)
 > $\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 unweighted graph with 5 vertices and 5 arc\left(s\right)}}$ (8)
 > $\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 unweighted graph with 5 vertices and 5 arc\left(s\right)}}$ (9)
 > $\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}}$ (10)
 > $\mathrm{IsIsomorphic}\left(\mathrm{D1},\mathrm{D3},'\mathrm{\phi }'\right)$
 ${\mathrm{true}}$ (11)
 > $\mathrm{\phi }$
 $\left[{1}{=}{3}{,}{2}{=}{4}{,}{3}{=}{5}{,}{4}{=}{1}{,}{5}{=}{2}\right]$ (12)

Create isomorphic permutation of Petersen graph, and check

 > $\mathrm{P1}≔\mathrm{SpecialGraphs}\left[\mathrm{PetersenGraph}\right]\left(\right)$
 ${\mathrm{P1}}{≔}{\mathrm{Graph 7: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (13)
 > $\mathrm{P2}≔\mathrm{IsomorphicCopy}\left(\mathrm{P1}\right)$
 ${\mathrm{P2}}{≔}{\mathrm{Graph 8: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (14)
 > $\mathrm{IsIsomorphic}\left(\mathrm{P1},\mathrm{P2},'\mathrm{mp}'\right)$
 ${\mathrm{true}}$ (15)
 > $\mathrm{mp}$
 $\left[{1}{=}{1}{,}{2}{=}{7}{,}{3}{=}{3}{,}{4}{=}{2}{,}{5}{=}{6}{,}{6}{=}{9}{,}{7}{=}{8}{,}{8}{=}{10}{,}{9}{=}{5}{,}{10}{=}{4}\right]$ (16)

Apply permutation to permuted graph to obtain original Petersen graph and compare adjacency matrices

 > $\mathrm{P2}≔\mathrm{IsomorphicCopy}\left(\mathrm{P2},\mathrm{map}\left(\mathrm{rhs},\mathrm{mp}\right)\right)$
 ${\mathrm{P2}}{≔}{\mathrm{Graph 9: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (17)
 > $\mathrm{A1}≔\mathrm{AdjacencyMatrix}\left(\mathrm{P1}\right)$
 $\left[\begin{array}{rrrrrrrrrr}0& 1& 0& 0& 1& 1& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 1& 0& 0& 0& 0& 1\\ 1& 0& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 1& 0& 0& 1& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 0& 0& 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 0& 1& 0& 0& 1& 0\end{array}\right]$ (18)
 > $\mathrm{A2}≔\mathrm{AdjacencyMatrix}\left(\mathrm{P2}\right)$
 $\left[\begin{array}{rrrrrrrrrr}0& 1& 0& 0& 1& 1& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 1& 0& 0& 0& 0& 1\\ 1& 0& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 1& 0& 0& 1& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 0& 0& 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 0& 1& 0& 0& 1& 0\end{array}\right]$ (19)
 > $\mathrm{LinearAlgebra}:-\mathrm{Equal}\left(\mathrm{A1},\mathrm{A2}\right)$
 ${\mathrm{true}}$ (20)
 > 

Compatibility

 • The GraphTheory[IsIsomorphic] command was updated in Maple 18.
 • The G1 and G2 parameters were updated in Maple 18.