Mathematics for Computer Science

9 Directed graphs & Partial Orders Directed graphs, calleddigraphsfor short, provide a handy way to represent how things are ...

Chapter 9 Directed graphs & Partial Orders234 in 0 in 1 in 2 out 0 out 1 out 2 Figure 9.2 A 6-switch packet routing digraph. ...

9.1. Digraphs & Vertex Degrees 235 u v tail e head Figure 9.4 A directed edgeeDhu!vi. The edgeestarts at the tail vertex,u, ...

Chapter 9 Directed graphs & Partial Orders236 12 6 1 4 2 8 10 5 7 3 9 11 Figure 9.5 The Digraph for Divisibility onf1;2;:::; ...

9.2. Digraph Walks and Paths 237 wherehvi!viC 1 i 2 E.G/fori 2 Œ0;k/. The walk is said tostartatv 0 , toendat vk, and thelength, ...

Chapter 9 Directed graphs & Partial Orders238 same vertex,v, we’ll say that theirmerge,fbr, is the walk that starts withfand ...

9.3. Adjacency Matrices 239 Of course you may expect this property to be true, but distance has a technical definition and its p ...

Chapter 9 Directed graphs & Partial Orders240 A payoff of this representation is that we can use matrix powers to count numb ...

9.3. Adjacency Matrices 241 In other words, you can determine the number of lengthkwalks between any pair of vertices simply by ...

Chapter 9 Directed graphs & Partial Orders242 9.4 Path Relations A basic question about a digraph is whether there is a path ...

9.5. Directed Acyclic Graphs & Partial Orders 243 Remembering that a digraph is a binary relation on its vertices, it makes ...

Chapter 9 Directed graphs & Partial Orders244 New6-3: SB in Computer Science and Engineering 6.UAT All subjects are 12 units ...

9.5. Directed Acyclic Graphs & Partial Orders 245 The proof is essentially the same as for Theorem 9.2.3 (see Problem 9.6). ...

Chapter 9 Directed graphs & Partial Orders246 9.6 Weak Partial Orders Partial orders come up in many situations which on the ...

9.7. Representing Partial Orders by Set Containment 247 For weak partial orders in general, we often write an ordering-style sym ...

Chapter 9 Directed graphs & Partial Orders248 So 1! f 1 g 3! f1;3g 4! f1;4g 6! f1;3;6g 8! f1;4;8g 12! f1;3;4;6;12g So, the f ...

9.9. Product Orders 249 order for which every two different elements are comparable is called apath-total order. So<andare p ...

Chapter 9 Directed graphs & Partial Orders250 That is, ifR 1 andR 2 both have one of these properties, then so doesR 1 R 2. ...

9.10. Scheduling 251 underwear shirt jacket left shoe right shoe belt left sock right sock pants tie Figure 9.7 DAG describing w ...

Chapter 9 Directed graphs & Partial Orders252 The elementa 0 isminimaliff no other element isa 0 , that is,NOT.ba 0 /for a ...