《Mathematics for Computer》Problem Set 5 Solutions

6.042/18.] Mathematics for Computer Science March 1. 2005 Srini devadas and Eric Lehman Problem Set 5 Solutions Due: Monday March 7 at 9 PM Problem 1. An undirected graph G has width w if the vertices can be arranged in a se quence such that each vertex ui is joined by an edge to at most w preceding vertices. (Vertex uj precedes vi if j< i. Use induction to prove that every graph with width at most w is (a 1)-colorable (Recall that a graph is k-colorable iff every vertex can be assigned one of k colors so that adjacent vertices get different colors Solution. We use induction on n, the number of vertices. Let P(n) be the proposition that every graph with width w is(w +1)colorable Base case: Every graph with n= l vertex has width 0 and is 0+1= l colorable. Therefore, P(1 is true Inductive step: Now we assume P(n)in order to prove P(n+1). Let G be an(n+1)-vertex graph with width w. This means that the vertices can be arranged in a sequence U1,U2,03 n,n+1 such that each vertex vi is connected to at most w preceding vertices. Removing vertex Un+1 and all incident edges gives a graph G with n vertices and width at most w. (If original sequence is retained, then removing Un+1 does not increase the number of edges from a vertex U; to a preceding vertex. )Thus, G is(w 1)-colorable by the assumption P(n). Now replace vertex Un+1 and its incident edges. Since Un+1 is joined by an edge to at most w preceding vertices, we can color un+1 differently from all of these. Therefore P(n+1) is true The theorem follows by the principle of induction Problem 2. In this problem, we walk you through a proof of the following theorem Theorem 1. A graph G is bipartite if and only if it contains no odd cycle As is common with"if and only if "assertions, the proof has two parts. Part(a)asks you to prove that the left side implies the right side. Parts(b),(c)and(d) help you prove that the right side implies the left (Recall that a graph is bipartite iff it is 2-colorable

6.042/18.062J Mathematics for Computer Science March 1, 2005 Srini Devadas and Eric Lehman Problem Set 5 Solutions Due: Monday, March 7 at 9 PM Problem 1. An undirected graph G has width w if the vertices can be arranged in a se￾quence v1, v2, v3, . . . , vn such that each vertex vi is joined by an edge to at most w preceding vertices. (Vertex vj precedes vi if j < i.) Use induction to prove that every graph with width at most w is (w + 1)­colorable. (Recall that a graph is k­colorable iff every vertex can be assigned one of k colors so that adjacent vertices get different colors.) Solution. We use induction on n, the number of vertices. Let P(n) be the proposition that every graph with width w is (w + 1) colorable. Base case: Every graph with n = 1 vertex has width 0 and is 0 + 1 = 1 colorable. Therefore, P(1) is true. Inductive step: Now we assume P(n) in order to prove P(n+ 1). Let G be an (n+ 1)­vertex graph with width w. This means that the vertices can be arranged in a sequence v1, v2, v3, . . . , vn, vn+1 such that each vertex vi is connected to at most w preceding vertices. Removing vertex vn+1 and all incident edges gives a graph G� with n vertices and width at most w. (If original sequence is retained, then removing vn+1 does not increase the number of edges from a vertex vi to a preceding vertex.) Thus, G� is (w + 1)­colorable by the assumption P(n). Now replace vertex vn+1 and its incident edges. Since vn+1 is joined by an edge to at most w preceding vertices, we can color vn+1 differently from all of these. Therefore, P(n + 1) is true. The theorem follows by the principle of induction. Problem 2. In this problem, we walk you through a proof of the following theorem: Theorem 1. A graph G is bipartite if and only if it contains no odd cycle. As is common with “if and only if” assertions, the proof has two parts. Part (a) asks you to prove that the left side implies the right side. Parts (b), (c) and (d) help you prove that the right side implies the left. (Recall that a graph is bipartite iff it is 2­colorable.)

Problem Set 5 (a)Assume the left side and prove the right side. Three to five sentences should suffice Solution. Select a 2-coloring of G. Consider an arbitrary cycle with vertices u1, U2,.,Uk Then the vertices v; must be one color for all even i and the other color for all odd Since v and Uk must be colored differently, k must be even. Thus, the cycle has even length (b)Now were going to prove that the right side implies the left. As a preliminary step, explain why there is a 2-coloring of any tree T Solution. Select a"root"vertex r arbitrarily. Color a vertex v red if the distance in T from r to u is even, and color u black if the distance from r is odd o see that this defines a valid 2-coloring of the tree T, consider an arbitrary edge I-y. There is a unique path from c to r and a unique path from y to r. One of these paths must contain the edge r-y; otherwise, this edge together with portions of the other two paths would form a cycle If r-y is on the unique path from a to r, then y is exactly one edge closer than r to the root r. Similarly, if -y is on the unique path from y to r, then a is one edge closer than y to the root. In either case one vertex is at an odd distance from r and the other is at an even distance from r, so the two vertices are differently-colored (c) Suppose that G is a connected graph with no odd cycle, and let T be a spanning tree of G. Show that a valid 2-coloring of T also defines a valid 2-coloring of G Solution. Vertices connected by an edge in T have different colors in a 2-coloring of T by the argument above, so we need only show that an edge x-y not in the tree must connect different-colored vertices Let z be the first common vertex on the path in T from a to the root r and the path in T from y to r. The path from a to z, followed by the path from z to y, followed by the edge y-a form a cycle which, by hypothesis, must be of even length. Since the length of the cycle is one plus the sum of the lengths of the two paths, one of the paths must have odd length and the other even length. This implies that of the paths from a to r and from y to r, one has even length and the other odd length From the way we 2-colored T, it follows that and y must be colored differently (d) Now assume the right side of Theorem 1; namely, G is a graph with no odd cycle, but is not necessarily connected Prove that G is bipartite Solution. Color each connected component of G with 2 colors one at a time Problem 3. Let G1=(V, E1)and G2=(V, E2)be undirected graphs in which every vertex has degree 1. The union of graphs G1 and G2 is the graphG=(V, E1 U E2). Prove that G is b Solution. Consider any cycle in G. If an edge on the cycle is in E1, then the dg her side in the cycle must be in E2; otherwise, the degree of G1 would be greater than

2 Problem Set 5 (a) Assume the left side and prove the right side. Three to five sentences should suffice. Solution. Select a 2­coloring of G. Consider an arbitrary cycle with vertices v1, v2, . . . , vk. Then the vertices vi must be one color for all even i and the other color for all odd i. Since v1 and vk must be colored differently, k must be even. Thus, the cycle has even length. (b) Now we’re going to prove that the right side implies the left. As a preliminary step, explain why there is a 2­coloring of any tree T. Solution. Select a “root” vertex r arbitrarily. Color a vertex v red if the distance in T from r to v is even, and color v black if the distance from r is odd. To see that this defines a valid 2­coloring of the tree T, consider an arbitrary edge x—y. There is a unique path from x to r and a unique path from y to r. One of these paths must contain the edge x—y; otherwise, this edge together with portions of the other two paths would form a cycle. If x—y is on the unique path from x to r, then y is exactly one edge closer than x to the root r. Similarly, if x—y is on the unique path from y to r, then x is one edge closer than y to the root. In either case, one vertex is at an odd distance from r and the other is at an even distance from r, so the two vertices are differently­colored. (c) Suppose that G is a connected graph with no odd cycle, and let T be a spanning tree of G. Show that a valid 2­coloring of T also defines a valid 2­coloring of G. Solution. Vertices connected by an edge in T have different colors in a 2­coloring of T by the argument above, so we need only show that an edge x—y not in the tree must connect different­colored vertices. Let z be the first common vertex on the path in T from x to the root r and the path in T from y to r. The path from x to z, followed by the path from z to y, followed by the edge y—x form a cycle which, by hypothesis, must be of even length. Since the length of the cycle is one plus the sum of the lengths of the two paths, one of the paths must have odd length and the other even length. This implies that of the paths from x to r and from y to r, one has even length and the other odd length. From the way we 2­colored T, it follows that x and y must be colored differently. (d) Now assume the right side of Theorem 1; namely, G is a graph with no odd cycle, but is not necessarily connected. Prove that G is bipartite. Solution. Color each connected component of G with 2 colors one at a time. Problem 3. Let G1 = (V, E1) and G2 = (V, E2) be undirected graphs in which every vertex has degree 1. The union of graphs G1 and G2 is the graph G = (V, E1 ∪ E2). Prove that G is bipartite. Solution. Consider any cycle in G. If an edge on the cycle is in E1, then the edges on either side in the cycle must be in E2; otherwise, the degree of G1 would be greater than

Problem set 5 1. Thus, the edges around the cycle are alternately in El and e2. This implies the length of the cycle must be even, so G is bipartite by Theorem 1 Problem 4. For each integer n >0, we can define a graph called an n-cube, which is denoted Hn. The vertices are all n-bit sequences, 0, 1. There is an edge between two vertices if they differ in exactly one bit position 0-cube -cube 2-cube 3-cube (a) Prove that h has an Euler tour for all even n >2 Solution. We prove that Hn has an Euler tour by showing that it is connected and every vertex has even degree First, consider two arbitrary vertices in an n-cube, b1b2. bn and C1C2.Cn. These two vertices are joined by a path which traverses vertices in the following sequence b1b2b3.bn C1b2b3.b C1C2C3··.Cm (Note the same vertex may appear several times consecutively in this sequence; so, more accurately, the path traverses the distinct vertices in this sequence. )Therefore, ph is connected Each vertex v in an n-cube is adjecent to exactly n other vertices, those which can be obtained by flipping one of the n bits of vertex v. Therefore, if n is even, every vertex in an n-cube has even degree. Thus, Hn has an Euler tour for all even (b)Prove that Hn has a Hamiltonian cycle for all n 2. Consider an inductive argument based on the fact that Hn+1 consists of two subgraphs isomorphic to Hn (bold lines) with corresponding vertices joined(dotted lines) -cube 3-cube

Problem Set 5 3 1. Thus, the edges around the cycle are alternately in E1 and E2. This implies the length of the cycle must be even, so G is bipartite by Theorem 1. Problem 4. For each integer n ≥ 0, we can define a graph called an n­cube, which is n denoted Hn. The vertices are all n­bit sequences, {0, 1} . There is an edge between two vertices if they differ in exactly one bit position. 0−cube 1−cube 2−cube 3−cube (a) Prove that Hn has an Euler tour for all even n ≥ 2. Solution. We prove that Hn has an Euler tour by showing that it is connected and every vertex has even degree. First, consider two arbitrary vertices in an n­cube, b1b2 . . . bn and c1c2 . . . cn. These two vertices are joined by a path which traverses vertices in the following sequence: b1b2b3 . . . bn c1b2b3 . . . bn c1c2b3 . . . bn . . . c1c2c3 . . . cn (Note the same vertex may appear several times consecutively in this sequence; so, more accurately, the path traverses the distinct vertices in this sequence.) Therefore, the graph is connected. Each vertex v in an n­cube is adjecent to exactly n other vertices, those which can be obtained by flipping one of the n bits of vertex v. Therefore, if n is even, every vertex in an n­cube has even degree. Thus, Hn has an Euler tour for all even n ≥ 2. (b) Prove that Hn has a Hamiltonian cycle for all n ≥ 2. Consider an inductive argument based on the fact that Hn+1 consists of two subgraphs isomorphic to Hn (bold lines) with corresponding vertices joined (dotted lines): 2−cube 3−cube

Problem Set 5 Solution. We use induction on n. Let P(n) be the proposition that an n-cube has a Hamiltonian cycle. A 2-cube is itself a cycle on four vertices, so P(2)is true. Now suppose that P(n) is true for some n >2, and consider an(n+ 1)-cube. As noted in the suggestion, this graph consists of two subgraphs isomorphic to the n-cube with corresponding vertices joined by edges. By induction, there is a Hamiltonian cle Cn in one of these two subgraphs and a corresponding Hamiltonian cycle C in the other. Deleting an edge u-U from Cn, deleting the corresponding edge u from Cn and adding the edges u-u' and U-U creates a Hamiltonian cycle in the (n+ 1)-cube. Therefore, P(n+ 1)is true, and the claim follows by the principle of induction Problem 5. A portion of a computer program consists of a sequence of calculations where the results are stored in variables, like this: Inputs b C a+b a米C C+3 5 6. h=f+1 d, g, h A computer can perform such calculations most quickly if the value of each variable is stored in a register, a chunk of very fast memory inside the microprocessor. Computers problem of assigning each variable in a program to a register is called register allocation Q usually have few registers, however, so they must be used wisely and reused often. TE In the example above, variables a and b must be assigned different registers, because they hold distinct input values. Furthermore, c and d must be assigned different registers if they used the same one, then the value of c would be overwritten in the second step and we'd get the wrong answer in the third step. On the other hand, variables b and d may use the same register; after the first step, we no longer need b and can overwrite the register that holds its value. Also, f and h may use the same register; once f+ 1 is evaluated in the last step, the register holding the value of f can be overwritten (Assume that the computer carries out each step in the order listed and that each step is completed before the next is begun. (a) Recast the register allocation problem as a question about graph colo What do the vertices correspond to? Under what conditions should there between two vertices? Construct the graph corresponding to the example above Solution. There is one vertex for each variable. An edge between two vertices indicates that the values of the variables must be stored in different registers

� 4 Problem Set 5 Solution. We use induction on n. Let P(n) be the proposition that an n­cube has a Hamiltonian cycle. A 2­cube is itself a cycle on four vertices, so P(2) is true. Now suppose that P(n) is true for some n ≥ 2, and consider an (n + 1)­cube. As noted in the suggestion, this graph consists of two subgraphs isomorphic to the n­cube, with corresponding vertices joined by edges. By induction, there is a Hamiltonian cycle Cn in one of these two subgraphs and a corresponding Hamiltonian cycle C� n in the other. Deleting an edge u—v from Cn, deleting the corresponding edge u� —v� from Cn, and adding the edges u—u� and v—v� creates a Hamiltonian cycle in the (n + 1)­cube. Therefore, P(n + 1) is true, and the claim follows by the principle of induction. Problem 5. A portion of a computer program consists of a sequence of calculations where the results are stored in variables, like this: Inputs: a, b Step 1. c = a + b 2. d = a ∗ c 3. e = c + 3 4. 5. f g = = c − e a + f 6. h = f + 1 Outputs: d, g, h A computer can perform such calculations most quickly if the value of each variable is stored in a register, a chunk of very fast memory inside the microprocessor. Computers usually have few registers, however, so they must be used wisely and reused often. The problem of assigning each variable in a program to a register is called register allocation. In the example above, variables a and b must be assigned different registers, because they hold distinct input values. Furthermore, c and d must be assigned different registers; if they used the same one, then the value of c would be overwritten in the second step and we’d get the wrong answer in the third step. On the other hand, variables b and d may use the same register; after the first step, we no longer need b and can overwrite the register that holds its value. Also, f and h may use the same register; once f + 1 is evaluated in the last step, the register holding the value of f can be overwritten. (Assume that the computer carries out each step in the order listed and that each step is completed before the next is begun.) (a) Recast the register allocation problem as a question about graph coloring. What do the vertices correspond to? Under what conditions should there be an edge between two vertices? Construct the graph corresponding to the example above. Solution. There is one vertex for each variable. An edge between two vertices indicates that the values of the variables must be stored in different registers

Problem set 5 5 We can classify each appearance of a variable in the program as either an assignment or a use. In particular, an appearance is an assignment if the variable is on the left side of an equation or on the" Inputs"line. An appearance of a variable is a use if the variable is on the right side of an equation or on the"Outputs"lir The lifetime of a variable is the segment of code extending from the initial assignment of the variable until the last use. There is an edge between two variables if their lifetimes overlap. This rule generates the following graph (b) Color your graph using as few colors as you can. Call the computer's registers Rl, R2, etc. Describe the assignment of variables to registers implied by your color ing. How many registers do you need? Solution. Four registers are needed. One possible assignment of variables to regis ters is indicated in the figure above In general, coloring a graph using the minimum number of colors is quite difficult no efficient procedure is known. However, the register allocation problem always leads to an interval graph. For interval graphs, there are efficient coloring procedures, which can be incorporated into a compiler (c) Suppose that a variable is assigned a value more than once, as in the code snippet below: r+s t*3 t+u How might you cope with this complication? Solution. Each time a variable is reassigned, we could regard it as a completely new

Problem Set 5 5 We can classify each appearance of a variable in the program as either an assignment or a use. In particular, an appearance is an assignment if the variable is on the left side of an equation or on the “Inputs” line. An appearance of a variable is a use if the variable is on the right side of an equation or on the “Outputs” line. The lifetime of a variable is the segment of code extending from the initial assignment of the variable until the last use. There is an edge between two variables if their lifetimes overlap. This rule generates the following graph: a b c d e f g h R1 R2 R2 R3 R4 R2 R1 R2 (b) Color your graph using as few colors as you can. Call the computer’s registers R1, R2, etc. Describe the assignment of variables to registers implied by your color￾ing. How many registers do you need? Solution. Four registers are needed. One possible assignment of variables to regis￾ters is indicated in the figure above. In general, coloring a graph using the minimum number of colors is quite difficult; no efficient procedure is known. However, the register allocation problem always leads to an interval graph. For interval graphs, there are efficient coloring procedures, which can be incorporated into a compiler. (c) Suppose that a variable is assigned a value more than once, as in the code snippet below: . . . t = r + s u = t ∗ 3 t = m − k v = t + u . . . How might you cope with this complication? Solution. Each time a variable is reassigned, we could regard it as a completely new

Problem Set 5 ariable. Then we would regard the example as equivalent to the following r+s n-k t+ We can now proceed with graph construction and coloring as before Problem 6. A DeBruijn sequence of order k is a string of 0s and 1's that contains ev- ery combination of k bits as a substring exactly once. For example, here is a De bruijn sequence of order 2 Notice that every combination of two bits(01, 11, 10, and 00) appears exactly once as a substring (a)Find a DeBruijn sequence of order 3. You may find the following diagram helpful 0 10 0 0 00 01 0 Solution. One possible solution 1000101110 Notice that this correponds to a directed walk beginning at vertex 10 that traverses every edge exactly once. Specifically, if we write down the number of the starting ertex(10) and then the number on each edge traversed, we obtain this sequence

6 Problem Set 5 variable. Then we would regard the example as equivalent to the following: . . . t = r + s u = t ∗ 3 t � = m − k v = t � + u . . . We can now proceed with graph construction and coloring as before. Problem 6. A DeBruijn sequence of order k is a string of 0’s and 1’s that contains ev￾ery combination of k bits as a substring exactly once. For example, here is a DeBruijn sequence of order 2: 01100 Notice that every combination of two bits (01, 11, 10, and 00) appears exactly once as a substring. (a) Find a DeBruijn sequence of order 3. You may find the following diagram helpful. 00 10 11 01 1 0 0 1 1 0 1 0 Solution. One possible solution is: 1000101110 Notice that this correponds to a directed walk beginning at vertex 10 that traverses every edge exactly once. Specifically, if we write down the number of the starting vertex (10) and then the number on each edge traversed, we obtain this sequence

Problem set 5 (b)In a directed graph, a directed walk is an alternating sequence of vertices and U1, U1 a directed Euler tour is a directed walk that traverses every edge in a graph exactly once and ends where it began; that is, U1=Un. Suppose G is a directed graph such that the in-degree of each vertex is equal to its out-degree and there is a directed walk from every vertex to every other vertex. Prove that g has a directed euler tour Solution. We use proof by contradiction. Let P=→→2,→t3,3—4,…,tn-1-t be the longest directed path in G. Then every edge out of un must be on the path ince the indegree of un is equal to the out-degree, the only possibility that the ul Suppose that P is not a directed Euler tour; that is, some edge c-y in graph G is not on the path P. Then there exists a directed path from un to r by assumption. Let Ui-z be the first edge on this path that is not on the path P. Then the directed -+2+1,Un-1Un:U1 ,2-t3,,"l-+z is longer than P, which is a contradiction. (c) Explain why a De Bruijn sequence of order k exists for every k> 2 Solution. Construct a digraph whose vertices are all (k-1)-bit strings. Put a di- rected edge labeled bk from each vertex b1b2... bk-1 to the vertex b2 ., bk-1bk.(Here, each variable bi denotes a bit. )The suggestion illustrates such a graph for k= 3 In this graph, each vertex has indegree 2 and outdegree 2. Furthermore, the grap is connected; a path from vertex b1b2... bk-1 to C1C2... Ck-1 is obtained by following the the edges labeled C1, C2,..., and Ck-1. Therefore, the digraph has an Euler tour Now start at any vertex. Write down the number at that vertex. Then write down ev ery number on a directed Euler tour of the graph Whenever the walk exits a vertex b1b2... bk-1 on an edge labeled bk, the suffix of the sequence so far is b1b2... bk-1bk Since the tour traverses every edge out of every vertex exactly once, the resulting sequence contains every k-bit string exactly once

Problem Set 5 7 (b) In a directed graph, a directed walk is an alternating sequence of vertices and edges: v1, v1 −→v2, v2, v2 −→v3, v3, v3 −→v4, v4, . . . , vn−1, vn−1 −→vn, vn A directed Euler tour is a directed walk that traverses every edge in a graph exactly once and ends where it began; that is, v1 = vn. Suppose G is a directed graph such that the in­degree of each vertex is equal to its out­degree and there is a directed walk from every vertex to every other vertex. Prove that G has a directed Euler tour. Solution. We use proof by contradiction. Let P = v1 −→v2, v2 −→v3, v3 −→v4, . . . , vn−1 −→vn be the longest directed path in G. Then every edge out of vn must be on the path. Since the indegree of vn is equal to the out­degree, the only possibility that the v1 = vn. Suppose that P is not a directed Euler tour; that is, some edge x−→y in graph G is not on the path P. Then there exists a directed path from v1 to x by assumption. Let vi −→ z be the first edge on this path that is not on the path P. Then the directed path vi −→vi+1, vn−1 −→vn, v1 −→v2, v2 −→v3, . . . , vi −→z is longer than P, which is a contradiction. (c) Explain why a DeBruijn sequence of order k exists for every k ≥ 2. Solution. Construct a digraph whose vertices are all (k − 1)­bit strings. Put a di￾rected edge labeled bk from each vertex b1b2 . . . bk−1 to the vertex b2 . . . , bk−1bk. (Here, each variable bi denotes a bit.) The suggestion illustrates such a graph for k = 3. In this graph, each vertex has indegree 2 and outdegree 2. Furthermore, the graph is connected; a path from vertex b1b2 . . . bk−1 to c1c2 . . . ck−1 is obtained by following the the edges labeled c1, c2, . . . , and ck−1. Therefore, the digraph has an Euler tour. Now start at any vertex. Write down the number at that vertex. Then write down ev￾ery number on a directed Euler tour of the graph. Whenever the walk exits a vertex b1b2 . . . bk−1 on an edge labeled bk, the suffix of the sequence so far is b1b2 . . . bk−1bk. Since the tour traverses every edge out of every vertex exactly once, the resulting sequence contains every k­bit string exactly once