Solved–Homework 2 –Solution

Description

1. An Eulerian cycle of a graph G is a path which starts and ends on the same vertex and traverses every edge in the graph exactly once.

1. 1. We have seen that an undirected connected graph G = (V, E) such that all the vertices have even degrees has an Eulerian cycle. Give an O(jEj) time algorithm to find it.

1. 2. A directed graph is strongly connected if every vertex is reachable from every other vertex. Assume that for every vertex in a directed graph G = (V, E) its in-degree equals its out degree, and G is strongly connected. Prove that G has an Eulerian cycle and give an O(E) time algorithm to find it.

2. A celebrity among n persons is someone who is known by everyone but does not know anyone. Equivalently, given a directed graph G = (V, E) with n vertices, a directed edge from v_i to v_j represents person i knows person j, a celebrity vertex is the vertex with no outgoing edge and n 1 incoming edges. In the class, we have seen an O(n) recursive algorithm that finds whether celebrity exists or not and it does returns it. The graph G is represented by an n n adjacency matrix M, which is a (0, 1)-matrix such that M[i, j] = 1 if and only if there is a directed edge from v_i to v_j . Give an iterative O(n) time algorithm to find the celebrity vertex in G, or output none if no one is.

3. Given a undirected tree T , the diameter of a tree is the number of edges in the longest path in the tree. Design an algorithm that find the diameter of the tree in O(n) time where n is number of the nodes in the tree.

4. Let K_n = (V, E) be a complete undirected graph with n vertices (namely, every two vertices are connected), and let n be an even number. A spanning tree of G is a connected subgraph of G that contains all vertices in G and no cycles. Design a recursive algorithm that given the graph K_n, partitions the set of edges E into n=2 distinct subsets E₁, E₂, …, E_n=2, such that for every subset E_i , the subgraph G_i = (V, E_i ) is a spanning tree of K_n.

(Hint: Solve the problem recursively by removing two nodes and their edges in K_n. From the output of recursive call, you get (n 2)=2 spanning trees for K_{n 2}. Extend those trees to be spanning trees for K_n and then construct a new spanning tree to complete the job. PS: A collection of sets S₁ , . . . , S_k is a partition of S, if each S_i is a subset of S, no two subsets have a non-empty intersection, and the union of all the subsets is S.)

• Express your algorithm in a well-structured manner. Pseudo code in the textbook has good ex-amples to follow. Avoid using a long continuous piece of text to describe your algorithm. Start each problem on a NEW page. Unless specified, you should justify the time complexity of your algorithm and why it works. For grading, we will take into account both the correctness and the clarity. Your answers are supposed to be in a simple and understandable manner and sloppy answers are expected to receiver fewer points.

• Homework assignments are due on Gradescope. Email attachments or paper submissions are NOT acceptable.

• Raw photo is NOT acceptable. Upload your homework as a PDF scan by using a scanner or mobile scanner app. Match each problem with your answer on Gradescope. Use dark pen or pencil and your handwriting should be clear and legible.

• We recommend using L^AT_EX, L_YX or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.

2