Chapter 9 Directed graphs & Partial Orders366
corresponding to the empty set must be scheduled first because; Sfor every
nonempty setSf1;2;3;4;5g.
(a)What is the minimum parallel time to complete these tasks?(b)Describe a maximum size antichain in this partial order.(c)Briefly explain why the minimum number of processors required to complete
these tasks in minimum parallel time is equal to the size of the maximum antichain.
Problems for Section 9.9
Class Problems
Problem 9.41.
LetR 1 ,R 2 be binary relations on the same set,A. A relational property is preserved
under product, ifR 1 R 2 has the property whenever bothR 1 andR 2 have the
property.
(a)Verify that each of the following properties are preserved under product.- reflexivity,
- antisymmetry,
- transitivity.
(b)Verify that ifeitherofR 1 orR 2 is irreflexive, then so isR 1 R 2.
Note that it now follows immediately that if ifR 1 andR 2 are partial orders and
at least one of them is strict, thenR 1 R 2 is a strict partial order.
Problem 9.42.
A partial order on a setAiswell foundedwhen every non-empty subset ofAhas a
minimalelement. For example, the less-than relation on a well ordered set of real
numbers (see 2.4) is a linear order that is well founded.
Prove that ifRandSare well founded partial orders, then so is their product
RS.
Homework Problems
Problem 9.43.
LetSbe a sequence ofndifferent numbers. AsubsequenceofSis a sequence that
can be obtained by deleting elements ofS.