Mathematics for Computer Science

9.12. Summary of Relational Properties 273 Oshani and Oscar want to complete all these tasks in the shortest possible time. Howe ...

Chapter 9 Directed graphs & Partial Orders274 Delete an edge that is in a cycle. Delete edgehu!viif there is a path from ve ...

9.12. Summary of Relational Properties 275 Problem 9.31. Letbe a partial order on a set,A, and let AkWWDfajdepth.a/Dkg wherek 2 ...

Chapter 9 Directed graphs & Partial Orders276 (c)Explain the connection between increasing and decreasing subsequences ofS, ...

9.12. Summary of Relational Properties 277 (d)Show thateverypartial order withnvertices and maximum chain size,t, has ap-process ...

...

10 Communication Networks Modeling communication networks is an important application of digraphs in com- puter science. In this ...

Chapter 10 Communication Networks280 IN 0 OUT 0 IN 1 OUT 1 IN 2 OUT 2 IN 3 OUT 3 assumeNis a power of two. Which input is suppos ...

10.4. Switch Count 281 path between an input and an output. For example, in the complete binary tree above, the distance from in ...

Chapter 10 Communication Networks282 10.5 Network Latency We’ll sometimes be choosing routings through a network that optimize s ...

10.7. 2-D Array 283 IN 0 OUT 0 IN 1 OUT 1 IN 2 OUT 2 IN 3 OUT 3 IN 0 OUT 0 IN 1 OUT 1 IN 2 OUT 2 IN 3 OUT 3 the congestion of th ...

Chapter 10 Communication Networks284 in 0 in 1 in 2 in 3 out 0 out 1 out 2 out 3 ...

10.8. Butterfly 285 Proof. First, we show that the congestion is at most 2. Letbe any permutation. Define a solution,P, forto ...

Chapter 10 Communication Networks286 2 inputs 2 outputs À À ND 2 1 Figure 10.1 F 1 , the Butterfly Net switches withND 21. compo ...

10.9. Bene ̆s Network 287 ⎧ ⎨ F ⎨ ⎩ 2 n Fn ⎩ 2 n1 tt ⎧ ⎨ F 2 n+^1 outputs ⎨ ⎩ 2 n Fn F newinputs ⎩ Fn+1 Figure 10.2 FnC 1 , the ...

Chapter 10 Communication Networks288 Bn Bn BnC 1 2 n 2 n 2 nC^1 À À new inputs new outputs Figure 10.3 BnC 1 , the Bene ̆s Net s ...

10.9. Bene ̆s Network 289 completely eliminates congestion problems! The proof of this fact relies on a clever induction argumen ...

Chapter 10 Communication Networks290 in 1 out 1 in 0 out 0 in 2 out 2 in 3 out 3 in 4 out 4 in 5 out 5 in 6 out 6 in 7 out 7 Fig ...

10.9. Bene ̆s Network 291 switches. We can record these additional constraints in our graph with gray edges: 1 5 0 4 2 6 7 3 Not ...

Chapter 10 Communication Networks292 For example, here is a 2-coloring of the constraint graph: blue blue blue blue red red red ...