(多分)グラフ理論に関係し、プログラムでグラフの数を求める質問です。

「N個の点があり、点に1からNまで数字がついている。各点の間に、線を引く引かないの2通りがある。ただし点1、点2の間には線を引かない。
この時、次の条件を満たすグラフを求めたい(a)点1と点2が他の線を通して繋がっている。(b)規約グラフである。(c)N個の頂点をもつ」
こんな感じの問題解き方の方針でも教えていただけると嬉しいです。よろしくお願いします

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2015/05/09 19:20:52
  • 終了:2015/05/16 19:25:05

回答(1件)

id:tea_cup No.1

tea_cup回答回数1026ベストアンサー獲得回数1842015/05/09 22:59:16

まず、「規約グラフ」でぐぐると「もしかして: 既約グラフ 」とサジェストされるので、「既約グラフ」でぐぐりなおして...と、中に出てくる言葉をつぎつぎたどって、判らないことが無くなったらその問題は解けています。

参考:

水素製造法 (1981年) (徳間文庫)

水素製造法 (1981年) (徳間文庫)

(作家ってすごいよね。)

id:shoronpoo

回答ありがとうございます。
既約グラフ説明すれば良かったです。
既約グラフではないグラフとは、各点から伸びているどの線を切ると複数のグラフにできるようなグラフです。
例を挙げます。線13,32,34,45,53がつながっているグラフは既約グラフではありません。なぜなら点3についてる4,5に向かう線を切ることで4,5を切り離すことができるからです。
線13,34,42,35,56,64がつながっているグラフは既約グラフです。なぜなら、点3で切っても分離できないからです。切る操作を考えるのは一つの点から伸びている線です。

もし何かまた分からないことがあればおっしゃってください

2015/05/10 18:14:35

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

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

トラックバック

  • 人力検索 今月の回答 バッテリー(電池)が「上がる」とはどんな状態なのでしょうか?「切れる(残量がなくなる)」とは違うのでしょうか? 液面が下がるのにバッテリー上がりとはこれ如
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

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

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