Computer Science 280: Homework 11 (The Last One!)

~

Homework 11 (The Last One!):
4/23/08 (due 4/30/08) Read 3.1, 3.3, 3.5, 3.6 (3.1, 3.2, 3.4, 3.6, and 3.7 in DAM2). final). Hand in all the following problems. Don't forget to explain your reasoning in all these problems. 

Section     Number                Points        Comments
3.1         3                     5             DAM2, 3.1, 2
            27(b)                 3             DAM2, 3.2, 16(b)
            29(a)                 4             DAM2, 3.2, 18(a).  Hint: do a proof by contradiction
3.3         34                    4             DAM2, 3.4, 26
            39(c)                 3             DAM2, 3.2, 24(c). Explain your answer!
3.6         12                    3             DAM2, 3.7, 10
            14                    4             DAM2, 3.7, 12

More problems:

1. [6 points] Which of the three graphs in Section 3.6, Problem 2 (3.7, 2 in DAM2) have Eulerian cycles? (Explain why or why not.) Of the ones that do not have Eulerian cycles, which have Eulerian paths? (Again, explain why or why not.) Describe the Eulerian path/cycle when there is one. This will require drawing the graph in your homework and naming the vertices. For simplicity, label the graphs using vertices v1, v2, v3, v4 and (for parts (b) and (c)) v5, with v1 at the top and the rest of the vertices labeled in clockwise order.

2. [4 points] For the graph described in Section 3.6, Problem 2(c) (3.7, 2(c) in DAM2) describe the order that the vertices would be visited using BFS (starting at v1). Repeat for DFS. When the algorithm gives you a choice, choose the lower labeled vertex (for example, if you have a choice between v2 and v3, choose v2).

3. [5 points] The divisibility graph D(n) has vertices {1,2,...,n} and an edge from i to j iff i divides j.
(a) Draw D(12)
(b) How many components does it have?
(c) What is its clique number?

4. [5 points] (due to Jon Kleinberg) Ad hoc networks, made up of low-powered wireless devices, have been proposed for situations like natural disasters in which the coordinators of a rescue effort might want to monitor conditions in a hard-to-reach area. The idea is that a large collection of these wireless devices could be dropped into such an area from an airplane, and then be configured into a functioning network. Suppose we have a collection of 8 such devices (real applications would have a much, much larger number), we drop them onto a region that we'll model as the plane, and they land at the following points as specified by 2-dimensional coordinates: (0, 0), (50, 0), (50, 50), (100, 50), (100, 100), (100, 150), (150, 50), (200, 50): Furthermore, suppose that two of these devices are able to communicate provided that they are within 80 meters of one another.
(a) Draw a picture of the following graph G: the vertices correspond to the set of 8 devices, and there is an edge joining each pair of devices that can communicate. (Leave out the self-loops.)
(b) Draw a spanning tree of G produced by breadth-first search starting from the vertex at coordinates (50, 0).

5. [4 points] (also due to Jon Kleinberg:) Recall that in class we showed that if an undirected graph G wiht no self-loops has the property that if every vertex has degree at least 2, then it must contain a cycle. We now want to claim that if we require the minimum degree to be large, then we can in fact find a long cycle. First, let's say that a cycle in a graph is simple if it doesn't repeat vertices; in other words, it consists of vertices v1, v2, v3, ,..., vk in sequence, where v1 = vk and v1, v2, .., v(k-1) are all different. For every d > 1, prove that if a graph G with no self-loops has the property that every vertex has degree at least d, then it contains a simple cycle with at least d + 1 vertices. (Hint: Consider creating a path in G by successively moving along edges from one vertex to another, trying to avoid repeating vertices for as long as possible. Think about what happens at the end of this process, when you can no longer avoid repeating vertices.)