GraphTheory - Maple Help

GraphTheory

Maple 17 has significant improvements to several GraphTheory commands, including:

 • TuttePolynomial, ChromaticPolynomial, FlowPolynomial, AcyclicPolynomial and  RankPolynomial
 • IsIsomorphic

 • LaplacianMatrix
 • ReliabilityPolynomial

Improvements to TuttePolynomial, ChromaticPolynomial, FlowPolynomial, AcyclicPolynomial and RankPolynomial commands

The TuttePolynomial command uses a new algorithm that is faster and consumes less memory.

For example, computation of the Tutte polynomial of the 12 vertex complete graph (CompleteGraph(12)) now requires 1/3 the memory, and completes in 1/3 the time.

For the 9,3 generalized Petersen graph (PetersenGraph(9,3)) the memory usage has dropped to 1/6, and the time to 1/8 of the time needed in Maple 16.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $G:=\mathrm{CompleteGraph}\left(12\right):$
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{TuttePolynomial}\left(G,'x','y'\right)\right):$
 memory used=106.98MiB, alloc change=0 bytes, cpu time=2.67s, real time=2.83s
 > $G:=\mathrm{GeneralizedPetersenGraph}\left(9,3\right):$
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{TuttePolynomial}\left(G,'x','y'\right)\right):$
 memory used=3.21MiB, alloc change=0 bytes, cpu time=125.00ms, real time=149.00ms

These improvements propagate to the commands ChromaticPolynomial, FlowPolynomial, AcyclicPolynomial and RankPolynomial as well.

Improvements to IsIsomorphic command

The IsIsomorphic command now utilizes a new algorithm that scales better to larger problems. As an example, two isomorphic soccer ball graphs (SpecialGraphs[SoccerBallGraph]) with 60 vertices and 90 edges can be tested for isomorphism in less than one second in Maple 17, while in Maple 16 and earlier, this same computation did not complete in under 10 minutes.

 > $S:=\mathrm{SoccerBallGraph}\left(\right):$
 > $G:=\mathrm{IsomorphicCopy}\left(S\right):$
 > $H:=\mathrm{IsomorphicCopy}\left(S\right):$
 > $\mathrm{CodeTools}:-\mathrm{Usage}\left(\mathrm{IsIsomorphic}\left(G,H,'\mathrm{φ}'\right)\right):$
 memory used=448.29KiB, alloc change=0 bytes, cpu time=47.00ms, real time=50.00ms



The LaplacianMatrix command

The new LaplacianMatrix command can be used to compute the Laplacian matrix representation of a graph:

 > $G:=\mathrm{CompleteGraph}\left(5\right):$
 > $\mathrm{LaplacianMatrix}\left(G\right)$
 $\left[\begin{array}{rrrrr}{4}& {-}{1}& {-}{1}& {-}{1}& {-}{1}\\ {-}{1}& {4}& {-}{1}& {-}{1}& {-}{1}\\ {-}{1}& {-}{1}& {4}& {-}{1}& {-}{1}\\ {-}{1}& {-}{1}& {-}{1}& {4}& {-}{1}\\ {-}{1}& {-}{1}& {-}{1}& {-}{1}& {4}\end{array}\right]$ (3.1)



The ReliabilityPolynomial command

The new ReliabilityPolynomial command can be used to compute the reliability polynomial of a graph:

 > $\mathrm{ReliabilityPolynomial}\left(G,'x'\right)$


 $\left({24}{}{{x}}^{{6}}{+}{36}{}{{x}}^{{5}}{+}{30}{}{{x}}^{{4}}{+}{20}{}{{x}}^{{3}}{+}{10}{}{{x}}^{{2}}{+}{4}{}{x}{+}{1}\right){}{\left({1}{-}{x}\right)}^{{4}}$ (4.1)