Discrete Mathematical Structure and Graph Theory - B.Tech 4th Semester Exam., 2015

The set of all real numbers under the usual multiplication operation is not a group since

1. multiplication is not a binary operation
2. multiplication is not associative
3. identity element does not exist
4. zero has no inverse

If \( R = \{(1, 2), (2, 3), (3, 3)\} \) be a relation defined on \( A = \{1, 2, 3\} \), then \( R \circ R \) is

1. R itself
2. \( \{(1, 2), (1, 3), (3, 3)\} \)
3. \( \{(1, 3), (2, 3), (3, 3)\} \)
4. \( \{(2, 1), (1, 3), (2, 3)\} \)

Pick out the correct statement(s):

1. The set of all \( 2 \times 2 \) matrices with rational entries (with the usual operations of matrix addition and matrix multiplication) is a ring which has no nontrivial ideals.
2. Let \( R = C[0,1] \) be considered as a ring with the usual operations of pointwise addition and pointwise multiplication and let \( I = \{f : [0,1] \rightarrow R | f(1/2) = 0\} \). Then I is a maximal ideal.
3. Let R be a commutative ring and let P be a prime ideal of R. Then R/P is an integral domain.
4. None of the above is correct

Let f and g be the functions defined by \( f(x) = 2x+3 \) and \( g(x) = 3x+2 \). Then the 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, then how many people jog?

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

If a graph is a tree, then

1. it has 2 spanning trees
2. it has only 1 spanning tree
3. it has 4 spanning trees
4. it has 5 spanning trees

The relation R on the set of all integers, where \( (x, y) \in R \) if and only if \( xy \ge 1 \) is

1. anti-symmetric
2. transitive
3. symmetric
4. both transitive and symmetric

How many functions are there from a set with three elements to a set with two elements?

1. 6
2. 8
3. 12
4. 7

Which one of the following is correct for any simple connected undirected graph with more than 2 vertices?

1. No two vertices have the same degree
2. At least two vertices have the same degree
3. At least three vertices have the same degree
4. All vertices have the same degree

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

Define set. Let X be the universal set and \( S \subset X \), \( T \subset X \). Then prove that:
(a) \( (S \cup T)^c = S^c \cap T^c \)
(b) \( (S \cap T)^c = S^c \cup T^c \)

Define relations and function. What is equivalence relation?

Let A be the set of all people in India. If \( x, y \in A \), then let us say that \( (x,y) \in R \) if x and y have the same surname (i.e., last name). Then prove that R is an equivalence relation.

Define group, Abelian group and groupoid. Also define composition of functions. Let \( f: R \rightarrow \{x \in R: x \ge 0\} \) be given by \( f(x) = x^4 + x^2 + 6 \) and \( g: \{x \in R: x \ge 0\} \rightarrow R \) be given by \( g(x) = \sqrt{x} - 4 \). Then find \( (g \circ f)(x) \) and \( (f \circ g)(x) \).

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.

Define commutative ring. Consider the set X, its power set \( P(X) = \{A | A \subset X\} \) is the set of all subsets of X. Show that the power set is a commutative ring under the following two operations \( A + B = (A - B) \cup (B - A) \) where \( \cup \) is set union and \( - \) is set difference, and \( AB = A \cap B \).

Prove that (a) the maximum number of nodes N on level i of a binary tree is \( 2^i \), \( i \ge 0 \) and (b) the maximum number of nodes in a binary tree of height h is \( 2^h - 1 \), \( h \ge 1 \).

Define Walks, Paths and Circuits related to a graph. Write down all possible (a) paths from \( v_1 \) to \( v_8 \), (b) circuits of G and (c) trails of length three in G from \( v_3 \) to \( v_5 \) of the graph shown in the figure below.

Show that if a and b are the only two odd degree vertices of a graph G, then a and b are connected in G. Prove that a connected graph G remains connected after removing an edge e from G if and only if e lie in some circuit in G.