Mathematics for Computer Science
11.7. Coloring 413 6:002 6:170 6:003 6:041 6:042 Figure 11.12 A scheduling graph for five exams. Exams connected by an edge cann ...
Chapter 11 Simple Graphs414 red blue green green blue Figure 11.13 A 3-coloring of the exam graph from Figure 11.12. is red, Mon ...
11.7. Coloring 415 Cycles in simple graphs by convention have positive length and so are not 1- colorable. So .Ceven/D2: On the ...
Chapter 11 Simple Graphs416 Figure 11.14 A 7-node star graph. Inductive step: Now assume thatP.n/is true, and letGbe an.nC1/-ver ...
11.8. Simple Walks 417 two stations have an overlap in their broadcast area, they can’t be given the same frequency. Frequencies ...
Chapter 11 Simple Graphs418 a b c d e f g h Figure 11.15 A graph with 3 cycles:bhecb,cdec,bcdehb. edge, and the other endpoint i ...
11.9. Connectivity 419 atdand going throughdehbcd. Furthermore, cycles in simple graphs don’t have a direction:dcbheddescribes t ...
Chapter 11 Simple Graphs420 But not all graphs are connected. For example, the graph where nodes represent cities and edges repr ...
11.9. Connectivity 421 In other words, if a graph has any one of the three properties above, then it has all of the properties. ...
Chapter 11 Simple Graphs422 for some positive length walksfandrthat begin and end atx. Since jwjDjfjCjrj is odd, exactly one off ...
11.9. Connectivity 423 For example, in the graph in figure 11.15, verticescandeare 3-connected,b andeare 2-connected,gandeare 1 ...
Chapter 11 Simple Graphs424 Inductive step: LetGebe the graph that results from removing an edge,e 2 E.G/. SoGe haskedges, and b ...
11.10. Forests & Trees 425 Figure 11.17 A 6-node forest consisting of 2 component trees. a b d c e h i f g Figure 11.18 A 9- ...
Chapter 11 Simple Graphs426 a b c f h i e d g Figure 11.19 The tree from Figure 11.18 redrawn with nodeeas the root and the othe ...
11.10. Forests & Trees 427 Suppose that we remove edgehu—vi. Since the tree contained a unique path betweenuandv, that path ...
Chapter 11 Simple Graphs428 Figure 11.20 A graph where the edges of a spanning tree have been thickened. Theorem 11.10.6.Every c ...
11.10. Forests & Trees 429 2 3 3 7 1 2 1 (a) 2 3 3 7 1 2 1 4 1 1 3 (b) Figure 11.21 A spanning tree (a) with weight 19 for a ...
Chapter 11 Simple Graphs430 What about the tree shown in Figure 11.22? It seems to be an MST, but how do we prove it? In general ...
11.10. Forests & Trees 431 2 7 1 2 1 1 3 Figure 11.23 A spanning tree found by Algorithm 1. So to extend a pre-MST, choose a ...
Chapter 11 Simple Graphs432 Now suppose we instead ran Algorithm 2 on our graph. We might again choose the weight 1 edge on the ...
«
17
18
19
20
21
22
23
24
25
26
»
Free download pdf