Discrete Mathematics Multiple Choice Questions 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
Answer: b
Clarification: 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
Answer: a
Clarification: 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)
Answer: a
Clarification: 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(!=)
Answer: a
Clarification: 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
Answer: a
Clarification: 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) ==
Answer: a
Clarification: 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
Answer: b
Clarification: 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}
Answer: a
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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.