a b
c
d
Relation R on A
making R a
partial order
c
d
ba
making a
Hasse diagram
a
b c
d
possible orderings
of elements of A
a, b, c, d
a, c, b, d
FIGURE 5.11 Partial order on a set A, Hasse diagram, and partial orderings of A.
The relation is transitive. Reflexive arcs are
dropped for ease of display.
1
2
3
4
6
9
R = “divides evenly”
on A = {1, 2, 3, 4, 6, 9}
1
2
3
4
6
9
6
2
3
4
1
9
Making R a Hasse diagram
16 possible orderings of elements of A:
1, 2, 3, 4, 6, 9 1, 3, 2, 4, 6, 9
1, 2, 3, 4, 9, 6 1, 3, 2, 4, 9, 6
1, 2, 3, 6, 4, 9 1, 3, 2, 6, 4, 9
1, 2, 3, 6, 9, 4 1, 3, 2, 6, 9, 4
1, 2, 3, 9, 4, 6 1, 3, 2, 9, 4, 6
1, 2, 3, 9, 6, 4 1, 3, 2, 9, 6, 4
1, 2, 4, 3, 6, 9 1, 3, 9, 2, 4, 6
1, 2, 4, 3, 9, 6 1, 3, 9, 2, 6, 4
FIGURE 5.12 Second Hasse diagram example.
134
GRAPHS AND DIRECTED GRAPHS (DIGRAPHS)