GraphTheory - Maple Programming Help

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

GraphTheory

 CycleBasis

 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

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$

Calculate and show the cycle basis of a wheel graph.

 > $G≔\mathrm{WheelGraph}\left(5\right):$
 > $\mathrm{Cycles}≔\mathrm{CycleBasis}\left(G\right)$
 ${\mathrm{Cycles}}{≔}\left[\left[{0}{,}{1}{,}{2}\right]{,}\left[{0}{,}{1}{,}{5}\right]{,}\left[{0}{,}{2}{,}{3}\right]{,}\left[{0}{,}{3}{,}{4}\right]{,}\left[{0}{,}{4}{,}{5}\right]\right]$ (1)
 > $\mathrm{map2}\left(\mathrm{DrawGraph}@\mathrm{HighlightVertex},G,\mathrm{Cycles},\mathrm{red},\mathrm{inplace}=\mathrm{false}\right)$
 $\left[{,}{,}{,}{,}\right]$

Calculate the cycle basis of the octahedron graph.

 > $G≔\mathrm{OctahedronGraph}\left(\right):$
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{Cycles}≔\mathrm{CycleBasis}\left(G\right)$
 ${\mathrm{Cycles}}{≔}\left[\left[{1}{,}{3}{,}{2}{,}{4}\right]{,}\left[{1}{,}{3}{,}{2}{,}{5}\right]{,}\left[{1}{,}{3}{,}{2}{,}{6}\right]{,}\left[{1}{,}{3}{,}{5}\right]{,}\left[{1}{,}{3}{,}{6}\right]{,}\left[{1}{,}{4}{,}{5}\right]{,}\left[{1}{,}{4}{,}{6}\right]\right]$ (2)
 > $\mathrm{numelems}\left(\mathrm{Cycles}\right)$
 ${7}$ (3)