updates/Maple17/GraphTheory - Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : updates/Maple17/GraphTheory

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

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:

CodeTools:-UsageTuttePolynomialG,'x','y':

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:=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 LaplacianMatrix command

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

 

G:=CompleteGraph5:

LaplacianMatrixG

4111114111114111114111114

(3.1)

The ReliabilityPolynomial command

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

 

ReliabilityPolynomialG,'x'

24x6+36x5+30x4+20x3+10x2+4x+11x4

(4.1)

See Also

GraphTheory, GraphTheory[LaplacianMatrix], GraphTheory[ReliabiltyPolynomial]


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam