Recent questions and answers in Discrete Mathematics - GATE Overflow

0 votes

1 answer

1

UGCNET-Dec2007-II: 2
The number of edges in a complete graph with ‘n’ vertices is equal to : $n(n-1)$ $\large\frac{n(n-1)}{2}$ $n^2$ $2n-1$

answered 3 days ago in Graph Theory by chirudeepnamini Loyal (5.3k points) | 19 views

0 votes

1 answer

2

UGCNET-Dec2006-II: 3
The number of edges in a complete graph with N vertices is equal to: $N (N−1)$ $2N−1$ $N−1$ $N(N−1)/2$

answered 5 days ago in Graph Theory by Sanjay Sharma Boss (49.6k points) | 13 views

0 votes

1 answer

3

UGCNET-Dec2004-II: 4
The following lists are the degrees of all the vertices of a graph : $1,2,3,4,5$ $3,4,5,6,7$ $1, 4, 5, 8, 6$ $3,4,5,6$ (i) and (ii) (iii) and (iv) (iii) and (ii) (ii) and (iv)

answered 5 days ago in Graph Theory by Divya Devi (23 points) | 16 views

+10 votes

5 answers

4

GATE1987-1-xxii
The equation $7x^{7}+14x^{6}+12x^{5}+3x^{4}+12x^{3}+10x^{2}+5x+7=0$ has All complex roots At least one real root Four pairs of imaginary roots None of the above

answered 5 days ago in Set Theory & Algebra by SatyamK (229 points) | 561 views

0 votes

0 answers

5

UGCNET-Dec2006-II: 2
The proposition ~ q ∨ p is equivalent to :

asked 5 days ago in Mathematical Logic by jothee Veteran (107k points) | 21 views

0 votes

1 answer

6

UGCNET-Dec2004-II: 2
If $f (x)=x+1\:\text{and}\:g(x)=x+3$ then $f 0 f 0 f 0 f$ is : $g$ $g+1$ $g^4$ None of these

answered 6 days ago in Set Theory & Algebra by Shobhit Joshi Loyal (5.5k points) | 11 views

0 votes

0 answers

7

UGCNET-Dec2004-II: 23
Weighted graph : Is a bi-directional graph. Is directed graph. Is graph in which number associated with arc. Eliminates table method.

asked 6 days ago in Graph Theory by jothee Veteran (107k points) | 5 views

0 votes

2 answers

8

NIELIT Scientist-B Dec 2017_44
On a set A = {a, b, c, d} a binary operation * is defined as given in the following table. * a b c d a b c d a c b d c b d a b d a c d a c b The relation is : (A) Commutative but not associative (B) Neither commutative nor associative (C) Both commutative and associative (D) Associative but not commutative

answered Mar 19 in Set Theory & Algebra by topper98 Junior (589 points) | 152 views

0 votes

1 answer

9

NIELIT Scientist-B Dec 2017_51
Let $u$ and $v$ be two vectors in R2 whose Euclidean norms satisfy $|u|=2|v|$. What is the value of $\alpha$ such that $w=u+\alpha v$ bisects the angle between $u$ and $v$ ? (A) 2 (B) 1 (C) 1/2 (D) -2

answered Mar 19 in Set Theory & Algebra by topper98 Junior (589 points) | 107 views

0 votes

2 answers

10

NIELIT Scientist-B Dec 2017_24
Using bisection method, one root of X4-X-1 lies between 1 and 2. After second iteration the root may lie in interval : (A) (1.25, 1.5) (B) (1, 1.25) (C) (1, 1.5) (D) None of the options

answered Mar 19 in Set Theory & Algebra by topper98 Junior (589 points) | 205 views

0 votes

2 answers

11

NIELIT July 2017_75
Choose the most appropriate definition of plane graph A) A simple graph which is isomorphic to Hamiltonian graph B) A graph drawn in a plane such away that if the vertex set of graph can be partitioned into two non - empty disjoint subset X and Y in such a way ... A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices D) None of the option

answered Mar 19 in Graph Theory by topper98 Junior (589 points) | 340 views

+3 votes

5 answers

12

NIELIT July 2017_73
For the graph shown, which of the following paths is a Hamilton circuit ? A) ABCDCFDEFAEA B) AEDCBAF C) AEFDCBA D) AFCDEBA

answered Mar 19 in Graph Theory by topper98 Junior (589 points) | 628 views

0 votes

2 answers

13

NIELIT July 2017_72
The following graph has no Euler circuit because A) It has 7 vertices B) It is even-valent (all vertices have even valence) C) It is not connected D) It does not have an Euler circuit

answered Mar 19 in Graph Theory by topper98 Junior (589 points) | 361 views

0 votes

2 answers

14

