This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Graphs – Hasse Diagrams”.

1. Hasse diagrams are first made by ______

a) A.R. Hasse

b) Helmut Hasse

c) Dennis Hasse

d) T.P. Hasse

View Answer

Explanation: Hasse diagrams can be described as the transitive reduction as an abstract directed acyclic graph. This graph drawing techniques are constructed by Helmut Hasse(1948).

2. If a partial order is drawn as a Hasse diagram in which no two edges cross, its covering graph is called ______

a) upward planar

b) downward planar

c) lattice

d) biconnected components

View Answer

Explanation: In a Hasse diagram if no two edges cross each other in the drawing of partial order Hasse diagram, then its covering graph called the upward planar.

3. If the partial order of a set has at most one minimal element, then to test whether it has a non-crossing Hasse diagram its time complexity __________

a) NP-complete

b) O(n^{2})

c) O(n+2)

d) O(n^{3})

View Answer

Explanation: If the partial order has at most one minimal element, or it has at most one maximal element, then to test whether a partial order with multiple sources and sinks can be drawn as a crossing-free Hasse diagram or not it’s time complexity is NP-complete.

4. Which of the following relation is a partial order as well as an equivalence relation?

a) equal to(=)

b) less than(<)

c) greater than(>)

d) not equal to(!=)

View Answer

Explanation: The identity relation = on any set is a partial order in which every two distinct elements are incomparable and that depicts the relation of both a partial order and an equivalence relation. For non-linear orders, there are many advanced properties of posets.

5. The relation ≤ is a partial order if it is ___________

a) reflexive, antisymmetric and transitive

b) reflexive, symmetric

c) asymmetric, transitive

d) irreflexive and transitive

View Answer

Explanation: Let A is a set and ≤ is a relation on A, then ≤ is a partial order if it satisfies reflexive, antisymmetric, and transitive, i.e., for all x, y and z in P. That means, x ≤ x (reflexivity);

if x ≤ y and y ≤ x then x = y (antisymmetry) and if x ≤ y and y ≤ z then x ≤ z (transitivity).

6. In which of the following relations every pair of elements is comparable?

a) ≤

b) !=

c) >=

d) ==

View Answer

Explanation: In the ≤(or less than and equal to) relation, every pair of elements is comparable.

7. In a poset (S, ⪯), if there is no element n∈S with m<n, then which of the following is true?

a) an element n exists for which m=n

b) An element m is maximal in the poset

c) A set with the same subset of the poset

d) An element m is minimal in the poset

View Answer

Explanation: By the definition, an element m exists in a poset (S, ⪯) is maximal if and only if there is no n∈S with m≺n.

8. In a poset P({v, x, y, z}, ⊆) which of the following is the greatest element?

a) {v, x, y, z}

b) 1

c) ∅

d) {vx, xy, yz}

View Answer

Explanation: We know that, in a Hasse diagram, the maximal element(s) are the top and the minimal elements are at the bottom of the diagram. In the given poset, {v, x, y, z} is the maximal or greatest element and ∅ is the minimal or least element.

9. Suppose P_{1} is a partially ordered class and a cut of P_{1} is pair (D, T) of nonempty subclasses of P_{1} satisfies which of the following properties?

a) D∩T=Ø

b) D∪T=P_{1}

c) xyz∈T

d) z∈T and zx∈D

View Answer

Explanation: Suppose P

_{1}is a partially ordered class and a cut of P

_{1}is pair (D, T) of nonempty subclasses of P

_{1}satisfies the following properties: i) D∩T=Ø and D∪T=P

_{1}ii) If z∈D and y≤z, then y∈D and iii) If z∈T and y≥z, then y∈T.

10. Let G be the graph defined as the Hasse diagram for the ⊆ relation on the set S{1, 2,…, 18}. How many edges are there in G?

a) 43722

b) 2359296

c) 6487535

d) 131963

View Answer

Explanation: Here the total number of elements in S is 18 and so number of vertices in Hasse diagram are 2

^{18}. Hence, the number of edges in Hasse diagram are 18 * 2

^{18-1}=2359296.

**Sanfoundry Global Education & Learning Series – Discrete Mathematics.**

To practice all areas of Discrete Mathematics, __here is complete set of 1000+ Multiple Choice Questions and Answers__.