Homework 2 Solution

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.



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.



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.



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 vi to vj 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 vi to vj . Give an iterative O(n) time algorithm to find the celebrity vertex in G, or output none if no one is.



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.



Let Kn = (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 Kn, partitions the set of edges E into n=2 distinct subsets E1, E2, ..., En=2, such that for every subset Ei , the subgraph Gi = (V, Ei ) is a spanning tree of Kn.



(Hint: Solve the problem recursively by removing two nodes and their edges in Kn. From the output of recursive call, you get (n 2)=2 spanning trees for Kn 2. Extend those trees to be spanning trees for Kn and then construct a new spanning tree to complete the job. PS: A collection of sets S1 , . . . , Sk is a partition of S, if each Si 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.



1



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 LATEX, LYX or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.

















































































































































































2