The following problem is known as the K-CLIQUE problem. You are given an undirected graph G...

   

Transcribed Image Text:

The following problem is known as the K-CLIQUE problem. You are given an undirected graph G with V vertices, and a number K < V. The goal is to find a set of K vertices are directly connected to each other in G. For instance, if the graph is the one shown below and K=4, then a solution is {B,D,G,H} A B E F G H I J A. How can you solve this problem using state space search? Give a precise description of the state space involved: What is a state, what is the successor to a state, what state, how do you recognize a goal state? The state space that you describe should be a tree. B. Do you know in advance the depth of the goal states? Which search algorithm would be best: DFS, BFS, or iterative deepening? C. Suppose that you have a graph G with V vertices and that no vertex in G has more than Q edges connected to it. That is, Q is the maximum number of edges that all co same vertex. In the graph in the diagram, vertex D has 6 edges connected to it, and no other vertex has more than 6, so Q=6. Give mathematical expressions in terms of th V, K, and Q for (i) the depth of your state space; (ii) the branching factor of the state space; (iii) an upper bound on the size of the state space. The following problem is known as the K-CLIQUE problem. You are given an undirected graph G with V vertices, and a number K < V. The goal is to find a set of K vertices are directly connected to each other in G. For instance, if the graph is the one shown below and K=4, then a solution is {B,D,G,H} A B E F G H I J A. How can you solve this problem using state space search? Give a precise description of the state space involved: What is a state, what is the successor to a state, what state, how do you recognize a goal state? The state space that you describe should be a tree. B. Do you know in advance the depth of the goal states? Which search algorithm would be best: DFS, BFS, or iterative deepening? C. Suppose that you have a graph G with V vertices and that no vertex in G has more than Q edges connected to it. That is, Q is the maximum number of edges that all co same vertex. In the graph in the diagram, vertex D has 6 edges connected to it, and no other vertex has more than 6, so Q=6. Give mathematical expressions in terms of th V, K, and Q for (i) the depth of your state space; (ii) the branching factor of the state space; (iii) an upper bound on the size of the state space.