Discrete Mathematics-B

(i) Let A be a finite set of n elements. Then number of maximum elements in any equivalence class of A is :

(a) 1

(b) n

(c) n + 1

(d) n²

एक अज्ञात: क्रमित समुच्चय में उच्चतम अवयवों की संख्या होती है :

(अ) 1

(ब) n

(स) n + 1

(द) n²

(ii) Number of maximal elements in a partially ordered set is :

(a) 1

(b) at least 1

(c) at most 1

(d) None of the above

एक अज्ञात: क्रमित समुच्चय में उच्चतम अवयवों की संख्या होती है :

(अ) 1

(ब) कम से कम 1

(स) अधिक से अधिक 1

(द) उपर्युक्त में से कोई नहीं

(iii) Number of edges in a complete graph of n vertices :

(a) n

(b) n/2

(c) n²–1

(d) n(n–1)/2

n शीर्ष वाले पूर्ण ग्राफ में भुजाओं की संख्या होगी :

(अ) n

(ब) n/2

(स) n²–1

(द) n(n–1)/2

(iv) No. of edges of a spanning tree spanned by a graph of vertices n :

(a) n

(b) n–1

(c) 2n–1

(d) n²

n शीर्ष वाले ग्राफ से जनित किसी जनक वृक्ष में भुजाओं की संख्या होगी :

(अ) n

(ब) n – 1

(स) 2n – 1

(द) n²

(v) Kuratowski's second graph is :

(a) planar

(b) non-planar

(c) may be planar or non-planar

(d) None of the above

कुराटोवस्की का द्वितीय ग्राफ होता है :

(अ) समतलीय

(ब) असमतलीय

(स) समतलीय या असमतलीय हो सकता है

(द) उपर्युक्त में से कोई नहीं

Find the disjunctive normal form of the polynomial :

बहुपद :

का वियोजनीय प्रसामान्य रूप ज्ञात कीजिए।

Or

अथवा

If R^-1 and S^-1 are inverse of the relations R and S respectively, then prove that :

यदि R^-1 तथा S^-1 क्रमशः संबंध R व S के प्रतिलोम हैं, तो सिद्ध कीजिए कि :

Make Hasse diagram of partial order set (S₃₀, D).

अंशतः क्रम समुच्चय (S₃₀, D) के लिए हासे चित्र बनाइए।

Or

अथवा

Define the following :

(a) Distributive lattice

(b) Bounded lattice

निम्नलिखित को परिभाषित कीजिए :

(अ) बंटनात्मक जालक

(ब) परिबद्ध जालक

Define Hamiltonian Path and Circuit.

हैमिल्टोनियन पथ तथा परिपथ को परिभाषित कीजिए।

Or

अथवा

Define connected graph, disconnected graph and components.

संबद्ध ग्राफ, असंबद्ध ग्राफ तथा घटक को परिभाषित कीजिए।

Define Rooted tree and Binary tree.

नियत वृक्ष और द्विचर वृक्ष को परिभाषित कीजिए।

Or

अथवा

If there is one and only one path between every pair of vertices in a graph G, then prove that G is a tree.

यदि किसी ग्राफ G में शीर्षों के प्रत्येक युग्म के बीच एक और केवल एक पथ हो, तो सिद्ध कीजिए कि G एक वृक्ष है।

Define Adjacency Matrix with an example.

संलग्नता आव्यूह को उदाहरण सहित परिभाषित कीजिए।

Or

अथवा

Discuss Konigsberg Bridge Problem with reference to graph theory.

ग्राफ सिद्धांत के संदर्भ में कोनिग्सबर्ग पुल समस्या का वर्णन कीजिए।

If R is equivalence relation on A then prove that R^-1 is also equivalence relation.

यदि R एक तुल्यता संबंध है, तो सिद्ध कीजिए कि R^-1 भी तुल्यता संबंध है।

Or

अथवा

State and prove Boal's expansion theorem.

बूल के विस्तार प्रमेय का कथन लिखिए एवं सिद्ध कीजिए।

If L is set of factors of 24 and l is relation on division on L, then show that (L, l) is a lattice.

यदि 1 एवं 24 के गुणनखंडों का समुच्चय है तथा ↓ L पर विभाज्य संबंध है, तब दर्शाइए कि (L, l) एक जालक है।

Or

अथवा

In a Boolean Algebra B[+, *, '], prove that :

(a) a + b = l.u.b. {a, b}

(b) ab = g.l.b. {a, b}

एक बूलीय बीजगणित B[+, *, '] में सिद्ध कीजिए :

(अ) a + b = l.u.b. {a, b}

(ब) ab = g.l.b. {a, b}

Find shortest path between a and z in the following graph :

निम्नलिखित ग्राफ में a और z के बीच न्यूनतम पथ ज्ञात कीजिए :

Using Prim's algorithm, find minimum spanning tree in the following graph :

प्रिम्स कलन का उपयोग करके निम्नलिखित ग्राफ हेतु न्यूनतम जनक वृक्ष ज्ञात कीजिए :

Or

अथवा

Using Kruskal's algorithm, find minimum spanning tree for the following graph :

क्रुसकल कलन का उपयोग करके निम्नलिखित ग्राफ के लिए न्यूनतम जनक वृक्ष ज्ञात कीजिए :

Find incidence and adjacency matrix of each graph :

प्रत्येक ग्राफ का आपतन एवं संलग्नता आव्यूह ज्ञात कीजिए :

(i)

(ii)

Or

अथवा

Prove that complete graph of five vertices is non-planar.

सिद्ध कीजिए कि पाँच शीर्षों वाला पूर्ण ग्राफ असमतलीय होता है।