DISCRETE MATHEMATICS
JEMSHEENA P S
ASSISTANT PROFESSOR
Module IV
TREES
(Part 2)
Cut-Set
In a connected graph G, a set of edges whose removal
from the graph leaves the graph disconnected, provided
removal of no proper subsets of these edges disconnets G.
is called a cut-set of the graph
In the graph in Figure : 4 the set of edges {a, c, d, f} is a
cut set of the graph.
Fundamental Circuit
Let T be a spanning tree in a connected graph G. When a chord
is added to a spanning tree T then it forms exactly one circuit.
Such a circuit is called a fundamental circuit with respect to the
spanning tree.
Fundamental cut-set
Let T be a spanning tree of a connected graph G. Then a cutset
formed by exactly one branch, say b, of T and possibly some
more chords of T is called a Fundamental cut-set of G relative to
the spanning tree T.
In the figure : 6 {d, e, f} is a fundamental cut-set with e as one of
the branch of a tree (thick lines) and remaining edges d and f as
chords of the corresponding tree.
Connectivity and Separativity
To measure the connectedness of a graph G .
Here we consider the minimum number of vertices and edges to be
removed from the graph inorder to disconnect it.
Connectivity defines whether a graph is connected or disconnected
A graph is said to be connected if there is a path between every pair of
vertex.
ie From every vertex to anyother vertex ,there should be some path to
traverse Then it is called connectivity of a graph
A graph with multiple disconnected vertices and edges is said to be
disconnected
Edge connectivity and Vertex connectivity
Edge Connectivity (λ(G))
The Edge Connectivity of a connected graph G is the number
of edges in the smallest cut-set of G.
.
Vertex Connectivity (K(G))
The Vertex Connectivity of a connected graph G is the smallest
number of vertices whose removal from the graph leaves the
graph G disconnected
Define k-connected graph
A connected graph G is called a k-connected graph if the ver-
tex connectivity of G is k.
The edge connectivity of the graph in the figure 6 is 2
Here b and c are cut vertices ,then k(G)=2
Separativity
Separable graph
A connected graph G is said to be Seperable if its vertex
connectivity is 1.
The graph in the figure 9 is a seperable graph as its vertex connec-
tivity is 1.
Separativity
In a seperable graph a vertex whose removal from the graph
leaves the graph disconnected is called a Cut-Vertex of the graph.
The vertex V in of the graph in the figure 9 is a cut-vertex.
Theorems
THANK YOU
