GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

CycleBasis

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

CycleBasis(G)

Parameters

G

-

graph

Description

• 

CycleBasis returns a list of cycles in the graph, with each cycle represented as a list of vertices.  These cycles form a basis for the cycle space of G, so that every other cycle in G can be obtained from the cycle basis using only symmetric differences. (The symmetric difference is applied to cycles as sets of edges.)

• 

The elements of the basis are also known as fundamental cycles.

• 

The number of elements in the cycle basis (i.e., the dimension of the cycle space) is called the cyclomatic number of G.

• 

The algorithm starts from a spanning tree of G and computes fundamental cycles for each graph obtained by adding one of the remaining edges of G to the spanning tree.

Examples

withGraphTheory:

withSpecialGraphs:

Calculate and show the cycle basis of a wheel graph.

GWheelGraph5:

CyclesCycleBasisG

Cycles0,1,2,0,1,5,0,2,3,0,3,4,0,4,5

(1)

Draw the graph with one of the basis cycle highlighted in each:

AsTrailsmapcycopcyc,cyc1,Cycles:

MMatrix2,3,map2`@`DrawGraph,HighlightTrail,G,AsTrails,red,inplace=false:

M2,3plotaxes=none:

plots:-displayM

Calculate the cycle basis of the octahedron graph.

GOctahedronGraph:

DrawGraphG

CyclesCycleBasisG

Cycles1,3,2,4,1,3,2,5,1,3,2,6,1,3,5,1,3,6,1,4,5,1,4,6

(2)

numelemsCycles

7

(3)

See Also

FundamentalCycle

IsAcyclic

SpanningTree