Complete path of a decision tree

107 Views Asked by At

The task is to prove that a complete path starts at the root and ends at the leaf. For me is quite obvious, but I should write a mathematical proof, so, need some help with it. I found a definition: "A path is a sequence of moves such that at the end of a node of any move in the sequence is the start node of the next move in the sequence, excepting the last node in the sequence. A path is complete if it is not part of any longer path."

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose that a path $p$ starts at a node. If this node is not the root, then there is a move $m$ ending in it. Thus the path consisting of $m$ followed by $p$ is a longer path. Thus $p$ is not complete.

In the same way, if the end of $p$ is not a leaf, then there is a move $n$ starting from this end and the path consisting of $p$ followed by $n$ is longer. Thus $p$ is not complete.