NIELIT July 2017_71
Consider the following graph L and find the bridges, if any A) No bridge B) {d, e} C) {c, d} D) {c, d} and {c, f}

answered Mar 19 in Graph Theory by topper98 Junior (589 points) | 395 views

+1 vote

1 answer

15

ISI2016-PCB-CS-8
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than 1 in a given tree. What is the maximum possible value of $k$? Justify your answer. Consider $2n$ committees, each having at least $2n$ persons, formed from a group of $4n$ persons. Prove that there exists at least one person who belongs to at least $n$ committees.

answered Mar 18 in Combinatory by Falahamin (21 points) | 46 views

0 votes

1 answer

16

ISI2016-MMA-25
A integer is said to be a $\textbf{palindrome}$ if it reads the same forward or backward. For example, the integer $14541$ is a $5$-digit palindrome and $12345$ is not a palindrome. How many $8$-digit palindromes are prime? $0$ $1$ $11$ $19$

answered Mar 18 in Combinatory by Falahamin (21 points) | 24 views

+3 votes

3 answers

17

GATE2020-CS-45
For $n>2$, let $a \in \{0,1\}^n$ be a non-zero vector. Suppose that $x$ is chosen uniformly at random from $\{0,1\}^n$. Then, the probability that $\displaystyle{} \Sigma_{i=1}^n a_i x_i$ is an odd number is______________

answered Mar 17 in Mathematical Logic by felics moses 1 (119 points) | 1k views

+13 votes

6 answers

18

GATE2019-38
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II

answered Mar 17 in Graph Theory by immanujs Active (3.3k points) | 4.7k views

+4 votes

6 answers

19

GATE2020-CS-42
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is ______.

answered Mar 15 in Combinatory by felics moses 1 (119 points) | 1.5k views

0 votes

1 answer

20

JEST 2020
X AND Y is an arbitrary sets, F: $X\rightarrow Y$ show that a and b are equivalent F is one-one For all set Z and function g1: $Z\rightarrow X$ and g2: $Z\rightarrow X$, if $g1 \neq g2$ implies $f \bigcirc g1 \neq f \bigcirc g2$ Where $\bigcirc$ is a fucntion composition.

answered Mar 12 in Set Theory & Algebra by commenter commenter Active (1.6k points) | 150 views

+20 votes

4 answers

21

GATE1996-1.4
Which of the following statements is FALSE? The set of rational numbers is an abelian group under addition The set of integers in an abelian group under addition The set of rational numbers form an abelian group under multiplication The set of real numbers excluding zero is an abelian group under multiplication

answered Mar 11 in Set Theory & Algebra by vivekgatecs2020 (137 points) | 2.2k views

+1 vote

2 answers

22

ISI2017-MMA-26
Let $n$ be the number of ways in which $5$ men and $7$ women can stand in a queue such that all the women stand consecutively. Let $m$ be the number of ways in which the same $12$ persons can stand in a queue such that exactly $6$ women stand consecutively. Then the value of $\frac{m}{n}$ is $5$ $7$ $\frac{5}{7}$ $\frac{7}{5}$

answered Mar 9 in Combinatory by kraken_wizard (41 points) | 93 views

0 votes

3 answers

23

NIELIT Scientist-B Dec 2017_56
Let G be a simple undirected graph on $n=3x$ vertices ($x>=1$) with chromatic number 3, then maximum number of edges in G is : (A) $n(n-1)/2$ (B) $n^{n-2}$ (C) $nx$ (D) $n$

answered Mar 8 in Graph Theory by vivekgatecs2020 (137 points) | 460 views

+28 votes

3 answers

24

GATE2002-1.4
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$

answered Mar 7 in Graph Theory by vivekgatecs2020 (137 points) | 3.1k views

+33 votes

4 answers

25

GATE2009-3
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.

answered Mar 7 in Graph Theory by vivekgatecs2020 (137 points) | 2.7k views

+2 votes

2 answers

26

Let a relation R be defined on the set of all real numbers by a R b <=> 1 + ab > 0 thus R is ?

answered Mar 3 in Set Theory & Algebra by MKraza (11 points) | 7.4k views

+2 votes

2 answers

27

Zeal Test Series 2019: Graph Theory - Graph Coloring
what is index ?

answered Mar 2 in Graph Theory by Parth Narodia (23 points) | 167 views

+25 votes

6 answers

28

GATE2005-7
The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be: $O(n)$ $O(n \log n)$ $O \left( n^{\frac{3}{2}} \right)$ $O\left(n^3\right)$

answered Mar 2 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 6.9k views

+14 votes

3 answers

29

GATE2002-3
Let $A$ be a set of $n(>0)$ elements. Let $N_r$ be the number of binary relations on $A$ and let $N_f$ be the number of functions from $A$ to $A$ Give the expression for $N_r,$ in terms of $n.$ Give the expression for $N_f,$ terms of $n.$ Which is larger for all possible $n,N_r$ or $N_f$

