GraphTheory
Maple 17 has significant improvements to several GraphTheory commands, including:
TuttePolynomial, ChromaticPolynomial, FlowPolynomial, AcyclicPolynomial and RankPolynomial
IsIsomorphic
In addition, two new commands were added to the package:
LaplacianMatrix
ReliabilityPolynomial
Improvements to TuttePolynomial, ChromaticPolynomial, FlowPolynomial, AcyclicPolynomial and RankPolynomial commands
Improvements to IsIsomorphic command
The LaplacianMatrix command
The ReliabilityPolynomial command
See Also
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.
withGraphTheory:
withSpecialGraphs:
G:=CompleteGraph12:
CodeTools:-UsageTuttePolynomialG,'x','y':
memory used=106.98MiB, alloc change=0 bytes, cpu time=2.67s, real time=2.83s
G:=GeneralizedPetersenGraph9,3:
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.
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:=SoccerBallGraph:
G:=IsomorphicCopyS:
H:=IsomorphicCopyS:
CodeTools:-UsageIsIsomorphicG,H,'φ':
memory used=448.29KiB, alloc change=0 bytes, cpu time=47.00ms, real time=50.00ms
The new LaplacianMatrix command can be used to compute the Laplacian matrix representation of a graph:
G:=CompleteGraph5:
LaplacianMatrixG
The new ReliabilityPolynomial command can be used to compute the reliability polynomial of a graph:
ReliabilityPolynomialG,'x'
24x6+36x5+30x4+20x3+10x2+4x+11−x4
GraphTheory, GraphTheory[LaplacianMatrix], GraphTheory[ReliabiltyPolynomial]
Download Help Document
