Fundamental Cycles
Adding just one edge to a spanning tree will create a cycle; such a cycle is called a fundamental cycle. There is a distinct fundamental cycle for each edge; thus, there is a one-to-one correspondence between fundamental cycles and edges not in the spanning tree. For a connected graph with V vertices, any spanning tree will have V-1 edges, and thus, a graph of E edges will have E-V+1 fundamental cycles. For any given spanning tree these cycles form a basis for the cycle space.
Dual to the notion of a fundamental cycle is the notion of a fundamental cutset. By deleting just one edge of the spanning tree, the vertices are partitioned into two disjoint sets. The fundamental cutset is defined as the set of edges that must be removed from the graph G to accomplish the same partition. Thus, there are precisely V-1 fundamental cutsets for the graph, one for each edge of the spanning tree.
The duality between fundamental cutsets and fundamental cycles is established by noting that cycle edges not in the spanning tree can only appear in the cutsets of the other edges in the cycle; and vice versa: edges in a cutset can only appear in those cycles containing the edge corresponding to the cutset.
Read more about this topic: Spanning Tree
Famous quotes containing the words fundamental and/or cycles:
“When we walk the streets at night in safety, it does not strike us that this might be otherwise. This habit of feeling safe has become second nature, and we do not reflect on just how this is due solely to the working of special institutions. Commonplace thinking often has the impression that force holds the state together, but in fact its only bond is the fundamental sense of order which everybody possesses.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“The stars which shone over Babylon and the stable in Bethlehem still shine as brightly over the Empire State Building and your front yard today. They perform their cycles with the same mathematical precision, and they will continue to affect each thing on earth, including man, as long as the earth exists.”
—Linda Goodman (b. 1929)