Mathematics for Computer Science

11.6. The Stable Marriage Problem 313 Brad Billy Bob Jennifer Angelina 1 2 2 1 1 2 2 1 Figure 11.11 Preferences for four people. ...

Chapter 11 Simple Graphs314 Robin Bobby Joe Alex Mergatroid 3 3 2 1 1 2 (^213) Figure 11.12 Some preferences with no stable budd ...

11.6. The Stable Marriage Problem 315  The Ritual eventually reaches the termination condition.  Everybody ends up married.  ...

Chapter 11 Simple Graphs316 Case 2: wwas crossed offm’s list prior to daydC 1. SincePis true at the end of dayd, this means that ...

11.6. The Stable Marriage Problem 317 the woman he most prefers among those on his list until he must cross her off, at which po ...

Chapter 11 Simple Graphs318 By the definition of an optimal spouse, there must be some stable set of marriages in which Keith ge ...

11.7. Coloring 319 The Internet infrastructure company, Akamai, also uses a variation of the Mating Ritual to assign web traffic ...

Chapter 11 Simple Graphs320 6:002 6:170 6:003 6:041 6:042 Figure 11.13 A scheduling graph for five exams. Exams connected by an ...

11.7. Coloring 321 coloring is called itschromatic number,.G/. SoGisk-colorable iff.G/k. In general, trying to figure out if ...

Chapter 11 Simple Graphs322 Sincekis the only nonnegative integer valued variable mentioned in the the- orem, you might be tempt ...

11.7. Coloring 323 Figure 11.15 A 7-node star graph. functions. This problem was eventually solved by making a 65,000-node confl ...

Chapter 11 Simple Graphs324 11.8 Getting fromutovin a Graph Walks and paths in simple graphs are esentially the same as in digra ...

11.9. Connectivity 325 a b c d e f g h Figure 11.16 A graph with 3 cycles:bhecb,cdec,bcdehb. Definition 11.8.2.A graphGis said t ...

Chapter 11 Simple Graphs326 11.9.1 Connected Components Being connected is usually a good property for a graph to have. For exam ...

11.9. Connectivity 327 Definition 11.9.3.Two vertices in a graph arek-edge connectedwhen they remain connected in every subgraph ...

Chapter 11 Simple Graphs328 Of course for Theorem 11.9.6 to be of any use, there must be fewer edges than vertices. Proof. We us ...

11.10. Odd Cycles and 2-Colorability 329 11.10 Odd Cycles and 2-Colorability We have already seen that determining the chromatic ...

Chapter 11 Simple Graphs330 is a closed walk starting and ending atu, and its length is jwujCjwvjC1: This length is odd, sincewu ...

11.11. Forests & Trees 331 Figure 11.18 A 6-node forest consisting of 2 component trees. a b d c e h i f g Figure 11.19 A 9- ...

Chapter 11 Simple Graphs332 a b c f h i e d g Figure 11.20 The tree from Figure 11.19 redrawn with nodeeas the root and the othe ...