Discrete Mathematics Questions and Answers – Graphs – Hasse Diagrams

«
»

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

Answer: b
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).
advertisement

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

Answer: a
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

Answer: a
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

Answer: a
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

Answer: a
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).
advertisement

6. In which of the following relations every pair of elements is comparable?
a) ≤
b) !=
c) >=
d) ==
View Answer

Answer: a
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

Answer: b
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

Answer: a
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

Answer: a
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.
advertisement

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

Answer: b
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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn