TOPICS
Search

Fundamental Cycle


If T is a spanning tree of a connected, finite, undiected graph G, then the fundamental cycle-set of G corresponding to T is the set of cycles (u,v,...,u) of G, each consisting of one edge (u,v) of G-T together with the unique path (v,...,u) in T (Paton 1969).

FundamentalCycles

There are exactly

 nu=m-n+c

fundamental cycles in a graph, namely one for each edge that does not belong to the spanning tree. Here, nu is the circuit rank, m is the edge count, n the vertex count, and c the number of connected components. A set of 13=24-12+1 fundamental cycles are illustrated above for the cuboctahedral graph, together with the graph itself and the spanning tree used to construct the basis.

Any cycle of a graph can be expressed as a sum modulo 2 over a fundamental cycle set of the graph (Gould 1959, Paton 1969).

The Wolfram Language function FindFundamentalCycles[g] can be used to find a set of fundamental cycles of a graph g.


See also

Circuit Rank, Graph Cycle

Explore with Wolfram|Alpha

References

Gotlieb, C. C. and nd Corneil, D. G. "Algorithms for Finding a Fundamental Set of Cycles for an Undirected Linear Graph." Comm. ACM 10, 780-783, 1967.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 192-193, 2006.Gould, R. "The Application of Graph Theory to the Synthesis of Contact Networks." Proc. International Symp. on the Theory of Switching, Pt. I, Apr. 2-5, 1957. In The Annals of the Computation Laboratory of Harvard University, Annals No. 29. Cambridge, MA: Harvard University Press, pp. 244-292, 1959.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 37-38, 1994.Paton, K. "An Algorithm for Finding Fundamental Cycles of a Graph." Comm. ACM 12, 514-518, 1969.Sch, P. "Enumerating All Cycles in an Undirected Graph." 9 Sep 2018. https://www.codeproject.com/Articles/1158232/Enumerating-All-Cycles-in-an-Undirected-Graph.Welch, J. T. Jr. "A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs." J. ACM 18, 2, 205-210, 1966.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 374, 2000.

Cite this as:

Weisstein, Eric W. "Fundamental Cycle." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FundamentalCycle.html

Subject classifications