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

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

Previous Next

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Digital Logic

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages

Computer Organization