柔軟に働き方を選ぶ時代に必要なこと >>

離散数学 オイラーグラフ、ハミルトングラフの質問です。

添付データの画像のグラフについて考えています。
括弧の中に書いてあることが正しいのかと、このグラフはハミルトングラフであるか?
また、その理由を教えてください。


このグラフは位数(5)の(完全)グラフであり(4)次の(4-正則)グラフ

3辺形は(5C3= 10個)
4辺形は(5C4 * 2 = 10個)

(すべての辺から偶数個の辺が出ているためオイラーグラフ)

「離散数学 オイラーグラフ、ハミルトングラ」の質問画像

このQ&Aに関連する最新のQ&A

A 回答 (1件)

> (すべての辺から偶数個の辺が出ているためオイラーグラフ)



オイラーグラフの条件は

全ての「頂点」から偶数個の辺が出ている

ではないでしょうか。

> このグラフはハミルトングラフであるか?
> また、その理由を教えてください。

ハミルトン閉路が存在すれば、
それだけで「ハミルトングラフである」と言えるはずですよね。
なので総当たりでもなんでも良いので、
とにかく1個ハミルトン閉路を見つけましょう。

今回のグラフの場合、
グラフをなぞってみるとすぐにハミルトン閉路が見つかります。
    • good
    • 0
この回答へのお礼

> (すべての辺から偶数個の辺が出ているためオイラーグラフ)
書き間違えていました。ご指摘ありがとうございます。

ハミルトングラフはよく分かっておらずNP困難関係のものかと思い苦しんでいたので目からうろこの思いです。

試験問題の範囲なのですがおかげさまで助かりました。

素早い回答ありがとうございました。

お礼日時:2010/08/13 13:55

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qハミルトングラフ

ハミルトングラフになるときって、頂点がn個で、任意の二つの点v,w隣接してないとき
deg(v)+deg(w)≧n
なんで、
つまり頂点vとwの次数の合計がn以上なら、成り立つんですよね?
でも閉路グラフC6の時って、どの頂点でも
2+2≦6
になるのにハミルトングラフなんですよね?
ハミルトングラフってどんなときになるんですか?

Aベストアンサー

>C6のように「deg(v)+deg(w)≦n」となる場合はどのように判断すればいいのでしょうか?
簡単に判断できる方法はないです。与えられたグラフがハミルトングラフかどうかを判定する問題は、NP完全問題の有名な例です。

もちろん、頂点数がN個のとき、N!通りの可能性を全てしらみつぶしに調べれば、ハミルトングラフかどうか判断できるわけですが。

Q全射の総数

|X|=4、|Y|=3であるとき、写像f:X→Yで全射になる写像の総数はいくらか

この回答は36なのですが、考え方が良くわかりません、誰か教えてください、お願いします

Aベストアンサー

 
  この問題に関しての回答でよいということなら記します。
 
  XとYは、要素の差が1しかありません。これがもっとたくさんだと、計算が複雑で解きにくいのですが、ここでは、差1なので、順列組み合わせの考え方を使います。
 
  Yの要素は3個ですから、これを三つの位置と考え、この位置に、Xの四つの要素を入れて行くことにします。この場合、Xの要素のどれか二つが、Yの同じ位置に入ることになります。そこで、Xの要素から二つを組み合わせる可能性の数を考えると、それは4・3で12ですが、これは順列でないので、2で割ると6が出てきます。
 
  Xの四個の要素のなかで、二つを選ぶと、残りの二個は自動的に決まります。つまり、6通りに分けて、それぞれ要素が違う三つの要素があると考えてよいのです。こう言っても分かりにくいかも知れませんから、具体的に、その6通りを以下に書いてみます。X={a,b,c,d}とします。
 
  ケース1){(a,b),c,d}
  ケース2){(a,c),b,d}
  ケース3){(a,d),b,c}
  ケース4){(b,c),a,d}
  ケース5){(b,d),a,c}
  ケース6){(c,d),a,b}
 
  これら6個のケースは、すべて要素が違う集合と考えても構いません。Yの三つの要素の位置に、これら6ケースごとで、三つの要素を入れて行く(対応させて行く)ことを考えると、これが、X→Yの全射になります。6個のケースで、三つの要素の順列を入れ替えても、6個のケースで、同じ、重複した順序はできません。
 
  従って、Yの三つの位置に対する順列を取ると、3・2・1=6で、これと、ケースの数6をかけると、6・6=36になり、これが、答えです。
 
  注記)六個のケースの三つの要素(二つの要素の組み合わせで、一つの新しい要素を造っていることに注意)の順列をどう入れ替えても、6個のケース全体で、同じ重複した組み合わせはできないというのがポイントです。「二重要素」を定義しているので、重複が排除されるのです。
 

 
  この問題に関しての回答でよいということなら記します。
 
  XとYは、要素の差が1しかありません。これがもっとたくさんだと、計算が複雑で解きにくいのですが、ここでは、差1なので、順列組み合わせの考え方を使います。
 
  Yの要素は3個ですから、これを三つの位置と考え、この位置に、Xの四つの要素を入れて行くことにします。この場合、Xの要素のどれか二つが、Yの同じ位置に入ることになります。そこで、Xの要素から二つを組み合わせる可能性の数を考えると、それは4・3で1...続きを読む

Qn角形の頂点をt色以下で塗り分けるグラフ彩色

