人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

●質問者: shoronpoo
●カテゴリ:科学・統計資料
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● tea_cup

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

参考:

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

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

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


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

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