(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.
$$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$List-$${\rm I}$$
(a) Thread $$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$(b) Virtual Address space
(c) File System $$\,\,\,\,\,\,\,\,\,\,$$(d) Signal
$$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$List-$${\rm II}$$
(1) Interrupt $$\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$(2) Memory
(3) $$CPU$$ $$\,\,\,\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,\,$$(4) Disk
GATE CSE Papers
All year-wise previous year question papers