GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

GraphNormal

  

finds the normal form of a graph

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

GraphNormal(G)

GraphNormal(M)

GraphNormal(M,ws)

Parameters

G

-

undirected unweighted graph

M

-

adjacency matrix for undirected unweighted graph

ws

-

working storage

Description

• 

The GraphNormal command computes a normal form for an undirected, unweighted graph. The normal form chosen is defined as the permutation that puts the greatest number of 1's in the earliest location in the adjacency matrix, when examining the entries in the order M[1,2], ..., M[1,n], M[2,3], ..., M[2,n], M[3,4], ....

• 

This problem is exponential in the number of vertices, so can only be expected to return in reasonable time for graphs with a small to moderate number of vertices.

• 

The form of the return is different for the three possible calling sequences:

  

For the first calling sequence, when the input is a graph, GraphNormal returns the permuted normal form graph.

  

For the second calling sequence, when the input is an adjacency matrix, GraphNormal returns a permutation in the form [1=n[1], 2=n[2], ...] that maps the original vertices to the normal form vertices.

  

For the third calling sequence, the working storage ws must be rectangular with wordsize integer datatype and of size nn+3 when n is the number of vertices in the graph, and the permutation [n[1],n[2],...] is stored in the first n elements of the workspace on return.

• 

Note that if the adjacency matrix is rectangular storage with wordsize integer datatype, then it is modified in-place to the adjacency matrix of the normal form. If the working storage is also specified, then the implementation will allocate no memory, and the validation that the input adjacency matrix is symmetric is skipped, so this is the most efficient calling sequence. If in this case the input adjacency matrix is not symmetric, the result is not defined.

Examples

withGraphTheory:

Start with the Petersen graph.

PSpecialGraphsPetersenGraph

PGraph 1: an undirected unweighted graph with 10 vertices and 15 edge(s)

(1)

Obtain normalization.

PnGraphNormalP

PnGraph 2: an undirected unweighted graph with 10 vertices and 15 edge(s)

(2)

Compare adjacency matrices.

AnAdjacencyMatrixPn:

AdjacencyMatrixP,An

0100110000101000001001010010000010100001100100010010000010010010010100000010101001000001010001010010,0111000000100011000010000011001000000011010000101001000001010010100001001001001000011001000001011000

(3)

Create a randomized isomorphic copy, and verify that normalizations are equal.

P2IsomorphicCopyP:

AdjacencyMatrixP2

0000011010001101000001000011000100100010000100100111000000011010100000001000001110010001000000110100

(4)

LinearAlgebra:-EqualAn,AdjacencyMatrixGraphNormalP2

true

(5)

Create another randomized isomorphic copy, and verify that normalizations are equal.

P3IsomorphicCopyP:

AdjacencyMatrixP3

0100110000100000001100000101100000101010100100010010100010000001010001001010000101110000000100001100

(6)

LinearAlgebra:-EqualAn,AdjacencyMatrixGraphNormalP3

true

(7)

See Also

AdjacencyMatrix

IsomorphicCopy