GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

IsIsomorphic

  

determine if two graphs are isomorphic

 

Calling Sequence

Parameters

Description

Examples

Compatibility

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

withGraphTheory:

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

G1GraphTrail1,2,3,4,5,6,1,3

G1Graph 1: an undirected unweighted graph with 6 vertices and 7 edge(s)

(1)

G2GraphTrail1,2,3,4,5,6,1,4

G2Graph 2: an undirected unweighted graph with 6 vertices and 7 edge(s)

(2)

G3GraphTrail1,2,3,4,5,6,1,5

G3Graph 3: an undirected unweighted graph with 6 vertices and 7 edge(s)

(3)

DrawGraphG1,G2,G3,width=3,style=circle

IsIsomorphicG1,G2

false

(4)

IsIsomorphicG1,G3,φ

true

(5)

φ

1=1,2=6,3=5,4=4,5=3,6=2

(6)

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

D1Graphdirected,Trail1,2,3,1,4,5

D1Graph 4: a directed unweighted graph with 5 vertices and 5 arc(s)

(7)

D2Graphdirected,Trail1,2,3,4,5,3

D2Graph 5: a directed unweighted graph with 5 vertices and 5 arc(s)

(8)

D3Graphdirected,Trail3,4,5,3,1,2

D3Graph 6: a directed unweighted graph with 5 vertices and 5 arc(s)

(9)

DrawGraphD1,D2,D3,width=3,style=circle

IsIsomorphicD1,D2

false

(10)

IsIsomorphicD1,D3,φ

true

(11)

φ

1=3,2=4,3=5,4=1,5=2

(12)

Create isomorphic permutation of Petersen graph, and check

P1SpecialGraphsPetersenGraph

P1Graph 7: an undirected unweighted graph with 10 vertices and 15 edge(s)

(13)

P2IsomorphicCopyP1

P2Graph 8: an undirected unweighted graph with 10 vertices and 15 edge(s)

(14)

IsIsomorphicP1,P2,mp

true

(15)

mp

1=1,2=7,3=3,4=2,5=6,6=9,7=8,8=10,9=5,10=4

(16)

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

P2IsomorphicCopyP2,maprhs,mp

P2Graph 9: an undirected unweighted graph with 10 vertices and 15 edge(s)

(17)

A1AdjacencyMatrixP1

0100110000101000001001010010000010100001100100010010000010010010010100000010101001000001010001010010

(18)

A2AdjacencyMatrixP2

0100110000101000001001010010000010100001100100010010000010010010010100000010101001000001010001010010

(19)

LinearAlgebra:-EqualA1,A2

true

(20)

Compatibility

• 

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

• 

The G1 and G2 parameters were updated in Maple 18.

See Also

AdjacencyMatrix

IsomorphicCopy