Remarks: In all algorithm, always explain how and why they work. ALWAYS, analyze the complexity of your algorithms. Prove that it works. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. In all data structures, try to minimize as much as possible the running time of any operation. Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected. Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so that no two edges in the matching share a common vertex. A vertex cover is a collection U CV of vertices so that for every edge uv E E either u EU or v EU. 1. Show that the largest size matching in a graph is no larger than the size of an arbitrary vertex cover in the graph. 2. Show that if I is an independent set then G(V I) (namely, the graph with vertices V - I, restricted to edge with both endpoints in V - I is) a Vertex Cover. 3. Give an example for a graph so that the Maximum Matching is strictly smaller than the minimum Vertex Cover 4. A clique is a collection C of vertices U so that for every uv EC, uv E E. Say that we are given an algorithm that finds a clique of maximum size in time f(n). Give an O(n) + f(n) time algorithm to find the maximum independent set and the minimum vertex cover in the graph Question 3:Long paths in undirected graphs In this question m is the number of edges in an undirected graph. 1. Show that if the degree of every vertex is at least k, then the graph has a simple path of length at least k. Hint: consider the longest simple path in the graph say from x to y. Show that the endpoints x and y do not have edges to vertices outside the path. Thus all the neighbors of x, y are in the path. And recall that all degrees are at least k. 2. Show that every graph has a subgraph with minimum degree m. Hint: itera- tively remove all vertex of degree strictly smaller than m 3. Show that any graph has a path of length at least m. Use the two claims proven in the previous questions. Question 4: A tournament graph is a directed graph that has all edges uv, except that we either have the edge u Hvor v Hu (note that the number of edges is ). Indeed its as if we have n teams, and every pair of two teams plays one basketball game. If u lost to v, the tournament will have the edge u Hv. Clearly what we get is a tournament graph. Show that every tournament graph contains am Hamiltonian path. Hint: Induction will make the answer simple. Give an algorithm that finds an Hamiltonian path in a tournament Question 5: Say that the input has three numbers a, b, c. And we have an algorithm that runs in time at most 2-log a +1/3+ (log c)3. Does the algorithm run in polynomial time? Remarks: In all algorithm, always explain how and why they work. ALWAYS, analyze the complexity of your algorithms. Prove that it works. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. In all data structures, try to minimize as much as possible the running time of any operation. Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected. Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so that no two edges in the matching share a common vertex. A vertex cover is a collection U CV of vertices so that for every edge uv E E either u EU or v EU. 1. Show that the largest size matching in a graph is no larger than the size of an arbitrary vertex cover in the graph. 2. Show that if I is an independent set then G(V I) (namely, the graph with vertices V - I, restricted to edge with both endpoints in V - I is) a Vertex Cover. 3. Give an example for a graph so that the Maximum Matching is strictly smaller than the minimum Vertex Cover 4. A clique is a collection C of vertices U so that for every uv EC, uv E E. Say that we are given an algorithm that finds a clique of maximum size in time f(n). Give an O(n) + f(n) time algorithm to find the maximum independent set and the minimum vertex cover in the graph Question 3:Long paths in undirected graphs In this question m is the number of edges in an undirected graph. 1. Show that if the degree of every vertex is at least k, then the graph has a simple path of length at least k. Hint: consider the longest simple path in the graph say from x to y. Show that the endpoints x and y do not have edges to vertices outside the path. Thus all the neighbors of x, y are in the path. And recall that all degrees are at least k. 2. Show that every graph has a subgraph with minimum degree m. Hint: itera- tively remove all vertex of degree strictly smaller than m 3. Show that any graph has a path of length at least m. Use the two claims proven in the previous questions. Question 4: A tournament graph is a directed graph that has all edges uv, except that we either have the edge u Hvor v Hu (note that the number of edges is ). Indeed its as if we have n teams, and every pair of two teams plays one basketball game. If u lost to v, the tournament will have the edge u Hv. Clearly what we get is a tournament graph. Show that every tournament graph contains am Hamiltonian path. Hint: Induction will make the answer simple. Give an algorithm that finds an Hamiltonian path in a tournament Question 5: Say that the input has three numbers a, b, c. And we have an algorithm that runs in time at most 2-log a +1/3+ (log c)3. Does the algorithm run in polynomial time
