R. Clayton (rclayton@monmouth.edu)
Wed, 19 Apr 2000 17:25:29 -0400 (EDT)
In class we got W(To) >= W(T') and then drew the conclusion that W(T') is also
an optimal tree. However, I question that conclusion.
Yes, I botched that one, didn't I? Here's the logic behind the proof:
By assumption, the tree To is optimal, which means, for any other tree T',
w(To) <= w(T')
Now, if I can also show that w(To) >= w(T') holds, then I have
w(To) <= w(T') and w(To) >= w(T') -> w(To) = w(T')
that is, T' is also an optimal tree.
If To is an optimal tree, then it has minimum weight. However, by exchanging
two items x and b we arrive at a tree that has a lower weight
Stop right there: we arrive at a tree T' that has weight no greater than To,
which is not the same thing as a lower weight (or a weight less than).
It's the equal part of "greater than or equal to" that saves us.
This archive was generated by hypermail 2.0b3 on Wed Apr 26 2000 - 09:35:05 EDT