1
GATE CSE 1999
Subjective
+5
-0
Let $$G$$ be a connected, undirected graph. A $$cut$$ in $$G$$ is a set of edges whose removal results in $$G$$ being broken into two or more components which are not connected with each other. The size of a cut is called its $$cardinality$$. A $$min-cut$$ of $$G$$ is a cut in $$G$$ of minimum cardinality. Consider the following graph.

(a) Which of the following sets of edges is a cut?
$$\,\,\,\,$$(i)$$\,\,\,\,\left\{ {\left( {A,\,B} \right),\left( {E,\,F} \right),\left( {B,\,D} \right),\left( {A,\,E} \right),\left( {A,\,D} \right)} \right\}$$
$$\,\,\,\,$$(ii)$$\,\,\,\,\left\{ {\left( {B,\,D} \right),\left( {C,\,F} \right),\left( {A,\,B} \right)} \right\}$$

(b) What is the cardinality of a min-cut in this graph?

(c) Prove that if a connected undirected graph $$G$$ with $$n$$ vertices has a min-cut of cardinality $$k$$, then $$G$$ has at least $$(nk/2)$$ edges.

2
GATE CSE 1995
Subjective
+5
-0
How many minimum spanning tress does the following graph have? Draw them (Weights are assigned to the edges).
GATE CSE Subjects
EXAM MAP
Medical
NEET