Editing Minimum spanning tree (section)

=== Decision trees ===
Given graph {{mvar|G}} where the nodes and edges are fixed but the weights are unknown, it is possible to construct a binary [[decision tree]] (DT) for calculating the MST for any permutation of weights. Each internal node of the DT contains a comparison between two edges, e.g. "Is the weight of the edge between {{mvar|x}} and {{mvar|y}} larger than the weight of the edge between {{mvar|w}} and {{mvar|z}}?". The two children of the node correspond to the two possible answers "yes" or "no". In each leaf of the DT, there is a list of edges from {{mvar|G}} that correspond to an MST. The runtime complexity of a DT is the largest number of queries required to find the MST, which is just the depth of the DT. A DT for a graph {{mvar|G}} is called ''optimal'' if it has the smallest depth of all correct DTs for {{mvar|G}}.

For every integer {{mvar|r}}, it is possible to find optimal decision trees for all graphs on {{mvar|r}} vertices by [[brute-force search]]. This search proceeds in two steps.

'''A. Generating all potential DTs'''
* There are <math>2^{r \choose 2}</math> different graphs on  {{mvar|r}} vertices.
* For each graph, an MST can always be found using {{math|''r''(''r'' – 1)}} comparisons, e.g. by [[Prim's algorithm]].
* Hence, the depth of an optimal DT is less than {{math|''r''{{sup|2}}}}.
* Hence, the number of internal nodes in an optimal DT is less than <math>2^{r^2}</math>.
* Every internal node compares two edges. The number of edges is at most {{math|''r''{{sup|2}}}} so the different number of comparisons is at most {{math|''r''{{sup|4}}}}.
* Hence, the number of potential DTs is less than

<math>{(r^4)}^{(2^{r^2})} = r^{2^{(r^2+2)}}.</math>

'''B. Identifying the correct DTs'''
To check if a DT is correct, it should be checked on all possible permutations of the edge weights.
* The number of such permutations is at most {{math|(''r''{{sup|2}})!}}.
* For each permutation, solve the MST problem on the given graph using any existing algorithm, and compare the result to the answer given by the DT.
* The running time of any MST algorithm is at most {{math|''r''{{sup|2}}}}, so the total time required to check all permutations is at most {{math|(''r''{{sup|2}} + 1)!}}.

Hence, the total time required for finding an optimal DT for ''all'' graphs with {{mvar|r}} vertices is:<ref name=PettieRamachandran2002/>
:<math>2^{r \choose 2} \cdot r^{2^{(r^2+2)}} \cdot (r^2+1)!,</math>
which is less than
:<math>2^{2^{r^2+o(r)}}.</math>

{{See also|Decision tree model}}