4
$\begingroup$

Let $T=(V, E')$ be a spanning tree of a graph $G=(V, E)$. Rather than verifying for any subset of vertices $S\subseteq V$ that $|E'(S)|=|S|-1$, is there an efficient way to satisfy the spanning tree constraint (as the complexity for calculating all vertices subsets is exponential)?

$\endgroup$
1
3
$\begingroup$

To confirm that $T$ is a tree, you need to confirm that (a) it is connected and (b) $\vert E'\vert = \vert V \vert - 1$. The second part is trivial. To confirm it is connected, start at an arbitrarily chosen node $v\in V$ and label all nodes adjacent to $v$ in $T$. For each freshly labeled node, label all unlabeled nodes adjacent to it and proceed recursively until you run out of nodes to process. If all nodes ended up labeled, $T$ is connected, and you are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.