正当性の証明：グラフ理論における木の直径のアルゴリズム

StackOverflow https://stackoverflow.com//questions/20010472

質問

ツリーの直径を見つけるために、ツリーから任意のノードを取り出すことができ、BFSを実行してそれから最も遠いノードを見つけてからそのノード上のBFSを実行します。2番目のBFから最大の距離は直径をもたらします。

私はこれを証明する方法はわかりません。ノード数で誘導を使用してみましたが、多くが多すぎます。

どんなアイデアも大いに感謝されるでしょう...

役に立ちましたか？

解決

最初のBFS Xによって見つけたエンドポイントを呼び出しましょう。決定的なステップは、この最初のステップで見つかったXが常に「機能」することを証明しています - つまり、それが常に一番長い経路の一端にあることを証明しています。 （一般的には1つ以上の等しいパスがある可能性があることに注意してください。）これを確立できる場合は、Xに根付いたBFSがXからできるだけ多くのノードを見つけることがわかります。最長パス

ヒント： 2つの頂点uとvの間の経路が長いと仮定して、どちらもx。

uとvの間の固有の経路では、頂点hの間の一意の経路であることを確認してください。 2つの可能性があります.HはBFSのルートからXへのパス上にあるか、そうではありません。両方の場合において、U - V経路は少なくとも長くすることができることを示すことによって矛盾を示す。

[編集] 実際には、結局のところ2つのケースを別々に扱う必要はないかもしれません。しかし、私はそれがいくつか（またはさえ多くの）ケースに構成を分割しやすく、それぞれを別々に扱うのが簡単にわかります。ここでは、BFSルートからXへの経路上にHが取り扱いが容易であり、他の場合に手がかりを与える。

[編集2] 後で考慮する必要がある2つのケースは（i）uvパスがルートからxへのパスと交差する2つのケースが私にあるようです（ 頂点yは必ずしもUV経路の最高点Hではありません。 （ii）ではありません。それぞれの場合を証明するにはまだHが必要です。

他のヒント

私は働くつもりです j_random_hackerのヒント。 s, tを最大限離れたペアにしましょう。 uを任意の頂点にしましょう。私たちは

のような模式を持っています 
    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,
.

ここで、xはs, t, u（すなわち、これらの頂点間の3つの経路のそれぞれにあるユニークな頂点）の接合部です。

vがuから最大離れた頂点であるとします。概略図が

のように見える場合 
    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,
.

それから

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),
.

ここで、d(u, t) = d(u, x) + d(x, t)とd(u, v) = d(u, x) + d(x, v)なので、不等式が保持されます。 vとsとxの間ではなく、xとtの間に添付されている対称的なケースがあります。

他のケースは

のように見えます 
    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .
.

今、

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),
.

SO max(d(v, s), d(v, t)) >= d(s, t)を平均化引数で、vは最大離れたペアに属します。

これを見る代替方法：

g =（ V 、 e ）頂点セットを備えた非控除性の有限の木である v とエッジセット e

次のアルゴリズムを考慮してください：

  1. count = 0をlet e の全てのエッジを最初に無色にします。 c は、最初は V に等しい。
  2. v のサブセット 'を考えてみてください。
    • v> 'が空の場合、 d = count * 2、停止します。
    • v 'の場合、それからそれらの相互（無色の）エッジ緑色をカラーにして、 d = count * 2 + 1、停止。
    • それ以外の場合、 V 'は少なくとも3つの頂点を含む。次のように進みます：
  3. increment count で1つ。
  4. 無色のエッジがない c からすべての頂点を取り除きます。
  5. v の各頂点に対して、2つ以上の露出しないエッジを持つ、それぞれの緑色のエッジを再色にします（一部の頂点はそのようなエッジがゼロになる可能性があります）。
  6. v 'の各頂点には、その色が無色のエッジグリーンを色します。
  7. 手順（2）に戻ります。

    8. 基本的には、葉からのグラフを内側に色し、緑色の葉まで最大距離の経路をマーキングし、赤の短い距離だけでマーキングします。一方、 C> の節点は、葉までの最大距離が短くなるまで、 c までの中心を解析する。最大距離が最大の葉に1つか2つのノードのみを含みます。

    建設では、緑色のエッジのみをトラバースした緑色の頂点から最寄りの中央の頂点へのすべての単純な経路は、同じ長さ（ count ）、および葉の頂点からのすべてのシンプルなパスへの頂点頂点（少なくとも1つの赤いエッジを横切る）は短いです。さらに証明することができます

    • このアルゴリズムは、 g のあらゆるエッジを赤または緑色のどちらかの範囲で残し、 c のあらゆるエッジを終了します。 1つか2つの要素で。
    • アルゴリズム終端時、 d は、e端で測定された g の直径です。
    • v> の頂点 v 、 g <の最大長さの単純経路/ strong> V から始まるのは、まさにセンターのすべての頂点を含み、葉で終了し、中央と遠端点の間の緑色のエッジのみを横断します。これらは中央を横切る v から、中心から最も遠い葉のうちの1つに行きます。

    今のアルゴリズムを考慮して、上記に照らしてもっと実用的かもしれません。任意の頂点 V から始めて、その頂点から単純なパス p が存在し、中央の頂点で終わる、そしてのすべての頂点を含む。中央（ G は木であり、 c に2つの頂点がある場合、それらはエッジを共有します） 。 g> の最大単純経路は、 V を有する v を有する P 中心から葉までの単純な経路が緑色の縁のみを横断します。

    私たちの目的のための重要なポイントは、他のエンドポイントの入ってくるエッジが必ずしも緑色です。したがって、そこから始まる最長パスの検索を実行すると、中央の緑色のエッジ（のすべての頂点）から別のリーフへの緑色のエッジのみを横断するものがあります。これらは正確に g の最大長の単純経路であるので、2番目の検索が実際にグラフの直径を明らかにすると確信している可能性がある。

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top