FindFundamentalCycles

FindFundamentalCycles[g]
finds fundamental cycles of the graph g.

Details and OptionsDetails and Options

  • FindFundamentalCycles is also known as cycle basis.
  • FindFundamentalCycles returns a list of cycles consisting of fundamental cycles .
  • For an undirected graph g with a spanning tree s, fundamental cycles are cycles that contain exactly one non-tree edge each.
  • Cycles can be combined into new cycles by adding their edges modulo two, i.e. if the same edge is covered an odd number of times it is kept and otherwise discarded.

Background
Background

  • FindFundamentalCycles returns a list of fundamental cycles of a graph. Here, fundamental cycles are a set of cycles that form a fundamental cycle basis, which is a set of cycles that can generate every cycle in a graph by a linear combination of members based on a spanning tree. The cycles are returned as a list of edge lists. A cycle basis is useful in the study of chemical graphs, for generating a large cycle family, and for computation of voltage or current in a circuit.
  • FindFundamentalCycles uses the result of FindSpanningTree as the default spanning tree.
  • A list of all cycles of a graph (not just the fundamental ones) may be returned using FindCycle. FindHamiltonianCycle and FindEulerianCycle return other specific types of graph cycles. EdgeCycleMatrix is a related function that can be used to return an edge cycle matrix of a graph.
Introduced in 2014
(10.0)