(メモ) 木の中心と直径について
証明を書いていたら迷子になってしまった
— ゆらふな (@yurahuna) 2016年7月18日
なのでツイートだけ貼り付けておきます。ごめんね。
参考にしたpdf: http://www.cs.columbia.edu/~cs4203/files/GT-Lec4.pdf
【中心がただ1つ or 隣接する2頂点 になることの略称】
— ゆらふな (@yurahuna) 2016年7月18日
木Tの頂点数をnとする。
n = 1, 2 のときは明らか。
n >= 3 のとき、Tの葉をすべて削除した木をT*とすると、T*における各頂点の離心数(最遠点までの距離)はちょうど1下がる。(続)
よって中心の集合はTとT*で一致する。n >= 3 のとき葉でない頂点が必ず存在するので、葉をすべて削除するという操作を繰り返すとn = 1, 2 に帰着される。(終)
— ゆらふな (@yurahuna) 2016年7月18日
【「葉をすべて削除すると離心数が1ずつ下がる」の略証】
— ゆらふな (@yurahuna) 2016年7月18日
ある頂点vからの最遠点u は必ず葉である(葉でないとすると次の頂点にパスを伸ばせて、最遠という仮定に反する)。操作により距離d_vuの点はすべて削除され、一方でuから1歩だけ戻ったu'がT*に存在する。よってちょうど1下がる
「n >= 3 のとき中心は葉でない」が抜けていた(これは次数の総和より示せる)
— ゆらふな (@yurahuna) 2016年7月18日
葉をすべて削除するというアルゴリズムに則れば、「任意の最遠点対について(u, v)について、パスP_uvは中心を通る」は簡単っぽい。葉が両側から削られていくから。これにより「Dが偶数(奇数) ⇒ 中心が1つ(2つ)」も言える。逆はどう示すか？
— ゆらふな (@yurahuna) 2016年7月18日
でも確かに、「Dが偶数(奇数) ⇒ 中心が1つ(2つ)」が示されていて、Dは偶数または奇数、中心は1個または2個なのだから対偶を取れば逆は一瞬だった
— ゆらふな (@yurahuna) 2016年7月18日
証明を理解するのと記述するのはまた別なスキルな気がした。
