木の２つまたは３つの中心の求め方と証明(特に証明）

１．木の１つの中心の求め方
解．端点を削っていくやり方で求められます。

２．木の２つの中心の求め方
解．１．で求めた中心を通る線を取り、
　　２つの木にする。
　　その２つの木の中心（２つ）がそのまま解になります。

３．木の３つの中心の求め方
解．２．で求めた中心を通る線(２本）を取り、
　　３つの木にする。
　　その３つの木の中心（３つ）がそのまま解になります。

２．と３．の証明を教えてください。

No.1 ベストアンサー 回答者： nagata 回答日時： 2001/11/16 14:29

n個の木の中心の正確な定義を教えてください。

概ね予想はつくのですが証明しろといわれると正確な定義が必要になります。

この回答への補足

１．木の１つの中心の求め方
解．端点を削っていくやり方で求められます。

２．木の２つの中心の求め方
解．１．で求めた中心を通る線を取り、
　　２つの木にする。
　　その２つの木の中心（２つ）がそのまま解になります。

２．の証明を教えてください。

訂正。

３．は間違いです。２．の証明だけお願いします。

一般の連結グラフGに対して中心の定義。

Gの2点ｘ、ｙに対し、これらを結ぶ最短道の長さをｘとｙの距離といい、
点ｖからもっとも遠い点までの距離をｖの離心点といい、
離心点が最小となる点をグラフの中心という。

定理。

１）木の中心は1点または2点からなり、2点の時にはそれらは隣接している。
２）位数3以上の木Tからすべての端末点を除去してえられる木をT’とすると、
　　Tの中心とT'の中心は一致する。

補足日時：2001/11/17 19:26

No.2 回答者： stomachman 回答日時： 2001/11/18 11:54

このご質問、言ってることめちゃくちゃですぜ。

●そもそも、
> 定理。
> １）木の中心は1点または2点からなり、2点の時にはそれらは隣接している。
ならば、３つの中心など存在しない。求める方法もない、ということになります。

●それから、
>１．木の１つの中心の求め方
> 解．端点を削っていくやり方で求められます。
> ２．木の２つの中心の求め方
> 解．１．で求めた中心を通る線を取り、
　　２つの木にする。
　　その２つの木の中心（２つ）がそのまま解になります。

ちょっと待ったあ！二つの中心を持つ木がどうしてまた同時に一つの中心を持つんでしょうね？たとえば、２点を１本のarcで結んだだけの木を考えて見てくださいな。この木は２個の中心を持つけれど、１つの中心は持たない。

●さらに申し上げるなら、これは無向グラフの木だと思われますけれど、
・Arc（edge、つまり点(node)を結ぶ線）に長さが与えられているのか、それとも単にarcの数を距離と言っているのか。

ちゅう訳で、問題を改変してません？あるいは定義をきちんと書いてない？

No.3 回答者： nagata 回答日時： 2001/11/18 18:39

stomachmanさんの言うように、問題が変わっているのでしょうか?

例えば次のような木を考えたとき提示されているアルゴリズム通り
木の2つの中心を求めると

与えられた木
●ー●ー●ー●ー●ー●ー●

1つの木の中心
●ー●ー●ー◯ー●ー●ー●


1つの木の中心を通る線を取り2つの木にする。

●ー●ー●・●・●ー●ー●


それぞれの木の中心
●ー◯ー●・●・●ー◯ー●

2つの木の中心
●ー◯ー●ー●ー●ー◯ー●

てなりますよね。
ある意味これも中心と呼べなくはない気もしますが、
2つの木の中心はこれで良いんでしょうか。

この路線でいくと3つの木の中心というのも定義できて

3つの木の中心
●ー◯ー●ー◯ー●ー◯ー●

という感じでしょうか。
提示されているアルゴリズムと中心の定義が食い違ってる?

この回答への補足

ごめんなさい。
説明不足です。

補足すると、1つの木の中心を通る線を、ひ・と・つ、取り2つの木にする。
このひとつというのは1つの辺を取り、2つの木にしたとき、共に最遠点までの距離がもっとも短くなるようになる辺です。

まだ、説明不足かもしれません。
その都度、突っ込んでください。

木の1つの中心
○ー○ー●ー○ー○
　　　　↓
○ー○ー●　○ー○　または　○ー○　●ー○ー○
（このばあい、どちらでもよい（どちらも同じ）
　　　　↓
○ー●ー○　●ー○　または　○ー●ー○　○ー●
●ー○　○ー●ー○　または　○ー●　○ー●ー○
（どれも同じ）

よって、この木の2つの中心は
○ー●ー○ー○ー●　または　○ー●ー○ー●ー○


他の例では、

○┐　　　　　　　┌○
　　○ー○ー○ー○
○┘　　　　　　　└○
　　　　↓

○┐　　　　　　　┌○
　　○ー●ー○ー○
○┘　　　　　　　└○
　　
中心についている辺のうちとる辺はこのばあい、右なので
（左をとると最遠点までの距離が２（左の木）と、３（右の木）となり、
　右をとると最遠点までの距離が２（左の木）と、２（右の木）となるから）

　　　　↓
○┐　　　　　　　　　┌○
　　○ー●　と　○ー○
○┘　　　　　　　　　└○

　　　　↓

○┐　　　　　　　　　┌○
　　●ー○　と　○ー●
○┘　　　　　　　　　└○

よって、この木の2つの中心は

○┐　　　　　┌○
　　●ー○ー●
○┘　　　　　└○

となります。

補足日時：2001/11/19 05:56

No.4 回答者： nagata 回答日時： 2001/11/19 20:20

諸定義：

2点ｘ、ｙに対し、これらを結ぶ最短道の長さをｘとｙの距離という。
点vからもっとも遠い点をvの離心点といい,
vとvの離心点の距離をvの離心距離という。

点集合sと点vに対してsの要素の点とvの距離の最小値をsとvの距離という。
点集合sに対して距離が最も大きい点をsの離心点といい,
sとsの離心点の距離をsの離心距離という。

要素数nの点集合の中で離心距離が最小になるような点集合をグラフのn個の中心という。

n個の中心とその中心の離心距離をn個の中心の半径という。



という感じで複数の点からなる中心を定義してみました。
あってますか?

No.5 回答者： stomachman 回答日時： 2001/11/20 01:20

どうも基本的なこと、つまり数学とは何かという所に誤解があるようにしか思えません。

というのはNo.2の補足、これはご質問の文章の舌足らずを補足し図解しただけのものです。これだけ読むと、ご質問の「解」が「１つの中心」「２つの中心」「３つの中心」の定義そのものということになり、従って証明は不要ってことになりますぜ。

ご質問は、３つの定理の証明を知りたいということですから、「１つの中心」「２つの中心」「３つの中心」をそれぞれ、ご質問に記載の定理を使わずに定義なさらなくては話になりませんや。

No.6 回答者： kony0 回答日時： 2001/11/20 11:37

まったくよくわかりませんが、ちとお邪魔して。

。。

ある木に対して中心が１つあるか２つあるかは、そもそも「木の形状に対して決定されているもの」であり、
その木に対して、#1の補足にある定理2)の操作を繰り返して行ったときに、最後に１点が残るか、２点が残るかのどちらかになって、それがその木の中心だっていう、それだけの話ではないのですか？！

なんか問題がよくわからんすぎる・・・