ツリーをトラバースするコストはn-1
、n
ノードの数です。
すべてのツリーには正確にエッジがあるため、これは当てはまりますn-1
。すべてのノードにアクセスするには、それらすべてを使用する必要があります。
正確には、次の3つのステートメントは、ノードを持つグラフ T
と同等であることがわかっています。n
- Tはツリーです(サイクルなしで接続されています)
- Tは接続されており、n-1個のエッジがあります
- Tにはサイクルがなく、n-1個のエッジがあります
上記から、ツリーでは、すべてのノードに到達するために、すべてのエッジを使用する必要があると結論付けることができます(サイクルがないため、冗長なエッジがないため)-そしてn-1
それらは正確にあります。
編集:
あなたの例から、各エッジから戻る回数もカウントしているようです(つまり、一部のエッジは2回カウントされます)。
この場合、最適なソリューションは次のようになります。
cost = (n-1)*2 - height
説明/証明のガイドライン:
ツリーには正確にエッジ
があります。n-1
ルートから最も深いノードにつながるものを除いて、それぞれが正確に2回トラバースされます。
最後のブランチを除いて、各ノードから戻るため、各エッジ(上記を除く)を正確に2回使用する必要があります。
最後のブランチには正確にheight
エッジがあるため、合計でcost = (n-1)*2 - height
それは基本的にあなたが得たものと同じであることに注意してください:
height + 2*(n-1-height) = height + 2(n-1) -2height = 2(n-1) - height