グラフ理論の問題(木について)

質問

次のことを証明せよ。
1.木の全ての最長路はその中心点を通過する。
2.木の最長路が1つ識別されると、木の中心が示される。

という問題です。
最長路の長さが偶数の場合と基数の場合に場合分けをしたとき

偶数の場合は両端の点から同じ距離にある点が中心点であり、
基数の場合は両端の点から同じ距離にあるような、隣接した2点が中心点になることを使うようなのですが、どのように使うのでしょうか。
また、なぜこうなるのでしょうか。

よろしくお願いします。

回答No.5

graphaffine · ベストアンサー

>また、なぜこうなるのでしょうか。

取敢えず、最長路の長さが偶数の場合を示してみる。「奇」数の場合はお任せします。

Tを木とし、Tが含む最長路Pの長さが偶数とする。Pの両端点をa,bとし、P上の点vをd(v,a)=d(v,b)のように取る。vがTの中心であることを示す。
Tの点xに対し、点xと、x以外の点の距離との最大値をM(x)と書くことにする。
このとき、示すべきことは、v以外のTの点wに対し、M(v)<M(w)である。
Pが最長路だから、d(v,a)=M(v)である。
(1)wが道P上の点の場合)wはaとvの間にあるとしてよい。このとき、d(w,b)=d(w,v)+d(v,b)>M(v)だから、M(v)<M(w)である。
(2)wが道P上にない点の場合)wに最も近いP上の点をzとする。z=vのときは明らかだからzとvは異なるとしてよい。このとき、zはaとvの間にあるとしてよい。
このとき、d(w,b)=d(w,z)+d(z,v)+d(v,b)>M(v)だから、M(v)<M(w)である。
(1),(2)より、主張が示された。

明示はしていないが、思いっきり木の性質を使ってます。その辺は大丈夫ですよね。

>「木の最長路が1つ指定されると、木の中心を求めることができる」と解釈しました。
これが示すべき命題ですか。本当に？
それとも、3+4は計算可能であることを示せ。(解）3+4は7である。従って、計算可能である（証明終了）と言うような話なの。

お礼

回答ありがとうございます。
この方法を参考にして、奇数のほうもやってみます。

問題の2については自信がないですが、
「両端点から同じ距離にある点が中心点である」ことを証明すると、同時に証明できるものではあると思います。

ちなみに原文を示しますと、"(Show that) the center of a tree can be located once a diametral path in the tree is discerned"です。

回答No.6

graphaffine

#5の証明で、「このとき、示すべきことは、v以外のTの点wに対し、M(v)<M(w)である。」
のM(v)<M(w)をM(v)≦<M(w)に訂正します。証明中の細かい手直しはお任せします。

>"(Show that) the center of a tree can be located once a diametral path in the tree is discerned"

直訳っぽく訳すと、「一旦木の最長路が指定されれば、木の中心を(その中に)位置づけられ得る」
要するに、木において、任意の最長路を取ったとき、その中に木の中心がありますよ。ということで、1と全く同じ意味になるんですが、何で2箇所で同じことを言ってるんだろう。

お礼

回答ありがとうございます。
木の中心は1つか2つであるという性質から、最長路の長さが偶数の場合は中心が1つなので、M(v)<M(w)をそのまま納得してしまったのですが、
そうするとそのことについても証明が必要になってしまいますよね。

"the center of a tree can be located"は「(最長路の中で)場所が一意に指定される」というような意味で解釈していたのですが、「最長路の中に存在する」という意味だったのですね。
1と全く同じ意味になってしまうことについてはちょっと分かりかねます・・

回答No.4

alice_44

てか、1. が「中心点」の定義なんじゃないの？

補足

ここで考えている中心点の定義は、「グラフの他点との間の距離の最大値が最も小さいような点」でした。

回答No.3

Tacosan

#1 は「この問題はこういうことを言いたんだろうなぁ」と推測したうえで, しかし中途半端に書いてます＞#2.
ナイーブにとれば, #2 でも「もし」以降に書かれているように 2 は自明. そうでない場合にはおそらく上の「推測」があっているはずで, その場合 1 を証明すれば (その方法にもよるけど) 2 はおまけでついてくるんじゃないかな.

たしかに推測で書いちゃダメですね. 反省.

回答No.2

graphaffine

>2.木の最長路が1つ識別されると、木の中心が示される。

この文章が分からない。「識別される」は指定されると解釈して、その後は
何を言ってるの。示されるとは、誰がどうやって何を示すの。

＃1の方、本当に自明ですか。中心の定義を知りたいと言うことには同意します。

もし、

>(最長路の長さが)偶数の場合は両端の点から同じ距離にある点が中心点であり、
>(最長路の長さが)基数の場合は両端の点から同じ距離にあるような、隣接した2点が中心点になることを使う

ならば、既に、最長路が中心を含むことは言えてることになるが、他に何を示す必要があるのでしょうか。

補足

確かにこの命題から最長路が中心点を通ることは明らかですね。失礼しました。

2については、よく読みなおした結果、「木の最長路が1つ指定されると、木の中心を求めることができる」と解釈しました。
この場合、1が証明できれば2も一緒に証明することができそうです。

回答No.1

Tacosan

「中心点」の定義が微妙に怪しい気はする. 英語の本だとしたら, もっときっちり読んだ方がいいかもしれない.

さておき, 2 は自明なので無視して 1 は背理法でいけそう.

補足

回答ありがとうございます。
おっしゃる通り英語の本です。
この本の中心点の定義は、「グラフの他点との間の距離の最大値が最も小さいような点」です。
とりあえず1を背理法で考えてみようと思います。