Remarks: In all algorithm, always prove why they work. ALWAYS, analyze the com- plexity of your algorithms. In all algorithms, always try to get the fastest possible. In all data structures, try to minimize as much as possible the running time of any operation. . Question 1: Let vi, v2... , Vn be an ordering of the vertices of an undirected graph G(V, E) on a line. Let Na(v) be the neighbors of v that appear after v in the line. The ordering is called a perfect elimination sequence if for every v, Na(v) is a clique (a clique is a graph such that an two vertices are neighbors) 1. Consider the following algorithm: While there are still vertices in the line, take the first (non deleted) vertex u in the line. Define a set uUNa(u) and remove this set and any edge touching a vertex from this set, from the graph. Then iterate. Show that the above algorithm decomposes the graph into a collection of cliques (namely every set un Na(u) is a clique) 2. Say that the above algorithm gives q cliques. Show that the maximum indepen- dent set in the graph has size at least q 3. Show that the maximum in dependent set is also of size at most q. 4. Show that that the algorithm find a maximum independent set in the graph. Remarks: In all algorithm, always prove why they work. ALWAYS, analyze the com- plexity of your algorithms. In all algorithms, always try to get the fastest possible. In all data structures, try to minimize as much as possible the running time of any operation. . Question 1: Let vi, v2... , Vn be an ordering of the vertices of an undirected graph G(V, E) on a line. Let Na(v) be the neighbors of v that appear after v in the line. The ordering is called a perfect elimination sequence if for every v, Na(v) is a clique (a clique is a graph such that an two vertices are neighbors) 1. Consider the following algorithm: While there are still vertices in the line, take the first (non deleted) vertex u in the line. Define a set uUNa(u) and remove this set and any edge touching a vertex from this set, from the graph. Then iterate. Show that the above algorithm decomposes the graph into a collection of cliques (namely every set un Na(u) is a clique) 2. Say that the above algorithm gives q cliques. Show that the maximum indepen- dent set in the graph has size at least q 3. Show that the maximum in dependent set is also of size at most q. 4. Show that that the algorithm find a maximum independent set in the graph