ここで言及されている木の直径を見つけるアルゴリズムはかなり前から知っていました。
しかし、なぜそれが機能するのですか？
可能であれば、 Ivanとcoprocの両方の回答を受け入れます。これらは 2 つの非常に異なるアプローチであり、どちらも私の質問に答えます。
と言うS = [A - B - C - D - ... X - Y - Z]のは木の直径です。
の各ノードを考えてみましょSう。たとえば@、そこから始めて、直径から「離れる」と、 よりも長いチェーンはありませんmin(length(@, A), length(@, Z))。
したがって、ツリーの任意のノードから dfs を実行すると、A「Z」または 'Z' で終了します。つまり、直径の一方の端です。そこから再び dfs を実行すると、もちろんツリーの反対側に移動します。
これを参照してください
手順 1 と 2 を完了し、S を見つけ、ツリーに S を含む直径がないとします。ツリーの直径 PQ を選択します。基本的に、考えられるケースを確認する必要があり、そのすべてにおいて、PS または SQ のいずれかが少なくとも PQ と同じ長さであることを確認する必要があります。これは矛盾します。
すべてのケースを体系的にチェックするために、ツリーのルートが A であると仮定できます。次に、任意の 2 つの頂点 U と V の間の最短パスを次の方法で計算します。W を U と V の共通の最下位の先祖とします。次に、 UV の長さは、U と W の間の距離と V と W の間の距離の合計に等しくなります。また、ルート ツリーでは、これらの距離はノードのレベルの違いにすぎません (このツリーでは、S は最大レベルを持ちます)。 ）。
次に、W をルートとするサブツリー (P と Q の最小共通祖先) および頂点 P と Q に関して、S が取り得るすべての位置を分析します。たとえば、最初のケースは単純です。S は、W をルートとするサブツリーにありません。 . 次に、P と Q のうちルートから遠い方を選択し、それを S に接続することで、パスを自明に改善できます。
このアルゴリズムは、任意の非巡回グラフ（ルートを持つという点で特別な非巡回グラフであるツリー）に対して機能します。
任意の2つの追加点S2とD2を選択し、それらの距離d（S2、D2）≤d（S、D）を示すことにより、証明を作成できます。私たちが知っているアルゴリズムから
最大5つのケースを区別することで（たとえば、パスSDとS2D2に共通のエッジがない、パスSDとS2D2に共通のエッジがあり、AがSにつながるエッジに接続されているなど）、上記を分解できます。サブパスに距離を置き、サブパスに基づいて不等式を書き換えます。結論は単純な代数から得られます。詳細は演習として読者に任されています。:-)
証明を始める前にいくつかの補題/事実.
|XY| も定義しましょう。パス X--Y の長さになります。
|XX| を定義する = 0。
アルゴリズムによって選択されたランダム ノードを A とします。ステップ 2 の後、最も遠いノードを P とします。P が S または D の場合、補題 2を使用して完了です。したがって、P は S または D のいずれかでなければならないことを示さなければなりません。
主張 : S--D が直径の場合、P は S または D のいずれかです。
証明: 対偶を証明することによって、上記を証明しようとしています。この証明は、一意の直径を持つツリーに対するものですが、一意でない直径に対してもマイナーな変更 (ほとんどの場合等値) で機能するはずです。
P が S でも D でもない場合、S--D は直径ではありません。
P は S でも D でもないと仮定します。
ケース 1: パス A--P が S--D と交差する
交点を K とします。BFS が P を A およびLemma 1から最も遠いノードとしてマークしたことがわかります。
|AP| > |AS| |AK| + |KP| > |AK| + |KS|
したがって、|KP| が得られます。> |KS|。
同様に |KP| > |KD|。
ここで、パス SP を考えます。
|SP| = |SK| + |KP| |SP| > |SK| + |KD| |SP| > |SD|
したがって、SP は直径よりも長いため、SD は直径ではありません。
ケース 2:パス A--P が S--D と交差しない
これで、BFS が P を最も遠いノードとしてマークしたことがわかりました。だから私たちは持っています
|AP| > |西暦| |AP| > |AS|
|AD| と書くことができます。= |AK| + |KD| ここで、K は直径の頂点の 1 つです (S と D を含む)。同様に |AS| = |AK| + |KS|.
一般性を失うことなく、|AD|>=|AS| と仮定します。
|AK| + |KD| >= |AK| + |KS| |KD| >= |KS|
ここで、パス PD を考えます
|PD| = |AP| + |西暦| |PD| = |AP| + |AK| + |KD| |PD| > |AP| + |KD| (|AK| > 0 は A が直径上にないため) |PD| > |KD| + |KD| (|AP| > |KD|) |PD| > |SK| + |KD| (|KD| >= |KS|) |PD| > |SD|
したがって、SD は直径ではなく、したがって主張です。
Set s がツリーの直径に沿ったノードを表し、A と Z が終了ノードであり、A から Z までの距離が直径であるとします。s のメンバーである任意のノード n について、n からの可能な最長パスは A または Z のいずれかで終了します。ここで、ツリー内のランダム ノード v を選択すると、それはセットのメンバーであるか、またはは、このセット内のノード n へのパスを持ちます。n からの最長パスは A または Z のいずれかであり、v から n へのパスは、n から A または n から Z へのパスのいずれよりも長くなることはできないため (そうである場合、v はセットのメンバーである必要があります)。次に、任意のノード V で BFS を実行すると、最初に A または Z が検出され、その後の呼び出しで補完的なエンドポイントが検出されます。数学の女の子ではなく、考えを捨てるだけです。