Task 2: Maximal Independent Set Problem Warmup: Adjacency Lists Adjacency matrices are cumbersome to specify manually. An alternative representation for graphs are adjacency lists where we give the neighbours of each vertex directly as a list of vertices (indices) and gather all these lists of neighbours in order of the vertices that they belong to into a single container list. For example: >>> lec-graph [ [2, 4, 5, 6, 7], [2, 3, 5, 6, 7], [0, 1, 6, 7], [1, 4, 7], [0, 3, 6] , [0, 1], [0, 1, 2, 4, 7], [0, 1, 2, 4, 7]] Write a function adjacency matrix(adj-lists) that accepts an adjacency list of a graph as input and outputs the adjacency matrix representation of the same graph. For example: >>> adjacency_matrix(lec-graph) [ [0, 0, 1, 0, 1, 1, 1, 1], [0, 0, 1, 1, 0, 1, 1, 1], (1, 1, 0, 0, 0, 0, 1, 1], [0, 1, 0, 0, 1, 0, 0, 1], (1, 0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0, 0, 0], (1, 1, 1, 0, 1, 0, 0, 1], (1, 1, 1, 0, 1, 0, 0, 1] ] Extension: In case, this was too easy, can you write the function using a single list comprehension? Part A: Independent Sets Recall the definition of an independent set from the lecture slides: A set of vertices X is called an independent set of a graph G=(V, E) if for all contained pairs v, w from X there is no edge (U, w) in E" Write a function is_indset (adj.lists, x) that accepts as input the adjacency lists of a graph and a collection of vertices x and returns as output whether x is an independent set in the given graph. For example: >>> is_indset(lec-graph, []) True >>> is_indset(lec-graph, [5]) True >>> is_indset(lec-graph, [0, 2]) False >>> is_indset(lec-graph, [6, 5, 3]) True Part B: Greedy Maximisation Write a function greedy-indset (adj list) that accepts as input the adjacency list of a graph and produces as output a greedy approximation to a maximum independent set. In particular, your strategy should be good enough to find an optimal independent set for our example graph, i.e., you should get: >>> x = greedy_indset (lec-graph) >>> is_indset(lec-graph, x) True >>> len(x) 3 Describe the greedy strategy you are using inside the docstring of your function. Bonus: Counter Example (Not Assessed) Construct an adjacency list of a graph for which your greedy algorithm does not produce an optimal solution. Store this counter example under the variable name counter-ex in your module. Also, as proof that the greedy algorithm fails, store under the variable name opt a collection of vertices that represents a maximal independent set in your graph. That is, in the end, you should have the following behaviour: >>> is_indset(countr_ex, opt) True >>> len(greedy_indset (countr_ex)) >> lec-graph [ [2, 4, 5, 6, 7], [2, 3, 5, 6, 7], [0, 1, 6, 7], [1, 4, 7], [0, 3, 6] , [0, 1], [0, 1, 2, 4, 7], [0, 1, 2, 4, 7]] Write a function adjacency matrix(adj-lists) that accepts an adjacency list of a graph as input and outputs the adjacency matrix representation of the same graph. For example: >>> adjacency_matrix(lec-graph) [ [0, 0, 1, 0, 1, 1, 1, 1], [0, 0, 1, 1, 0, 1, 1, 1], (1, 1, 0, 0, 0, 0, 1, 1], [0, 1, 0, 0, 1, 0, 0, 1], (1, 0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0, 0, 0], (1, 1, 1, 0, 1, 0, 0, 1], (1, 1, 1, 0, 1, 0, 0, 1] ] Extension: In case, this was too easy, can you write the function using a single list comprehension? Part A: Independent Sets Recall the definition of an independent set from the lecture slides: A set of vertices X is called an independent set of a graph G=(V, E) if for all contained pairs v, w from X there is no edge (U, w) in E" Write a function is_indset (adj.lists, x) that accepts as input the adjacency lists of a graph and a collection of vertices x and returns as output whether x is an independent set in the given graph. For example: >>> is_indset(lec-graph, []) True >>> is_indset(lec-graph, [5]) True >>> is_indset(lec-graph, [0, 2]) False >>> is_indset(lec-graph, [6, 5, 3]) True Part B: Greedy Maximisation Write a function greedy-indset (adj list) that accepts as input the adjacency list of a graph and produces as output a greedy approximation to a maximum independent set. In particular, your strategy should be good enough to find an optimal independent set for our example graph, i.e., you should get: >>> x = greedy_indset (lec-graph) >>> is_indset(lec-graph, x) True >>> len(x) 3 Describe the greedy strategy you are using inside the docstring of your function. Bonus: Counter Example (Not Assessed) Construct an adjacency list of a graph for which your greedy algorithm does not produce an optimal solution. Store this counter example under the variable name counter-ex in your module. Also, as proof that the greedy algorithm fails, store under the variable name opt a collection of vertices that represents a maximal independent set in your graph. That is, in the end, you should have the following behaviour: >>> is_indset(countr_ex, opt) True >>> len(greedy_indset (countr_ex))