Mathematics for Computer Science

9.10. Scheduling 251

underwear shirt

jacket

left shoe right shoe belt

left sock right sock

pants tie

Figure 9.7 DAG describing which clothing items have to be put on before others.

underwear left sock

pants shirt

belt tie

shirt underwear

tie right sock

jacket pants

left sock right shoe

right sock belt

left shoe jacket

right shoe left shoe

(a) (b)

Figure 9.8 Two possible topological sorts of the partial order described in Fig-
ure 9.7. In each case, the elements are listed so thatxyiffxis aboveyin the
list.