離散数学です。


「4個以下の節点からなる異なる(同型でない)有向木をすべて挙げよ。」

これの解説、または参考になるサイトを教えてください。
解答のみは不可です。(教科書の後ろに解答は載っているため)

わかり次第終了します。

宿題は月曜日までなのですが、思わず友達に聞くのを忘れてしまい、週末になってしまいましたorz

回答の条件
  • 1人2回まで
  • 登録:2006/11/17 21:50:46
  • 終了:2006/11/18 14:18:59

ベストアンサー

id:Z9M9Z No.1

Z9M9Z回答回数343ベストアンサー獲得回数112006/11/18 10:20:04

ポイント50pt

まず無向木で挙げてみましょう。木、つまりループなしですから、

2節は O-O 

3節は O-O-O

4節は O-O-O-O か

    O-O-O

      |

      O

の4通りとなります。で、有向木ですが、

2節は O>O これだけですね。左右取り替えても同型ですから。

3節は O-O-O この2つのリンクが右ばかり・内向き・外向きの3通り。

4節の直線パターン O-O-O-O も、同様に、中央を右向き固定して、両側が右ばかり・内向き・外向きの3通り。

O>O>O>O O>O>O<O O<O>O>O

3腕の4節のパターンは、中央の節を基準にして、そこから全外むき・1つ内・2つ内・そこへ全内むきの4通り。

以上です。たぶん。

id:shun262

ありがとうございます。

ちなみに答えは

2節点:1

3節点:3

4節点:8

と書いています。

id:Z9M9Z4さんの答えは4節は7通りしか書いていないようですが、どうなんでしょう。

2006/11/18 12:25:47

その他の回答(2件)

id:Z9M9Z No.1

Z9M9Z回答回数343ベストアンサー獲得回数112006/11/18 10:20:04ここでベストアンサー

ポイント50pt

まず無向木で挙げてみましょう。木、つまりループなしですから、

2節は O-O 

3節は O-O-O

4節は O-O-O-O か

    O-O-O

      |

      O

の4通りとなります。で、有向木ですが、

2節は O>O これだけですね。左右取り替えても同型ですから。

3節は O-O-O この2つのリンクが右ばかり・内向き・外向きの3通り。

4節の直線パターン O-O-O-O も、同様に、中央を右向き固定して、両側が右ばかり・内向き・外向きの3通り。

O>O>O>O O>O>O<O O<O>O>O

3腕の4節のパターンは、中央の節を基準にして、そこから全外むき・1つ内・2つ内・そこへ全内むきの4通り。

以上です。たぶん。

id:shun262

ありがとうございます。

ちなみに答えは

2節点:1

3節点:3

4節点:8

と書いています。

id:Z9M9Z4さんの答えは4節は7通りしか書いていないようですが、どうなんでしょう。

2006/11/18 12:25:47
id:Z9M9Z No.2

Z9M9Z回答回数343ベストアンサー獲得回数112006/11/18 13:41:04

ポイント15pt

O-O-O-Oで左ばかり、O<O>O<O が抜けてました。(_ _;)

id:shun262

ありがとうございます

2006/11/18 14:17:43
id:kronecker No.3

kronecker回答回数88ベストアンサー獲得回数102006/11/18 13:31:14

ポイント15pt

O<O>O<Oが抜けてるかな。これで8通りでしょう。

id:shun262

ありがとうございます

2006/11/18 14:18:01

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません