artak https://blog.hatena.ne.jp/artak/ あんまり見ないでください https://artak.hatenablog.com/ アルゴリズム グラフ 証明 非負の距離（重み）を持つ無向の木について，最も遠い頂点間の距離（最遠頂点間距離）を木の直径という．この直径を求めるアルゴリズムは意外と簡単だが，参考サイトの証明ではすっきりできなかったので，自分なりに証明を考えてみる．参考サイト：http://www.prefield.com/algorithm/graph/tree_diameter.html＜アルゴリズムの説明＞ 適当な頂点sを選び，sからの最遠頂点uを探索する．次にuからの最遠頂点vを探索する．このとき，(u,v)は木の最遠頂点対となっており，木の直径はuとvの距離と等しい．＜自分なりの証明＞ uが少なくとも一つの最遠頂点対に含まれること… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fartak.hatenablog.com%2Fentry%2F2014%2F02%2F20%2F114126" title="木の直径を求めるアルゴリズムの証明 - あんまり見ないでください" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/a/artak/20140220/20140220111143.png Hatena Blog https://hatena.blog 2014-02-20 11:41:26 rich https://artak.hatenablog.com/entry/2014/02/20/114126 1.0 100%