edited by
6,336 views
33 votes
33 votes

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:

  1. Which of the following sets of edges is a cut?

    1. $\left\{(A, B), (E, F), (B, D), (A, E), (A, D)\right\}$
    2. $\left\{(B, D), (C, F), (A, B)\right\}$
  2. What is cardinality of min-cut in this graph?
  3. Prove that if a connected undirected graph $G$ with $n$ vertices has a min-cut of cardinality $k$, then $G$ has at least $\left(\frac{n\times k}{2}\right)$ edges.
edited by

5 Answers

–4 votes
–4 votes
(a) (i) Not a cut. (ii) It is a cut.

(b) 3. {(B,D),(C,F),(A,B)} and {(A,E),(D,E),(E,F)} and {(B,D),(B,C),(A,B)}. Cardinality of each cut set is 3.

Related questions

39 votes
39 votes
5 answers
1
Kathleen asked Sep 23, 2014
8,736 views
The number of articulation points of the following graph is$0$$1$$2$$3$
13 votes
13 votes
3 answers
2
Kathleen asked Sep 23, 2014
2,349 views
Show that the formula $\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right]$ is not a tautology.Let $A$ be a tautology and $B$ any other formula. Prove that $(A \ve...
34 votes
34 votes
2 answers
3
Kathleen asked Sep 23, 2014
5,008 views
Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.