Recent questions in Discrete Mathematics / GATE Overflow for GATE CSE

3 votes

3 answers

4901

TIFR CSE 2016 | Part A | Question: 14
A $diagonal$ in a polygon is a straight line segment that connects two non-adjacent vertices, and is contained in the interior of the polygon (except for its points). Two such diagonals are said to cross if they have a point in common in the interior of the polygon. In one such ... the information given $\frac{n}{2}-2$ $\frac{n}{4}-1$ $n-4$ $n^2 - 9.5 n +22$

A $diagonal$ in a polygon is a straight line segment that connects two non-adjacent vertices, and is contained in the interior of the polygon (except for its points). Two...

go_editor

866 views

go_editor asked Dec 28, 2016

4 votes

3 answers

4902

TIFR CSE 2016 | Part A | Question: 13
Let $n \geq 2$ be any integer. Which of the following statements is not necessarily true? $\begin{pmatrix} n \\ i \end{pmatrix} = \begin{pmatrix} n-1 \\ i \end{pmatrix} + \begin{pmatrix} n-1 \\ i-1 \end{pmatrix}, \text{ where } 1 \leq i \leq n-1$ $n!$ divides the ... $ i \in \{1, 2, \dots , n-1\}$ If $n$ is an odd prime, then $n$ divides $2^{n-1} -1$

Let $n \geq 2$ be any integer. Which of the following statements is not necessarily true?$\begin{pmatrix} n \\ i \end{pmatrix} = \begin{pmatrix} n-1 \\ i \end{pmatrix} + ...

go_editor

1.1k views

go_editor asked Dec 28, 2016

0 votes

0 answers

4903

Give an approach !!

thor

204 views

thor asked Dec 28, 2016

0 votes

0 answers

4904

madeeasy
An entrepreneur needs to assign 5 different tasks to three of his employees. If every employee is assigned at least 1 task, how many ways can the entrepreneur assign those tasks to his employees? Doubt: Can this question reduce to distributing labelled objects ... boxes are empty. My view: The three employees are different from each other and hence should be treated as labelled boxes.

An entrepreneur needs to assign 5 different tasks to three of his employees. If every employee is assigned at least 1 task, how many ways can the entrepreneur assign thos...

Akhilesh Yadav 1

250 views

Akhilesh Yadav 1 asked Dec 28, 2016

0 votes

0 answers

4905

Kenneth Rosen Edition 6th Exercise 8.3 Question 53 (Page No. 555)
The complementary graph G' of a simple graph G has the same vertices as G. Two vertices are adjacent in G' if and only if they are not adjacent in G. Define Qn' (Hypercube complement). Answer given :-The ... are differing by 0 bit,as these are also not there in original graph ,so it must be in complementary graph?

The complementary graph G' of a simple graph G has the same vertices as G. Two vertices are adjacent in G' if and only if they are not adjacent in G. Define Qn' (Hyperc...

rahul sharma 5

533 views

rahul sharma 5 asked Dec 27, 2016

0 votes

1 answer

4906

Test series Testbook
Is this a distributive lattice????

Is this a distributive lattice????

bad_engineer

423 views

bad_engineer asked Dec 27, 2016

20 votes

5 answers

4907

TIFR CSE 2016 | Part A | Question: 8
Let $A$ and $B$ be finite sets such that $A \subseteq B$. Then, what is the value of the expression: $ \sum \limits_{C:A \subseteq C \subseteq B} (-1)^{\mid C \setminus A \mid,}$ Where $C \setminus A=\{x \in C : x \notin A \}$? Always $0$ Always $1$ $0$ if $A=B$ and $1$ otherwise $1$ if $A=B$ and $0$ otherwise Depends on the size of the universe

