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(n2)
c) O(n+2)
d) O(n3)
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 P1 is a partially ordered class and a cut of P1 is pair (D, T) of nonempty subclasses of P1 satisfies which of the following properties?
a) D∩T=Ø
b) D∪T=P1
c) xyz∈T
d) z∈T and zx∈D
View Answer
Explanation: Suppose P1 is a partially ordered class and a cut of P1 is pair (D, T) of nonempty subclasses of P1 satisfies the following properties: i) D∩T=Ø and D∪T=P1 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 218. Hence, the number of edges in Hasse diagram are 18 * 218-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.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check BCA Books
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Information Technology MCQs
- Practice BCA MCQs
