[] -----> [N] -----> [N,P] fail | | | ---> [N,S] fail | ---> [P] -----> [P,Q] (to cover R) fail | ---> [P,R] succeed.
B. A state is a set S of vertices together with an index vertex W. (We have left the index vertex implicit in the diagram above.) An operation on the pair < S,W > is the pair < S union {U}, X > if U covers W, S union {V} is an independent set, and X is the successor to W in the list of vertices. The starting state is < [], first vertex >. The goal state is a set that covers all the vertices in G.
C. Let N = |V|, the number of vertices. Then D = N and B < = N. If the condition that vertices are added to K in alphabetical order is enforced, then the size of the state space is certainly no more than 2^{N}, the number of different subsets of V. As written the algorithm may rediscover the same state in many different ways, but the state space is certainly not larger than N!.
[N,P,Q,R,S] -----> [N,Q,R,S] -----> [N,R,S] fail | ---> [N,Q,S] ---> [Q,S] succeed.
B. A state is a set S of vertices together with an index edge E. An operation on the pair < S,E > is the pair < S - {U}, F > if both ends of E are in S, U is an end of E, S - {U} covers G, and F is the successor to E in the list of edges. The starting state is < V, first edge >. The goal state is a kernel set.
C. The depth D is the number of edges, but the number of branch points on any path from the root is no more than N (since you can only remove N vertices). The branching factor is 2. The size of the state space is less than 2^{N}