answered Mar 2 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 932 views

+25 votes

4 answers

30

GATE2000-2.5
A relation $R$ is defined on the set of integers as $xRy$ iff $(x + y)$ is even. Which of the following statements is true? $R$ is not an equivalence relation $R$ is an equivalence relation having 1 equivalence class $R$ is an equivalence relation having 2 equivalence classes $R$ is an equivalence relation having 3 equivalence classes

answered Mar 2 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 3.4k views

+12 votes

4 answers

31

GATE1999-3
Mr. X claims the following: If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof: “From xRy, using symmetry we get yRx. Now because R is transitive xRy and yRx together imply xRx. Therefore, R is reflexive”. Give an example of a relation R which is symmetric and transitive but not reflexive.

answered Mar 2 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 979 views

+12 votes

3 answers

32

GATE1998-1.6
Suppose $A$ is a finite set with $n$ elements. The number of elements in the largest equivalence relation of A is $n$ $n^2$ $1$ $n+1$

answered Mar 2 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 3.1k views

0 votes

1 answer

33

website
There is 4 coins 1 paisa, 5 paise, 10 paise, 25 paise using these coins we have to make 50 paisa how many combination can we make ?

answered Mar 1 in Combinatory by smsubham Boss (16k points) | 46 views

+1 vote

2 answers

34

MadeEasy Test Series: Mathematical Logic - First Order Logic
Pardon for the screenshot though. No idea of latex.

answered Mar 1 in Mathematical Logic by Madhab Loyal (6.2k points) | 204 views

+3 votes

2 answers

35

Rosen 7e Exercise-6.5 question 45.b page 433
How many ways can n books be placed on k distinguishable shelves if no two books are the same, and the positions of the books on the shelves matter?

answered Mar 1 in Combinatory by smsubham Boss (16k points) | 213 views

+25 votes

5 answers

36

GATE2017-2-21
Consider the set $X=\{a, b, c, d, e\}$ under partial ordering $R=\{(a,a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e) \}$ The Hasse diagram of the partial order $(X, R)$ is shown below. The minimum number of ordered pairs that need to be added to $R$ to make $(X, R)$ a lattice is ______

answered Mar 1 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 4.3k views

+3 votes

2 answers

37

ISRO2020-73
Given that $B(a)$ means “$a$ is a bear” $F(a)$ means “$a$ is a fish” and $E(a,b)$ means “$a $ eats $b$” Then what is the best meaning of $\forall x [F(x) \to \forall y(E(y,x)\rightarrow b(y))]$ Every fish is eaten by some bear Bears eat only fish Every bear eats fish Only bears eat fish

answered Mar 1 in Mathematical Logic by Madhab Loyal (6.2k points) | 369 views

+2 votes

2 answers

38

GATE1988-2xviii
Show that if $G$ is a group such that $(a, b)^2 = a^2.b^2$ for all $a, b$ belonging to $G$, then $G$ is an abelian.

answered Feb 29 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 291 views

+11 votes

4 answers

39

TIFR2013-B-16
Consider a function $T_{k, n}: \left\{0, 1\right\}^{n}\rightarrow \left\{0, 1\right\}$ which returns $1$ if at least $k$ of its $n$ inputs are $1$. Formally, $T_{k, n}(x)=1$ if $\sum ^{n}_{1} x_{i}\geq k$. Let $y \in \left\{0, 1\right\}^{n}$ be such that $y$ ... $y_{i}$ is omitted) is equivalent to $T_{k-1}, n(y)$ $T_{k, n}(y)$ $y_{i}$ $\neg y_{i}$ None of the above.

answered Feb 29 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 465 views

+13 votes

3 answers

40

TIFR2012-B-1
For $x, y\in \left\{0, 1\right\}^{n}$, let $x ⊕ y$ be the element of $\left\{0, 1\right\}^{n}$ obtained by the component-wise exclusive-or of $x$ and $y$. A Boolean function $F:\left\{0, 1\right\}^{n}\rightarrow\left\{0, 1\right\}$ is said to be linear if $F(x ⊕ y)= F(x) ⊕ F(y)$ ... from $\left\{0, 1\right\}^{n}$ to $\left\{0, 1\right\}$ is. $2^{2n}$ $2^{n+1}$ $2^{n-1}+1$ $n!$ $2^{n}$

answered Feb 29 in Set Theory & Algebra by Pratyush Priyam Kuan Active (1.1k points) | 638 views

To see more, click for all the questions in this category.

Recent questions and answers in Discrete Mathematics

51,840 questions

58,630 answers

200,017 comments

111,642 users