OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
締切り
済み

木の2つまたは3つの中心の求め方と証明(特に証明)

  • 困ってます
  • 質問No.169419
  • 閲覧数83
  • ありがとう数1
  • 気になる数0
  • 回答数6
  • コメント数0

お礼率 0% (0/6)

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

2.木の2つの中心の求め方
解.1.で求めた中心を通る線を取り、
  2つの木にする。
  その2つの木の中心(2つ)がそのまま解になります。

3.木の3つの中心の求め方
解.2.で求めた中心を通る線(2本)を取り、
  3つの木にする。
  その3つの木の中心(3つ)がそのまま解になります。

2.と3.の証明を教えてください。
通報する
  • 回答数6
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全6件)

  • 回答No.2
レベル14

ベストアンサー率 57% (1014/1775)

このご質問、言ってることめちゃくちゃですぜ。 ●そもそも、 > 定理。 > 1)木の中心は1点または2点からなり、2点の時にはそれらは隣接している。 ならば、3つの中心など存在しない。求める方法もない、ということになります。 ●それから、 >1.木の1つの中心の求め方 > 解.端点を削っていくやり方で求められます。 > 2.木の2つの中心の求め方 ...続きを読む
このご質問、言ってることめちゃくちゃですぜ。
●そもそも、
> 定理。
> 1)木の中心は1点または2点からなり、2点の時にはそれらは隣接している。
ならば、3つの中心など存在しない。求める方法もない、ということになります。

●それから、
>1.木の1つの中心の求め方
> 解.端点を削っていくやり方で求められます。
> 2.木の2つの中心の求め方
> 解.1.で求めた中心を通る線を取り、
  2つの木にする。
  その2つの木の中心(2つ)がそのまま解になります。

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

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

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


  • 回答No.1
レベル8

ベストアンサー率 33% (10/30)

n個の木の中心の正確な定義を教えてください。 概ね予想はつくのですが証明しろといわれると正確な定義が必要になります。 ...続きを読む
n個の木の中心の正確な定義を教えてください。
概ね予想はつくのですが証明しろといわれると正確な定義が必要になります。
補足コメント
dao_20d

お礼率 0% (0/6)

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

2.木の2つの中心の求め方
解.1.で求めた中心を通る線を取り、
  2つの木にする。
  その2つの木の中心(2つ)がそのまま解になります。

2.の証明を教えてください。

訂正。

3.は間違いです。2.の証明だけお願いします。

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

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

定理。

1)木の中心は1点または2点からなり、2点の時にはそれらは隣接している。
2)位数3以上の木Tからすべての端末点を除去してえられる木をT’とすると、
  Tの中心とT'の中心は一致する。
投稿日時 - 2001-11-17 19:26:43
  • 回答No.3
レベル8

ベストアンサー率 33% (10/30)

stomachmanさんの言うように、問題が変わっているのでしょうか? 例えば次のような木を考えたとき提示されているアルゴリズム通り 木の2つの中心を求めると 与えられた木 ●ー●ー●ー●ー●ー●ー● 1つの木の中心 ●ー●ー●ー◯ー●ー●ー● 1つの木の中心を通る線を取り2つの木にする。 ●ー●ー●・●・●ー●ー● それぞれの木の中心 ●ー◯ー●・●・●ー ...続きを読む
stomachmanさんの言うように、問題が変わっているのでしょうか?
例えば次のような木を考えたとき提示されているアルゴリズム通り
木の2つの中心を求めると

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

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


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

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


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

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

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

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

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

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

お礼率 0% (0/6)

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

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

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

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

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


他の例では、

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

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

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

    ↓

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

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

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

となります。
投稿日時 - 2001-11-19 05:56:14
  • 回答No.4
レベル8

ベストアンサー率 33% (10/30)

諸定義: 2点x、yに対し、これらを結ぶ最短道の長さをxとyの距離という。 点vからもっとも遠い点をvの離心点といい, vとvの離心点の距離をvの離心距離という。 点集合sと点vに対してsの要素の点とvの距離の最小値をsとvの距離という。 点集合sに対して距離が最も大きい点をsの離心点といい, sとsの離心点の距離をsの離心距離という。 要素数nの点集合の中で離心距離が最小になるよ ...続きを読む
諸定義:
2点x、yに対し、これらを結ぶ最短道の長さをxとyの距離という。
点vからもっとも遠い点をvの離心点といい,
vとvの離心点の距離をvの離心距離という。

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

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

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



という感じで複数の点からなる中心を定義してみました。
あってますか?
  • 回答No.5
レベル14

ベストアンサー率 57% (1014/1775)

どうも基本的なこと、つまり数学とは何かという所に誤解があるようにしか思えません。 というのはNo.2の補足、これはご質問の文章の舌足らずを補足し図解しただけのものです。これだけ読むと、ご質問の「解」が「1つの中心」「2つの中心」「3つの中心」の定義そのものということになり、従って証明は不要ってことになりますぜ。 ご質問は、3つの定理の証明を知りたいということですから、「1つの中心」「2つの中心 ...続きを読む
どうも基本的なこと、つまり数学とは何かという所に誤解があるようにしか思えません。

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

ご質問は、3つの定理の証明を知りたいということですから、「1つの中心」「2つの中心」「3つの中心」をそれぞれ、ご質問に記載の定理を使わずに定義なさらなくては話になりませんや。
  • 回答No.6
レベル11

ベストアンサー率 36% (175/474)

まったくよくわかりませんが、ちとお邪魔して。。。 ある木に対して中心が1つあるか2つあるかは、そもそも「木の形状に対して決定されているもの」であり、 その木に対して、#1の補足にある定理2)の操作を繰り返して行ったときに、最後に1点が残るか、2点が残るかのどちらかになって、それがその木の中心だっていう、それだけの話ではないのですか?! なんか問題がよくわからんすぎる・・・
まったくよくわかりませんが、ちとお邪魔して。。。

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

なんか問題がよくわからんすぎる・・・
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