Discrete Mathematical Structures - B.Tech 4th Semester Exam., 2016

Let f and g be the functions defined by \( f(x) = 2x+3 \) and \( g(x) = 3x-2 \) then composition of f and g is

1. \( 6x+6 \)
2. \( 5x+5 \)
3. \( 6x+7 \)
4. \( 7x+5 \)

Among 200 people, 150 either swim or jog or both. If 85 swim and 60 swim and jog, how many jog?

1. 125
2. 225
3. 85
4. 25

A graph in which all nodes are of equal degree is known as graph.

1. complete
2. multi-
3. non-regular
4. regular

The minimum number of spanning trees in a connected graph with n nodes is

1. \( n-1 \)
2. \( n/2 \)
3. 2
4. 1

If a set contains exactly m distinct elements where m denotes some non-negative integer, then the set is

1. finite
2. infinite
3. None of the above
4. All of the above

In an unweighted, undirected-connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by

1. Dijkstra's algorithm starting from S
2. Warshall's algorithm
3. performing a DFS starting from S
4. performing a BFS starting from S

The negation of 'Today is Friday' is

1. Today is Saturday
2. Today is not Friday
3. Today is Thursday
4. Today is Sunday

Whether the relation R on the set of all integers is reflexive, symmetric, anti-symmetric, or transitive, where \( (x, y) \in R \) if and only if \( xy \ge 1 \)?

1. Anti-symmetric
2. Transitive
3. Symmetric
4. Both symmetric and transitive

If \( p = \text{'It is raining'} \) and \( q = \text{'She will go to college'} \), 'It is raining and she will not go to college' will be denoted by

1. \( p \rightarrow \sim q \)
2. \( p \wedge q \)
3. \( \sim p \wedge q \)
4. \( \sim(p \wedge q) \)

If \( x > 0 \) and \( x^2 < 0 \), then \( x \ge 10 \).

1. True
2. False
3. Both (i) and (ii)
4. None of the above

Define the following terms and give an example for each:
Reflexive relation, irreflexive relation, antisymmetric relation, partition set

Prove that, if \( S = \{s_1, s_2, \cdots, s_k\} \) be a set, then \( P(S) \) has \( 2^k \) elements.

Define 'group', 'order of a group', and 'Abelian group'. Prove that every subgroup of a cyclic group is cyclic.

Define the following with example:
Ring, homomorphism, cyclic group, coset

Determine whether f is one-one or onto for the following cases:
(i) Let \( A = B = \{1, 2, 3, 4\} \) and \( f = \{(1, 1), (2, 3), (4, 2)\} \)
(ii) Let \( A = \{a, b, c\} \), \( B = \{1, 2, 3, 4\} \) and \( f = \{(a, 1), (b, 1), (c, 4)\} \)

Suppose H and K are normal subgroups of G with \( H \cap K = \{1\} \). Show that \( xy = yx \) for all \( x \in H \) and \( y \in K \). Let \( I \in R \) be an ideal.

The radical \( \sqrt{I} = \{r \in R | rn \in I, n \in N\} \). Show that \( \sqrt{I} \) is an ideal.

State and prove De Morgan's laws of set theory.

In a survey of 260 college students, the following data were obtained: 64 had taken a mathematics course, 94 had taken a computer science course, 58 had taken a business course, 28 had taken both a mathematics and a business course, 26 had taken both a mathematics and a computer science course, 22 had taken both a computer science and a business course, and 14 had taken all three types of courses.
(i) How many of these students had taken none of the three courses?
(ii) How many had taken only a computer science course?

Prove that for any non-empty binary tree T, if \( n_0 \) is the number of leaves and \( n_2 \) be the number of nodes having degree two, then \( n_0 = n_2 + 1 \).

Derive total number of nodes of a binary tree having depth n.

What is graph? Differentiate between directed and undirected graph.

How many different ways can you represent a graph? Explain each of the representations by examples. What is complete graph?

Prove that the sum of degrees of all vertices in a graph is always even.

Consider the graph given below:
(a) Find the adjacency list and BFS traversal of the above graph.

Prove that the maximum number of edges possible in a simple graph of n nodes is \( n(n-1)/2 \).