木の直径の探索の正確性を証明します

順位表に登場すると、次のタスクに出くわしました。 互いに最大距離を持つツリーの2つの頂点を見つけるアルゴリズムを考え出し、その正当性を証明します。 その瞬間、木には直径、半径、その他多くのものがあることを基本的に知りませんでした。 テストの後、友人が私に教えてくれ、それがどんなアルゴリズムであるかを教えてくれたが、証拠はなかった。 それは私の頭が長い間詰まっているという証拠の問題でした。 いくつかの記事を読んだ後、私が自分ですべてを実際に指で説明するまで、資料が落ち着かないことが明らかになりました（おそらく読者もそれを好きになるでしょう）。 デマゴジーから本質に移りましょう。



ツリーの直径は、ツリー内の2つのピーク間の最大距離です。 検索アルゴリズムは、BFSの2つの開始で構成されます。 最初はツリーの任意の頂点から移動し、トラバーサル中に、現在の頂点から他のすべての頂点までの距離がカウントされます。 次に、それらから最もリモートのものが選択されます。 2回目のBFS起動は、それから行われます。 新しい距離がカウントされます。 それらの中で最大のものが直径になります。



なぜこの単純なアルゴリズムが正しく機能するのですか？



証明の落とし穴を避けるために、1つの頂点と2つの頂点からのツリーの場合についてすぐに説明します。 頂点が1つしかない場合、エッジはありません。最初のBFSは開始頂点の深さが最大であり、2番目の深さも報告します。 本質的にはこれが当てはまり、アルゴリズムは正しく機能します。 2つのピークがある場合、最初のラウンドは2番目のピークに到達し、2番目のピークは開始に到達します。これはこの場合に適しています。



最初に、目的の距離は2つのシート間の距離であることを理解します。 実際、見つかった最大パスの最後の頂点は葉ではありません。 同時に、仮定によって必要な距離を増やすことはできません。 ただし、これは、BFSが現在のピークの「背後にある」ピークにアクセスしなかったことを意味し、BFSの正確性と矛盾します。 見つかった両方の頂点が葉になることがわかります。 素晴らしい。



頂点vでツリーをぶら下げ、そこから最初の走査を開始します。



頂点v自体がリーフである別のケースを考えてみましょう。 直径の最初の端である場合、最初のBFSが2番目の端を見つけ、2番目が開始頂点に戻ることは明らかです。 そうしないと、直径はvを通過せず、3つ以上の葉を含むことができないため、「曲がり」ます。



直径とそれに対応する2つのピークを見つけましょう。 これらの頂点aとbのLCAを見つけ、この頂点をcと呼びます 。 明らかに、 D = d [a、c] + d [c、b]です。 実際、直径が最長パスに属している場合、直径は、ある頂点の2つの最も深いサブツリーの合計です。 ツリーの直径は、すべてのサブツリーの最大直径です。 幅の最初のウォークでは、深さの最大ピークが得られます（開始ピークで絞ったため）。 見つかったパスwの終わりの頂点を示します。 wが希望する最長パスに属することを証明しましょう。 直径を頂点cで「曲げ」 ます （2つの葉を接続し、葉は頂点vで吊り下げられているため「曲げ」ます）。 頂点wを頂点cのサブツリーの1つに属します 。 次に、パス（c、x）の一部を単純に置き換えます。ここで、 xは（c、w）で終わりの1つです。 d [c、x] <d [c、w]。 答えを改善しました。 したがって、元のパスは直径ではありませんでした。 wがcの祖先である場合、 wは葉ではないため、これは当てはまりません。 wが別のサブツリーのどこかにある場合、 e = LCA （c、w）とします。 d [w、e]は、サブツリーeの最大の深さです。 次に、 eはcの祖先なので、 d [x、e]> d [x、c]となります。 d [w、e]> d [y、e]> d [y、c] 。 したがって、 D0 = d [x、c] + d [y、c] <d [x、e] + d [w、e] = D つまり、最初は直径が誤って検出され、頂点wは直径に属します。



注：

証明のこの部分では、 wが属する特定のツリーのサブツリーでリーフwが最大の深さを持つというプロパティを使用しました。 帰納法で証明します。 ベースワンリーフw 。 明らかに、声明は真実です。 これが一部のサブツリーにも当てはまると仮定すると、1レベル上に移動します。 現在のサブツリーの深さがwよりも大きい頂点があるとします。 現在の頂点にa 、想定されるより大きな深さxを持つ頂点、ツリーのルートvに名前を付けます。

d [v、x] = d [v、a] + d [a、x];

d [v、w] = d [v、a] + d [a、w];

d [v、x] <d [v、w] BFSの正しい動作のため。

d [a、x]> d [a、w]仮定による。

その結果、矛盾が生じます。 したがって、頂点wは、どのサブツリーでも最大の深さを持ちます。



頂点wは直径に属し、その端の1つでもあることがわかります。 次に、 wから最も遠い頂点を見つけることだけが残っていることは明らかであり、これは2番目のBFSが行うことです。



記事を書くときに、次の資料が使用されました。

neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_ ％D0％BD％D0％B0_％D0％B4％D0％B5％D1％80％D0％B5％D0％B2％D1％8C％D1％8F％D1％85