algorithm - 正しさの証明: グラフ理論における木の直径のアルゴリズム

Question

ツリーの直径を見つけるには、ツリーから任意のノードを取得し、BFS を実行してそのノードから最も離れたノードを見つけ、そのノードで BFS を実行します。2 番目の BFS からの最大距離が直径になります。

私はこれを証明する方法がわかりませんか？ノード数の誘導を使用してみましたが、あまりにも多くの場合があります。

どんなアイデアでも大歓迎です...

Answer 1

最初の BFS x で見つかったエンドポイントを呼び出しましょう。重要なステップは、この最初のステップで見つかった x が常に「機能する」ことを証明することです。つまり、常に最長パスの一端にあることです。(一般に、同じ長さのパスが複数存在する可能性があることに注意してください。) これを確立できれば、x をルートとする BFS が x から可能な限り離れたノードを見つけることは簡単にわかります。最長パス。

ヒント: (逆に) 2 つの頂点 u と v の間に長いパスがあるとします。どちらも x ではありません。

u と v の間の一意のパス上に、いくつかの最高の (ルートに最も近い) 頂点 h がなければならないことに注意してください。2 つの可能性があります。h が BFS のルートから x へのパス上にあるか、そうでないかのいずれかです。どちらの場合も、パス セグメントの一部を x へのパスに置き換えることで、UV パスを少なくとも同じくらい長くできることを示すことで、矛盾を示します。

[編集]実際には、結局、2 つのケースを別々に扱う必要はないかもしれません。しかし、多くの場合、構成をいくつかの (または多くの) ケースに分割し、それぞれを個別に扱う方が簡単です。ここで、h が BFS ルートから x へのパス上にある場合の方が扱いやすく、他の場合の手がかりが得られます。

[編集 2]後でこれに戻ると、考慮する必要がある 2 つのケースは (i) uv パスがルートから x へのパスと交差する (頂点y で、必ずしも uv であるとは限りません)。パスの最高点 h); そして（ii）そうではありません。各ケースを証明するには、まだ h が必要です。