Mathematics for Computer Science
11.11. References 453 Supposefis ann-argument truth function. That is, fWfT;Fgn!fT;Fg: A graphGis called a3-color-f-gateiffGhasn ...
Chapter 11 Simple Graphs454 [h] T F ‘ P N ‘ NOT(P) Figure 11.28 A 3-colorNOT-gate [h] P OR Q P Q N F T Figure 11.29 ...
11.11. References 455 [h] u v x w Figure 11.30 A 3-color cross-over gadget. Problem 11.40. The 3-coloring problem for planar ...
Chapter 11 Simple Graphs456 [h] Figure 11.31 Replacing an edge-crossing with a planar gadget. Hint:Only two colorings are needed ...
11.11. References 457 supposeGnC 1 has a vertex,v, of degree strictly less thank. Now we only need to prove thatGnC 1 isk-colora ...
Chapter 11 Simple Graphs458 [h] N F T P ⊕ Q P Q XOR b F a c d e Figure 11.32 A 3-colorXOR-gate Problems for Section 11.8 Homewor ...
11.11. References 459 complete problems known as theHamiltonian Cycle Problem). But it turns out to be easy to characterize whic ...
Chapter 11 Simple Graphs460 (b)Verify that for any two verticesx¤yofH 3 , there are 3 paths fromxtoyin H 3 , such that, besidesx ...
11.11. References 461 (c)Explain whyMnis.n1/-edge connected. Problem 11.48. False Claim. If every vertex in a graph has positive ...
Chapter 11 Simple Graphs462 By the principle of induction,P.n/is true for alln 0 , which proves the Claim. Homework Problems ...
11.11. References 463 Problem 11.50. In the cycleC2nof length2n, we’ll call two verticesoppositeif they are on opposite sides of ...
Chapter 11 Simple Graphs464 For any state, letebe the number of edges in it, and letcbe the number ofcon- nected componentsit ha ...
11.11. References 465 c b a d f e h g Figure 11.33 The graphG. (c)ForGewith edgeha—dideleted, explain why there cannot be two ed ...
Chapter 11 Simple Graphs466 000 001 010 011 100 101 110 111 Figure 11.34 H 3. Problem 11.58. Thediameterof a connected graph is ...
11.11. References 467 For every finite graph (not necessarily a tree), there is one (a finite tree) that spans it. true false P ...
Chapter 11 Simple Graphs468 ProcedureMarksimply keeps marking eligible edges, and terminates when there are none. Prove thatMark ...
11.11. References 469 (vii)cCs (d)Prove that one of the quantities from part (c) strictly decreases at each transi- tion. Conclu ...
Chapter 11 Simple Graphs470 edge among the edges with one endpoint in the tree. Continue as long as there is no edge between two ...
11.11. References 471 (c)Assume thatDsatisfies equation (11.9). Show that it is possible to partition Dinto two setsS 1 ;S 2 suc ...
...
«
19
20
21
22
23
24
25
26
27
28
»
Free download pdf