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 $n\left(n+3\right)$ 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.

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

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

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

$\mathrm{Pn}≔\mathrm{GraphNormal}\left(P\right)$

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

$\mathrm{An}≔\mathrm{AdjacencyMatrix}\left(\mathrm{Pn}\right)\:$

$\mathrm{AdjacencyMatrix}\left(P\right),\mathrm{An}$

$\left[\begin{array}{cccccccccc}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],\left[\begin{array}{cccccccccc}0& 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 1& 1\\ 0& 1& 0& 0& 0& 0& 1& 0& 1& 0\\ 0& 1& 0& 0& 0& 0& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 1& 0& 0& 1& 0\\ 0& 0& 0& 1& 1& 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 1& 1& 0& 0& 0\end{array}\right]$

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

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

$\left[\begin{array}{cccccccccc}0& 0& 0& 0& 0& 1& 1& 0& 1& 0\\ 0& 0& 1& 1& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 1& 0& 0& 1\\ 1& 1& 0& 0& 0& 0& 0& 0& 0& 1\\ 1& 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 1& 1\\ 1& 0& 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 1& 0& 0\end{array}\right]$

$\mathrm{LinearAlgebra}:-\mathrm{Equal}\left(\mathrm{An}\,\mathrm{AdjacencyMatrix}\left(\mathrm{GraphNormal}\left(\mathrm{P2}\right)\right)\right)$

$\mathrm{true}$

$\mathrm{P3}≔\mathrm{IsomorphicCopy}\left(P\right)\:$

$\mathrm{AdjacencyMatrix}\left(\mathrm{P3}\right)$

$\left[\begin{array}{cccccccccc}0& 1& 0& 0& 1& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 1& 0& 0& 0& 1\\ 0& 0& 1& 0& 1& 0& 0& 0& 0& 1\\ 0& 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 1& 0& 0\end{array}\right]$

$\mathrm{LinearAlgebra}:-\mathrm{Equal}\left(\mathrm{An}\,\mathrm{AdjacencyMatrix}\left(\mathrm{GraphNormal}\left(\mathrm{P3}\right)\right)\right)$

$\mathrm{true}$