# Graphs – Hasse Diagrams

1. Hasse diagrams are first made by ______
a) A.R. Hasse
b) Helmut Hasse
c) Dennis Hasse
d) T.P. Hasse

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

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)

.

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(!=)

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

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

7. In a poset (S, ), if there is no element nS 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

.

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}

.

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

.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