compute cycle basis for graph
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.
Calculate and show the cycle basis of a wheel graph.
G ≔ WheelGraph⁡5:
Cycles ≔ CycleBasis⁡G
Draw the graph with one of the basis cycle highlighted in each:
AsTrails ≔ map⁡cyc→op⁡cyc,cyc1,Cycles:
M ≔ Matrix⁡2,3,map2⁡DrawGraph@HighlightTrail,G,AsTrails,red,inplace=false:
M2,3 ≔ plot⁡axes=none:
Calculate the cycle basis of the octahedron graph.
G ≔ OctahedronGraph⁡:
Download Help Document