9.12. Summary of Relational Properties 277
(d)Show thateverypartial order withnvertices and maximum chain size,t, has
ap-processor schedule that runs in timeM.n;t;p/.
Hint:Induction ont.
Problems for Section 9.11
Homework Problems
Problem 9.34.
For any total functionf WA!Bdefine a relationfby the rule:
afa^0 iff f.a/Df.a^0 /: (9.13)(a)Prove thatf is an equivalence relation onA.(b)Prove that every equivalence relation on a setAis equal toffor some total
functionf WA!B.