http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2
によると、
隣接する頂点同士が同じ色にならないように全頂点に彩色する問題を頂点彩色という。
彩色多項式とは、与えられたグラフをt色以下で彩色したときの彩色の組合せ数を求める式である。

閉路グラフC_n(つまり、n角形)をt色以下で彩色したときの彩色多項式は、
(t-1)^n+(-1)^n*(t-1)

これがどのように示されるのかがわからないので、どうか教えていただけないでしょうか。

Aベストアンサー

>もし、正多角形の塗りわけで、隣り合う色が異なり、回転して同じ配色になると同じとみなす、ものの場合の数の公式や理論がありましたら紹介いただけるとありがたいです。

残念乍、関連する文献は存じません。が、単純に考えれば正n角形の360/n度の回転から生成される巡回群は、自然に正n角形に作用しますので、P(C[n],t)/nで求められるような気がするんですが。

なお、正方形に関しては、昔対称軸による折り返しまで含めて似たようなことを考えたことがあります。その場合は、4次の二面体群D4の自然な作用を考えることになるので、P(C[4],t)/8が求める結果でした。
nが大きい場合は、対称軸が増えるので結構ややこしくなりそうですね。

Q同値関係とは

同値関係について
教科書などを見ると
反射律、対象律、推移律の3つを満たすときに同値関係になるとかいてあるのですが、その意味がよくわかりません。

説明できる方がいらっしゃいましたら教えてください。よろしくお願いします。

Aベストアンサー

関係~について,

 反射律とは a~a を満たすこと
 対称律とは a~b ⇒ b~a を満たすこと
 推移律とは a~b,b~c ⇒ a~c を満たすこと

です。この3つをすべて満たすことを同値関係といい,
高校までに習った「同値」という概念の本質を端的に
言い表しています。

定義なのだから,そのまま認めればいいだけのことですが,
実感がつかみにくいなら,中学・高校で習った具体例を
あげるとよいでしょう。
例えば,線分の長さについて考えると
  AB=AB,
  AB=CD ⇒ CD=AB,
  AB=CD,CD=EF ⇒ AB=EF
が成り立ちますから,「線分の長さが等しい」という関係は
同値関係ですね。

大学の数学って,今まであいまいにしてきたことを,
スッキリさせてくれますよね。

Qカットセット

電気回路を学んでいる者です。
そこでひとつお尋ねしたいのですが、カットセットとはどういうものなのでしょうか?
ネットで調べてみても難しく、どうもよくわかりません。

どなたかお教えください。

Aベストアンサー

グラフGが連結であるとき、節点の集合Aを空でない集合A1とA2(=A-A1:AからA1を除いた節点集合)に分けるとき、A1とA2とをつなぐ枝の集合のことを言う。(平山博著:電気回路論より)

Q離散数学に関する問題 -二項関係、合成関係-

問(2)が分かりません
『以下の問に答えよ
問(1) A={ 1, 2, 3, 4, 5 }, B={ 1, 2, 3, 4 }とし、関数f : A → B を全射とする。 f に対して5×4行列Mを以下のように定める。
   M の第(i, j)要素 = 1 … f(i) = j のとき
   M の第(i, j)要素 = 0 … f(i) ≠ j のとき
この行列Mの一部の要素を空欄□に置き換えたものが下図(添付図)で表されたとする。
このMの空欄を全て埋めよ。

問(2) 集合A、Bは前問と同じとし、C={ 1, 2, 3 }とする。二項関係 S ⊂A×B と T⊂B×C を次のように定める。
   aSb <=> f(a) = b
   bTc <=> b > c+1
この時,関係Tを具体的に示せ。また、SとTを合成した二項関係 S○T を具体的に示せ。但し、合成関係 S○T は
   a(S○T)c <=> ある b∈B が存在して、aSb かつ bTc
によって定義される。 』

(1)は
関数f : A → B を全射としているので、行列M は
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
となる。
f(1)=2, f(2)=3, f(3)=4, f(4)=1, f(5)=2,

(2)は
S= { (1,2), (2,3), (3,4), (4,1), (5,2) }
T= { (3,1), (4,1), (4,2) }         (S、T に関して解答に自信がありません)

SとTを合成した二項関係 S○T が分かりません。
そもそもSとTを合成した二項関係 S○Tは存在するのでしょうか?

S○T の順序対は{ (2,1), (3,1), (3,2) } となると思います。

どなたか分かる方、教えていただけますと大変助かります。
どうかよろしくお願いします。

問(2)が分かりません
『以下の問に答えよ
問(1) A={ 1, 2, 3, 4, 5 }, B={ 1, 2, 3, 4 }とし、関数f : A → B を全射とする。 f に対して5×4行列Mを以下のように定める。
   M の第(i, j)要素 = 1 … f(i) = j のとき
   M の第(i, j)要素 = 0 … f(i) ≠ j のとき
この行列Mの一部の要素を空欄□に置き換えたものが下図(添付図)で表されたとする。
このMの空欄を全て埋めよ。

問(2) 集合A、Bは前問と同じとし、C={ 1, 2, 3 }とする。二項関係 S ⊂A×B と T⊂B×C を次のように定める。
   aSb ...続きを読む

Aベストアンサー

S= { (1,2), (2,3), (3,4), (4,1), (5,2) }
T= { (3,1), (4,1), (4,2) } 
書き換えると
1S2,2S3,3S4,4S1,5S2
3T1,4T1,4T2
この中でaSbかつbTcの形になってるものがあればそれがa(S○T)c


人気Q&Aランキング

おすすめ情報