CS 163/265--Graph Algorithms Homework 1

CS 163/265--Graph Algorithms  Homework 1 

Please answer the following questions, each of which is worth 10 points. 

1. (CS 163 students only) Draw a simple undirected graph G that has 12 vertices, 18 edges, and 3 connected components. Why would it be impossible to draw G with 3 connected components if G had 66 edges? 

2. (CS 163 students only) Let G be a graph whose vertices are the integers 1 through 8, and let the adjacent vertices of each vertex be given by the table below:  

Assume that, in a traversal of G, the adjacent vertices of a given vertex are returned in the same order as they are listed in the above table. 

(a) Draw G. 

(b) Order the vertices as they are visited in a DFS traversal starting at vertex 1. 

(c) Order the vertices as they are visited in a BFS traversal starting at vertex 1. 

3. Let G be an undirected graph with n vertices and m edges. Describe an algorithm running in O(n+ m) time that traverses each edge of G exactly once in each direction. 

4. Suppose G is a graph with n vertices and m edges. Describe a way to represent G using O(n + m) space so as to support in O(log n) time an operation that can test, for any two vertices v and w, whether v and w are adjacent. 

5. Let G be an undirected graph with n vertices and m edges. Describe an O(n+m)-time algorithm to determine whether G contains at least two cycles. 

6. (CS 265 students only) The time delay of a long-distance call can be determined by multiplying a small fixed constant by the number of communication links on the telephone network between the caller and callee. Suppose the telephone network of a company named RT&T is a free tree. The engineers of RT&T want to compute the maximum possible time delay that may be experienced in a long-distance call. Given a free tree T, the diameter of T is the length of a longest path between two nodes of T. Give an efficient algorithm for computing the diameter of T. 

7. (CS 265 students only) A company named RT&T has a network of n stations connected by m high-speed communication links. Each customer’s phone is connected to one station in his or her area. The engineers of RT&T have developed a prototype videophone system that allows two customers to see each other during a phone call. In order to have acceptable image quality, however, the number of links used to transmit video signals between the two parties cannot exceed 4. Suppose that RT&T’s network is represented by a graph. Design an efficient algorithm that computes, for each station, the set of stations it can reach using no more than 4 links.