GATE CSE 2014 Set 1 | GATE CSE Year Wise Previous Years Questions

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 2014 Set 1

MCQ (Single Correct Answer)

-0.3

Consider the statement
"Not all that glitters is gold"
Predicate glitters$$(x)$$ is true if $$x$$ glitters and
predicate gold$$(x)$$ is true if $$x$$ is gold.

Which one of the following logical formulae represents the above statement?

$$\forall x:\,glitters\,\left( x \right) \Rightarrow \neg gold\left( x \right)$$

$$\forall x:\,gold\left( x \right) \Rightarrow glitters\left( x \right)$$ v

$$\exists x:\,gold\left( x \right) \wedge \neg glitters\left( x \right)$$

$$\exists x:\,glitters\,\left( x \right) \wedge \neg gold\left( x \right)$$

GATE CSE 2014 Set 1

MCQ (Single Correct Answer)

-0.6

An ordered $$n$$-tuple $$\left( {{d_1},\,\,{d_2},\,....,{d_n}} \right)$$ with $${{d_1} \ge ,\,\,{d_2} \ge .... \ge {d_n}}$$ is called graphic if there exists a simple undirected graph with $$n$$ vertices having degrees $${d_1},{d_2},.....,{d_n}$$ respectively. Which of the following $$6$$- tuples is NOT graphic?

$$(1, 1, 1, 1, 1, 1)$$

$$(2, 2, 2, 2, 2, 2)$$

$$(3, 3, 3, 1, 0, 0)$$

$$(3, 2, 1, 1, 1, 0)$$

GATE CSE 2014 Set 1

Numerical

-0

Consider an undirectional graph $$G$$ where self-loops are not allowed. The vertex set of $$G$$ is $$\left\{ {\left( {i,j} \right):\,1 \le i \le 12,\,1 \le j \le 12} \right\}.$$ There is an edge between $$(a,b)$$ and $$(c,d)$$ if $$\left| {a - c} \right| \le 1$$ and $$\left| {b - d} \right| \le 1$$. The number of edges in this graph is _____.

Your input ____

PREVIOUS NEXT

GATE CSE Papers

2024