Difference between fundamental circuit and fundamental cutset
Answers
Answered by
0
Note that a set of fundamental circuits or cuts is based on the chosen spanning tree. So pick a spanning tree of the given graph, call it TT. The fundamental cycles are those formed by adding edges to TTfrom G∖TG∖T such that a cycle is created.
A fundamental cut consists of E(T)∖eE(T)∖e for a single edge ee in TT. That is, removing an edge from TT is a fundamental cut. The fundamental set of cuts consists of all such fundamental cuts for TT.
Edit: There are 66 vertices in K3,3K3,3, and so a spanning tree has 55 edges. Let's take P6P6, a path on 66 vertices, as our spanning tree. Let the first partition have odd numbered vertices, and the second partition have even numbered vertices. So our path is 1−2−3−4−5−61−2−3−4−5−6. So we can add an edges {1,4},{1,6}{1,4},{1,6} to create cycles. There are two edges we can add for each odd vertex. Thus, there are 66 fundamental cycles in K3,3K3,3.
In K5K5, let's take P5P5 as our spanning tree. Each pair of vertices are adjacent in K5K5. So if our path is 1−2−3−4−51−2−3−4−5, adding any edge from K5K5 will create a cycle. And so there are (52)−4=10−4=6(52)−4=10−4=6 edges in G∖P5G∖P5 to add, and each will create a different cycle. So there are 66fundamental cycles.
A fundamental cut consists of E(T)∖eE(T)∖e for a single edge ee in TT. That is, removing an edge from TT is a fundamental cut. The fundamental set of cuts consists of all such fundamental cuts for TT.
Edit: There are 66 vertices in K3,3K3,3, and so a spanning tree has 55 edges. Let's take P6P6, a path on 66 vertices, as our spanning tree. Let the first partition have odd numbered vertices, and the second partition have even numbered vertices. So our path is 1−2−3−4−5−61−2−3−4−5−6. So we can add an edges {1,4},{1,6}{1,4},{1,6} to create cycles. There are two edges we can add for each odd vertex. Thus, there are 66 fundamental cycles in K3,3K3,3.
In K5K5, let's take P5P5 as our spanning tree. Each pair of vertices are adjacent in K5K5. So if our path is 1−2−3−4−51−2−3−4−5, adding any edge from K5K5 will create a cycle. And so there are (52)−4=10−4=6(52)−4=10−4=6 edges in G∖P5G∖P5 to add, and each will create a different cycle. So there are 66fundamental cycles.
Similar questions