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:
“It’s important to remember that children who are facing a frightening situation have three fundamental concerns: Am I safe? Are you, the people who care for me, safe? How will this affect my daily life?”
—Lawrence Kutner (20th century)
“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)