91影视

Consider that the spanning tree is a subset of a Graph $G$ that covers all of the vertices with the fewest number of edges feasible. It can be deduced from this definition that every linked and undirected Graph $G$contains at least one spanning tree

Consider the given input and output with $k鈮�2$.

Here, it is important to demonstrate that given a solution $S$ to the spanning tree problem that can be checked in polynomial time whether it is in fact a k-spanning tree. This comments to verifying that every node in the original graph is used in $S$ such that $S$ have no cycle because it is a tree.

Every node in the tree has a maximum degree $k$ . All of these can be checked efficiently and therefore the $k鈭�$ spanning tree is a search problem.

Therefore, it can be concluded that for $k鈮�2$, the $k鈭�$spanning tree is a search problem.

Any of a class of computer problems for which no efficient solution algorithm has been developed is known as an NP-complete issue.From part (a) it is known that the $k鈭�$spanning tree is in NP.

In the Rudrata path algorithm, assume $G$ is an unweighted undirected graph. Add weights equal to 1 on every edge of $G$ while executing the Rudrata path algorithm with $k=2$ .It is observed that a tree that has each vertex with a degree at most $2$ is a path. Hence, there is no path without loops that reaches all the vertices so there will be no Rudrata path.

Therefore, it can be concluded that the Rudrata path is reduced to a $k鈭�$spanning tree along with the fact that the $k鈭�$spanning tree is in NP.