Exercises
201
a
a Logon
e
e Load Text Editor
f
f Open File
Dh
P h Insert Ext. File
b
b b Open Mailer
4P
c Reply
g
P g Modify File
d
P, d Send New Msg.
0 i Save Modified File
Linear order
U
In Chapter 6, we will examine and analyze an algorithm called Topological Sort that
carries out the embedding of a partial order in a linear order.
rnExercises
1. (a) Draw the diagram to represent the I (divides) partial order on {1, 2, 3, 4, 5, 6}.
(b) List all the maximal, maximum, minimal, and minimum elements.
2. (a) Draw a diagram to represent the I (divides) partial order on 10, 1, 2, 3, 4, 5, 6, 7,
8,9, 10, 111.
(b) Identify all minimal, minimum, maximal, and maximum elements in the diagram.
3. (a) Draw a diagram to represent the I (divides) partial order on the set {1, 2, 3, 4, 5, 6,
7,8,9,10,11).
(b) Identify all minimal, minimum, maximal, and maximum elements in the diagram.
4. Draw a diagram to represent the I (divides) partial order on the following:
(a) {1, 111
(b) 11, 3, 7, 211
(c) {1, 2, 3, 4, 6, 9, 12, 18, 36)
(d) {1, 2, 4, 8, 16, 32, 64)
5. Prove that Examples 5(a) and (b) are partial orderings.
6. Let
X = 1-5, -4, -3, -2, -1,0, 1, 2, 3,4, 51
For x, y E X, set x R y if x
2 < y
2 or x = y. Show that R is a partial ordering on X.
Draw a diagram of R.
7. (a) Explain why the relation "is older than or the same age" is a partial order.
(b) Explain why the relation "is older than" is not a linear order.