ALL CUTSETS IN A GRAPH
Er. Priyanka Tripathi
Assistant Professor
Department of Computer Science and Engineering
University of Lucknow
Lucknow
4-2. SOME PROPERTIES OF A CUT-SET
Consider a spanning tree T in a connected graph G and an arbitrary
cutset S in G. Is it possible for S not to have any edge in common with T?
The answer is no. Otherwise, removal of the cut-set S from G would not
disconnect the graph. Therefore,
THEOREM 4-1
Every cut-set in a connected graph G must contain at least one branch
of every spanning tree of G.
Will the converse also be true? In other words, will any minimal set of
edges containing at least one branch of every spanning tree be a cut-set?
The answer is yes.
THEOREM 4-2
In a connected graph G, any minimal set of edges containing at least
one branch of every spanning tree of G is a cut-set.
THEOREM 4-3
Every circuit has an even number of edges in common with any cut-set.
4-3. ALL CUTSETS IN A GRAPH
In Section 4-1 it was shown how cutsets are used to identify weak spots
in a communication net. For this purpose we list all cutsets of the
corresponding graph, and find which ones have the smallest number of
edges. It must also have become apparent to you that even in a simple
example, such as in Fig. 4-1, there is a large number of cutsets, and we
must have a systematic method of generating all relevant cutsets.
In the case of circuits, we solved a similar problem by the simple technique
of finding a set of fundamental circuits and then realizing that other circuits
in a graph are just combinations of two or more fundamental circuits. We
shall follow a similar strategy here. Just as a spanning tree is essential for
defining a set of fundamental circuits, so is a spanning tree essential for a
set of fundamental cutsets. It will be beneficial for us to look for the
parallelism between circuits and cutsets.
Fundamental CutSets:
Consider a spanning tree T of a connected graph G. Take any branch
b in T. Since {b} is a cut-set in T, {b} partitions all vertices of T into two
disjoint sets—one at each end of b.
Consider the same partition of vertices in G, and the cut set S in G that
corresponds to this partition. Cutset S will contain only one branch b of T,
and the rest (if any) of the edges in S are chords with respect to T. Such
a cut-set S containing exactly one branch of a tree T is called a
fundamental cut-set with respect to T. Sometimes a fundamental cut-set
is also called a basic cut-set.
In Fig. 4-3, a spanning tree T (in heavy lines) and all five of the
fundamental cutsets with respect to T are shown (broken lines “cutting”
through each cut-set).
Fig. 4-3 Fundamental cutsets of a graph.
Just as every chord of a spanning tree defines a unique fundamental
circuit, every branch of a spanning tree defines a unique fundamental
cut-set. It must also be kept in mind that the term fundamental cut-set
(like the term fundamental circuit) has meaning only with respect to a
given spanning tree.
Now we shall show how other cutsets of a graph can be obtained from
a given set of cutsets.
THEOREM 4-4
The ring sum of any two cutsets in a graph is either a third cut-set or an
edge-disjoint union of cutsets.
Example: In Fig. 4-3 let us consider ring sums of the following three
pairs of cutsets.
Disclaimer: The e-content is exclusively meant for academic purposes and for enhancing teaching
and learning. Any other use for economic/commercial purpose is strictly prohibited. The users of
the content shall not distribute, disseminate or share it with anyone else and its use is restricted to
advancement of individual knowledge. The information provided in this e-content is developed
from authentic references, to the best of my knowledge.
References
Deo, N, Graph theory with applications to Engineering and Computer
Science, PHI.
Gary Chartrand and Ping Zhang, Introduction to Graph Theory, TMH.
Robin J. Wilson, Introduction to Graph Theory, Pearson Education.
