Description

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 indegree 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 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.

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 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_{1}, E_{2}, …, 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_{1} , . . . , S_{k} is a partition of S, if each S_{i} is a subset of S, no two subsets have a nonempty intersection, and the union of all the subsets is S.)

Express your algorithm in a wellstructured manner. Pseudo code in the textbook has good examples 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 L^{A}T_{E}X, L_{Y}X or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.
2