Let $A$ and $B$ be finite sets such that $A \subseteq B$. Then, what is the value of the expression:$$ \sum \limits_{C:A \subseteq C \subseteq B} (-1)^{\mid C \setminus A...

go_editor

2.7k views

go_editor asked Dec 27, 2016

5 votes

1 answer

4908

TIFR CSE 2016 | Part A | Question: 7
Let $S$ be the $4 \times 4$ square grid $\{(x, y): x, y \in \{0, 1, 2, 3\} \}$. A $monotone \: \: path$ in this grid starts at $(0, 0)$ and at each step either moves one unit up or one unit right. For example, from the point $(x, y)$ one ... many distinct monotone paths are there to reach point $(3, 3)$ starting from $(0, 0)$? $2z+6$ $3z+6$ $2z+8$ $3z+8$ $3z+4$

Let $S$ be the $4 \times 4$ square grid $\{(x, y): x, y \in \{0, 1, 2, 3\} \}$. A $monotone \: \: path$ in this grid starts at $(0, 0)$ and at each step either moves one ...

go_editor

748 views

go_editor asked Dec 27, 2016

2 votes

1 answer

4909

planar region
How many planar regions? How many closed regions? and how many are unbounded? How many of then are bounded by a cycle of length $4$ ? Now, for example (a different question, not related to above diagram ) a question says, In a connected 3 regular graph, ... region is bounded by exactly 5 edges, then count no of edges? Please explain the last QS with the help of Euler's equation.

How many planar regions?How many closed regions? and how many are unbounded?How many of then are bounded by a cycle of length $4$ ?Now, for example (a different question,...

dd

2.6k views

dd asked Dec 26, 2016

8 votes

5 answers

4910

TIFR CSE 2016 | Part A | Question: 2
Consider the graph shown below: The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set of $9$ possibilities. Next, a common neighbour $k$ of $i$ and $j$ is chosen, again uniformly from the set of ... $\frac{1}{6}$ $\frac{1}{4}$ $\frac{1}{3}$ $\frac{2}{3}$ $\frac{5}{6}$

Consider the graph shown below:The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set...

go_editor

1.1k views

go_editor asked Dec 26, 2016

0 votes

1 answer

4911

Math Probability
Consider the random variable X such that it takes values +1,-1 and +2 with probability 0.1 each .Calculate values of the commulative frequencydistribution function F(x) at x=-1 and x=1 and x=2 are ?

Consider the random variable X such that it takes values +1,-1 and +2 with probability 0.1 each .Calculate values of the commulative frequencydistribution function F(x) a...

Çșȇ ʛấẗẻ

291 views

Çșȇ ʛấẗẻ asked Dec 26, 2016

2 votes

1 answer

4912

connectivity
Consider a simple connected undirected graph G which has m vertices and n edges. Which of the following condition always guarantee that after removal of those number of edges graph will be disconnected? a)m – n + 2 b)$_{2}^{m}\textrm{C}-n+2$ c)n – 2 d)None of the above

Consider a simple connected undirected graph G which has m vertices and n edges. Which of the following condition always guarantee that after removal of those number of e...

Sanket_

1.9k views

Sanket_ asked Dec 26, 2016

0 votes

1 answer

4913

ACE-MockTest:-Countable Set

KISHALAY DAS

671 views

KISHALAY DAS asked Dec 24, 2016

0 votes

0 answers

4914

E = 2N -3
I read in https://gateoverflow.in/28955/given-vertex-edges-how-find-non-isomorphic-graphs-possible question explanantion,it was written that e=2n-3 where e= number of edges and n is no of vertices. how is it derived??can anyone tell me the source??

I read in https://gateoverflow.in/28955/given-vertex-edges-how-find-non-isomorphic-graphs-possible question explanantion,it was written that e=2n-3 where e= number of edg...

Akriti sood

158 views

Akriti sood asked Dec 24, 2016

2 votes

1 answer

4915

maths

psb

1.1k views

psb asked Dec 24, 2016

17 votes

2 answers

4916

TIFR CSE 2017 | Part B | Question: 13
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if the corresponding edges in $G$ are ... vertex in the line graph is at most the maximum degree in the original graph each vertex in the line graph has degree one or two

For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if...

go_editor

2.9k views

go_editor asked Dec 23, 2016

54 votes

7 answers

4917

TIFR CSE 2017 | Part B | Question: 12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n-1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$

An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a d...

go_editor

6.6k views

go_editor asked Dec 23, 2016

32 votes

3 answers

4918

TIFR CSE 2017 | Part B | Question: 11
Given that $B(x)$ means "$x$ is a bat", $F(x)$ means "$x$ is a fly", and $E(x, y)$ means "$x$ eats $y$", what is the best English translation of $ \forall x(F(x) \rightarrow \forall y (E(y, x) \rightarrow B(y)))?$ all flies eat bats every fly is eaten by some bat bats eat only flies every bat eats flies only bats eat flies

Given that$B(x)$ means "$x$ is a bat",$F(x)$ means "$x$ is a fly", and$E(x, y)$ means "$x$ eats $y$",what is the best English translation of $$ \forall x(F(x) \rightarrow...

go_editor

3.7k views

go_editor asked Dec 23, 2016

23 votes

2 answers

4919

TIFR CSE 2017 | Part B | Question: 10
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements: If every vertex in $G$ has ... the above statements is/are TRUE? Choose from the following options: only i only i and ii only i and iii only ii and iii i, ii, and iii

A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider ...

go_editor

2.8k views

go_editor asked Dec 23, 2016

8 votes

1 answer

4920

TIFR CSE 2017 | Part B | Question: 6
Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE? Partial orders cannot be axiomatized in FOL FOL has a complete proof system Natural numbers cannot be axiomatized in FOL Real numbers cannot be axiomatized in FOL Relational numbers cannot be axiomatized in FOL

Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE?Partial orders cannot be axiomatized in FOL...

go_editor

1.2k views

go_editor asked Dec 23, 2016

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true