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 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

Cycles:=0,1,2,0,1,5,0,2,3,0,3,4,0,4,5

(1)

map2DrawGraph@HighlightVertex,G,Cycles,red,inplace=false

,,,,

Calculate the cycle basis of the octahedron graph.

GOctahedronGraph:

DrawGraphG

CyclesCycleBasisG

Cycles:=1,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

 

 


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