MIT6 042JF10 Assn05 PDF

6.042/18.
062J Mathematics for Computer Science Tom Leighton and Marten van Dijk
October 5, 2010
Problem Set 5
Readings: Section 5.4 to 5.7 and 6.1-6.2. Problem 1. [20 points] Recall that a tree is a connected acyclic graph. In particular, a single vertex is a tree. We dene a Splitting Binary Tree, or SBTree for short, as either the lone vertex, or a tree with the following properties: 1. exactly one node of degree 2 (called the root). 2. every other node is of degree 3 or 1 (called internal nodes and leaves, respectively). For the case of one single vertex (see above), that vertex is considered to be a leaf. It is easier to understand the denition visually, so an example is shown in Figure 1. An example of a tree which is not an SBTree is shown in Figure 2. (a) [10 pts] Show if an SBTree has more than one vertex, then the induced subgraph obtained by removing the unique root consists of two disconnected SBTrees. You may assume that by removing the root you obtain two separate connected componenents, so all you need to prove is that those two components are SBTrees. (b) [10 pts] Prove that two SBTrees with the same number of leaves must also have the same total number of nodes. Hint: As a conjecture, guess an expression for the total number of nodes in terms of the number of leaves N (l). Then use induction to prove that it holds for all trees with the same l Problem 2. [20 points] In Die Hard: The Afterlife, the ghosts of Bruce and Sam have been sent by the evil Simon on another mission to save midtown Manhattan. They have been told that there is a bomb on a street corner that lies in Midtown Manhattan, which Simon denes as extending from 41st Street to 59th Street and from 3rd Avenue to 9th Avenue. Additionally, the code that they need to defuse the bomb is on another street corner. Simon, in a good mood, also tosses them two carrots:
He will have a helicopter initially lower them to the street corner where the bomb is.
Problem Set 5
Figure 1: Splitting Binary Tree: Node A is the root, B and E are internal nodes, and C, D, F, and G are leaves. Notice how all internal nodes have degree 3.
Figure 2: This is an example of a tree which is NOT a Splitting Binary Tree. Notice how both A and C have degree 2, when a BSTree can only have one such node.
Problem Set 5
He promises that the code is placed only on a corner of a numbered street and a numbered avenue, so they dont have to search Broadway.
The map of midtown Manhattan is an example of an N M (undirected) grid. In particular, midtown Manhattan is a 19 7 grid. Bruce and Sam need to check all 19 7 = 133 street corners for the code. Once they are at a corner, they dont need any additional time to verify if the code is there. Once they nd the code and return to the bomb, they can disarm it in 2 minutes (even, or especially, as the timer ticks down to 0). Also, they can run one block (in any of the four directions) in exactly 1 minute. They are given 135 minutes total in which to nd the code and disarm the bomb, which means that they need to return to the bomb, code in hand, in 133 minutes. Sam realizes that the map of NYC is actually a graph, and that they need to use a cool new 6.042 concept: A Hamiltonian cycle is a path that visits each vertex in a graph exactly once and ends at its starting point (so it is a cycle). A graph is Hamiltonian if it has a Hamiltonian cycle. Hamiltonian graphs are really useful because you can visit each node and return to the starting point by taking only n steps, where n is the number of nodes if a graph is not Hamiltonian, you would need at least n + 1 steps to visit each of the n nodes and return to the starting point. In general, we dont know how to eciently determine whether a general graph is Hamiltonian or not. However, Sam is very excited because he thinks that he can show that Midtown Manhattan is Hamiltonian. If it is, Bruce and Sam can save the day! Will they make it? (a) [10 pts] Show that they cannot do it that is, more generally, show that if both N and M are odd, then the N M grid is not Hamiltonian. Hint: First show that any N M 2-dimensional undirected grid is bipartite. (b) [10 pts] Suppose Simon dened Midtown in the more standard way as extending from 40th Street to 59th Street and from 3rd Avenue to 9th Avenue (that is suppose Midtown Manhattan was a 20 7 grid), and gave them another 7 minutes, 1. Show that if either N is even and M > 1 or M is even and N > 1, then the N M grid is Hamiltonian. 2. Explain why your proof breaks down when N and M are odd. 3. Would they survive? Does it depend on where the bomb is placed? Problem 3. [20 points] An n-node graph is said to be tangled if there is an edge leaving every set of n or fewer 3 vertices. As a special case, the graph consisting of a single node is considered tangled. (Recall that the notation x refers to the smallest integer greater than or equal to x.)
4 (a) [7 pts] Find the error in the proof of the following claim. Claim. Every non-empty, tangled graph is connected.
Problem Set 5
Proof. The proof is by strong induction on the number of vertices in the graph. Let P (n) be the proposition that if an n-node graph is tangled, then it is connected. In the base case, P (1) is true because the graph consisting of a single node is dened to be tangled and is trivially connected. In the inductive step, for n 1 assume P (1), . . . , P (n) to prove P (n + 1). That is, we want to prove that if an (n + 1)-node graph is tangled, then it is connected. Let G be a tangled, (n + 1)-node graph. Arbitrarily partition G into two pieces so that the rst piece contains exactly n vertices, and the second piece contains all remaining vertices. Note that since 3 n 1, the graph G has a least two vertices, and so both pieces contain at least one vertex. By induction, each of these two pieces is connected. Since the graph G is tangled, there is an edge leaving the rst piece, joining it to the second piece. Therefore, the entire graph is connected. This shows that P (1), . . . , P (n) imply P (n + 1), and the claim is proved by strong induction. (b) [5 pts] Draw a tangled graph that is not connected. (c) [8 pts] An n-node graph is said to be mangled if there is an edge leaving every set of n 2 or fewer vertices. Again, as a special case, the graph consisting of a single node is considered mangled. Prove the following claim. Hint: Prove by contradiction. Claim. Every non-empty, mangled graph is connected. Problem 4. [15 points] (a) [5 pts] Suppose that G is a simple, connected graph on n nodes. Show that G has exactly n 1 edges i G is a tree. (b) [10 pts] Prove by induction that any connected graph has a spanning tree. Problem 5. [15 points] The adjacency matrix of a graph is given below (Section 5.1.6 in the book denes adjacency matrices) 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 0
Problem Set 5
(a) [4 pts] Draw the graph dened by this adjacency matrix. Label the vertices of your graph 1, 2, . . . , 6 so that vertex i corresponds to row and column i of the matrix. (b) [4 pts] In a graph, we dene the distance between to vertices to be the length of the shortest path between them. We dene the diameter of a graph to be the largest distance between any two nodes. What is the diameter of this graph? Explain why. (c) [3 pts] Find a cycle in this graph of maximum length and explain why it has maximum length. (d) [4 pts] Give a coloring of the vertices that uses the minimum number of colors. Prove that this a minimum coloring. Problem 6. [10 points] Let G be a graph. In this problem we show every vertex of odd degree is connected to at least one other vertex of odd degree in G. (a) [6 pts] Let v be an odd degree node. Consider the longest walk starting at v that does not repeat any edges (though it may omit some). Let w be the nal node of that walk. Show that w = v. (b) [4 pts] Show that w must also have odd degree.
MIT OpenCourseWare http://ocw.mit.edu
6.042J / 18.062J Mathematics for Computer Science

Fall 2010
For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.

MIT6 042JF10 Assn05 PDF

Uploaded by

Copyright:

Available Formats

MIT6 042JF10 Assn05 PDF

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MIT6 042JF10 Assn05 PDF

Uploaded by

Copyright:

Available Formats

6.042/18.

MIT OpenCourseWare http://ocw.mit.edu

6.042J / 18.062J Mathematics for Computer Science

You might also like