JunKobayashi https://blog.hatena.ne.jp/JunKobayashi/ JunKobayashi's Diary https://junkobayashi.hatenablog.com/ 木の直径 前回の記事 junkobayashi.hatenablog.com に引き続き「木の直径」について整理していく。今回は「2頂点\(u,v\)が直径パスの2端点であると判明している時、木の頂点のうち任意の1つを\(x\)とすると、\(x\)から最も遠い頂点は必ず\(u,v\)のうちのどちらかである（すなわち、\(x\)から最も遠い頂点までの距離は\( \max \{ d(x,u) , d(x,v) \} \)である）」という性質が成立していることの証明を記載していく。 余談とも補足とも言い難い話 木の頂点の集合および木の直径パスの端点からなる集合をそれぞれ\(V,A\)とする。前回の記事で示した… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fjunkobayashi.hatenablog.com%2Fentry%2F2025%2F04%2F25%2F231829" title="木の直径に関しての勉強2：直径と最遠点の関係 - JunKobayashi&#39;s Diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/J/JunKobayashi/20250422/20250422005417.png Hatena Blog https://hatena.blog 2025-04-25 23:18:29 rich https://junkobayashi.hatenablog.com/entry/2025/04/25/231829 1.0 100%