GATE CSE 2014 Set 1 | Graph Theory Question 34 | Discrete Mathematics

GATE CSE 2014 Set 1

MCQ (Single Correct Answer)

-0.3

Let $$G = \left( {V,E} \right)$$ be a directed graph where $$V$$ is the set of vertices and $$E$$ the set of edges. Then which one of the following graphs has the same strongly connected components as $$G$$?

$${G_1} = \left( {V,\,\,{E_1}} \right)\,\,\,$$where $$\,\,{E_1} = \left\{ {\left( {u,v} \right) \notin E} \right\}$$

$${G_2} = \left( {V,\,\,{E_2}} \right)\,\,\,$$ where $$\,\,\,{E_2} = \left\{ {\left( {u,v} \right) \in E} \right\}$$

$${G_3} = \left( {V,\,\,{E_3}} \right)\,\,\,$$ where $$\,\,{E_3} = $$ {$${\left( {u,v} \right)\left| \, \right.}$$ there isa path of length $$ \le 2$$ from $$u$$ to $$v$$ in $$E$$}

$${G_4} = \left( {{V_4},\,\,{E_{}}} \right)\,\,\,$$ where $${{V_4}}$$ is the set of vertices in $$G$$ which are not isolated.

GATE CSE 2013

MCQ (Single Correct Answer)

-0.3

Consider an undirected random$$^ \circ $$ graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?

$$1/8$$

$$1$$

$$7$$

$$8$$

GATE CSE 2013

MCQ (Single Correct Answer)

-0.3

Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

P only

Q only

Both P and Q

Neither P and Q

GATE CSE 2012

MCQ (Single Correct Answer)

-0.3

Let G be a simple undirected planner graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to