Chapter 9 Directed graphs & Partial Orders270
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.
Problems for Section 9.10
Practice Problems
Problem 9.24.
What is the size of the longest chain that is guaranteed to exist in any partially
ordered set ofnelements? What about the largest antichain?
Problem 9.25.
Describe a sequence consisting of the integers from 1 to 10,000 in some order so
that there is no increasing or decreasing subsequence of size 101.
Problem 9.26.
What is the smallest number of partially ordered tasks for which there can be more
than one minimum time schedule, if there are unlimited number of processors?
Explain your answer.
Class Problems
Problem 9.27.
The table below lists some prerequisite information for some subjects in the MIT
Computer Science program (in 2006). This defines an indirect prerequisite relation