CycleBasis - Maple Help

GraphTheory

 CycleBasis
 compute cycle basis for graph

 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

 > $\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)

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

 > $\mathrm{AsTrails}≔\mathrm{map}\left(\mathrm{cyc}↦\left[\mathrm{op}\left(\mathrm{cyc}\right),\mathrm{cyc}\left[1\right]\right],\mathrm{Cycles}\right):$
 > $M≔\mathrm{Matrix}\left(2,3,\mathrm{map2}\left(\mathrm{DrawGraph}@\mathrm{HighlightTrail},G,\mathrm{AsTrails},\mathrm{red},\mathrm{inplace}=\mathrm{false}\right)\right):$
 > $M\left[2,3\right]≔\mathrm{plot}\left(\mathrm{axes}=\mathrm{none}\right):$
 > $\mathrm{plots}:-\mathrm{display}\left(M\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)
 >