Mathematics for Computer Science

12.5. Returning toK 5 andK3;3 373 Butf DevC 2 by Euler’s formula, and substituting into (12.3) gives 3.evC2/2e e3vC 6  0 e3v ...

Chapter 12 Planar Graphs374 for any embedding of a planar bipartite graph. By Euler’s theorem,fD 2 vCe. Substituting 2 vCeforf i ...

12.7. Coloring Planar Graphs 375 n 2 n 1 n 2 n 1 !! m Figure 12.12 Merging adjacent verticesn 1 andn 2 into new vertex,m. Many a ...

Chapter 12 Planar Graphs376 (a) (b) (c) (d) (e) (f) e 1 v 1 v 2 e 2 v 3 Figure 12.13 One method by which the graph in (a) can be ...

12.8. Classifying Polyhedra 377 Every planar graph withvvertices is five-colorable. Base cases(v 5 ): immediate. Inductive case ...

Chapter 12 Planar Graphs378 (a) (b) (c) Figure 12.14 The tetrahedron (a), cube (b), and octahedron (c). (a) (b) (c) Figure 12.15 ...

12.8. Classifying Polyhedra 379 n m v e f polyhedron 3 3 4 6 4 tetrahedron 4 3 8 12 6 cube 3 4 6 12 8 octahedron 3 5 12 30 20 ic ...

Chapter 12 Planar Graphs380 Problems for Section 12.2 Practice Problems Problem 12.1. What are the discrete faces of the followi ...

12.8. Classifying Polyhedra 381 b c d e a g h i f j k l m n o g 1 g 2 g 3 (d)Explain why all embeddings of two isomorphic planar ...

Chapter 12 Planar Graphs382 a b c d e f Figure 12.17 Class Problems Problem 12.5. Figures 1–4 show different pictures of planar ...

12.8. Classifying Polyhedra 383 a b d c e e figure 1 figure 2 figure 3 figure 4 a b d c a b d c a b d c ...

Chapter 12 Planar Graphs384 Homework Problems Problem 12.7. A simple graph istriangle-freewhen it has no cycle of length three. ...

12.8. Classifying Polyhedra 385 Corollary(Delete Edge).Deleting an edge from a planar graph leaves a planar graph. (d)Conclude t ...

...

13 State Machines DRAFT We’ve already demonstrated the use of state machines as abstract models of step- by-step processes. In t ...

Chapter 13 State Machines388 outgoing-msgs, a finite sequence ofM, whose initial value is calledall-msgs tagbit2f0;1g, initially ...

13.1. The Alternating Bit Protocol 389 All 0 ’s. All 1 ’s. A positive number of 0 ’s followed by a positive number of 1 ’s. A p ...

Chapter 13 State Machines390 mis the first message onwork-buf 1. The effect of the transition is to changetag 2 to make it equal ...

13.2. Reasoning AboutWhilePrograms 391  CID—called thesequencingofCandD,  ifTthenCelseD—called aconditionalwithtest,T, andbran ...

Chapter 13 State Machines392 Executing a program causes a succession of changes to the environment^1 which may continue until th ...