The "Best Independent Set" problem is defined as follows: Input: An undirected graph G, in which each vertex is marked by a positive value ; and a target value T. Goal: A set of vertices S such that (a) no two vertices in S are connected by an edge in G; and (b) the total value of the vertices in S is at least T. For instance, in Graph 1 below, with T=16, there are three solutions: { C,D },{ A,E }, and {B,E} In Graph 2, with T=21 the only solution is {G,H,K} The N-Queens problem is actually a special case of this, with the vertices being the squares on the chess board, an edge between two vertices if the squares attack, all vertices have value 1 , and the target value is N. Problem 1 Consider the following state space for systematically solving the problem: State: A set of vertices, no two of which are connected by an edge. Successor to state S : Add some vertex V to S such that (a) V is alphabetically later than the vertices in S (to guarantee systematic search); (b) V is not connected to any vertex in S. Start state: The empty set. Goal state: A state that attains the target value. Show the part of the state space that would be generated if you use depth-first search in this state space to find the solution to graph 2 with T=21. You should show this as a tree. I recommend drawing trees for assignments left-to-right typewriter format like this: If you want to use graphics software to make a nice looking tree, that's even better, though more work for you. If you want to draw it out and photograph it, that's OK, though less preferred