• ベストアンサー

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

離散数学　オイラーグラフ、ハミルトングラフの質問です。 添付データの画像のグラフについて考えています。 括弧の中に書いてあることが正しいのかと、このグラフはハミルトングラフであるか？ また、その理由を教えてください。 このグラフは位数（５）の（完全）グラフであり（４）次の（４-正則）グラフ ３辺形は（5Ｃ3＝　１０個） ４辺形は（5C4 * 2 = 10個) （すべての辺から偶数個の辺が出ているためオイラーグラフ）

画像を拡大する

質問者が選んだベストアンサー

  • ベストアンサー
  • R_Earl
  • ベストアンサー率55% (473/849)
回答No.1

> （すべての辺から偶数個の辺が出ているためオイラーグラフ） オイラーグラフの条件は 全ての「頂点」から偶数個の辺が出ている ではないでしょうか。 > このグラフはハミルトングラフであるか？ > また、その理由を教えてください。 ハミルトン閉路が存在すれば、 それだけで「ハミルトングラフである」と言えるはずですよね。 なので総当たりでもなんでも良いので、 とにかく1個ハミルトン閉路を見つけましょう。 今回のグラフの場合、 グラフをなぞってみるとすぐにハミルトン閉路が見つかります。

mottyomettyo
質問者

お礼

> （すべての辺から偶数個の辺が出ているためオイラーグラフ） 書き間違えていました。ご指摘ありがとうございます。 ハミルトングラフはよく分かっておらずＮＰ困難関係のものかと思い苦しんでいたので目からうろこの思いです。 試験問題の範囲なのですがおかげさまで助かりました。 素早い回答ありがとうございました。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 位数5のオイラーグラフの個数について

    情報学部 離散数学についての質問です。 位数5の、34個のグラフのうち、オイラーグラフは（2,2,2,2,2）,(4,4,4,4,4)の2つのみなのでしょうか。 自信が無く、担当の先生に質問しても無視されているため、どなたか教えて頂きたいです。

  • 情報数学　単純グラフの問題

    この中で2部グラフはどれか　５個 正則グラフはどれか　４個 補グラフが非連結になるグラフはどれか　３個 オイラーグラフはどれか　３個 辺を一本追加また削除するとオイラーグラフになるのはどれか　2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。

  • 情報数学　単純無向グラフについての問題

    この中で2部グラフはどれか　５個 正則グラフはどれか　４個 補グラフが非連結になるグラフはどれか　３個 オイラーグラフはどれか　３個 辺を一本追加また削除するとオイラーグラフになるのはどれか　2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。

  • 情報数学　単純グラフの問題

    この中で2部グラフはどれか　５個 正則グラフはどれか　４個 補グラフが非連結になるグラフはどれか　３個 オイラーグラフはどれか　３個 辺を一本追加また削除するとオイラーグラフになるのはどれか　2個 橋 (bridge) を持つグラフはどれか ２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。

  • 離散数学です

    離散数学なのですが 以下が成立することをべん図以外の方法で示せといわれたら、 どのように示せばいいのか、次の二つをやってみせてくれないですか？ 他にも同じような問題があるのですが、どのようにすればいいのかさっぱりなので (-д-；) 1 A⊆B →A∪(B-A)=B 2 A×(B∪C)=(A×B)∪(A× C) （×は直積を表す）

  • 離散数学の証明

    離散数学の証明 束に関する証明問題なのですがいまいち分かりません。 以下の問題を解いて解説していただけるとありがたいです。 おそらく吸収則や冪等則を用いるのだと思うのですが・・・ Lを束とする。このとき、任意のa,b,c,d∈Lに対して、次の(1)～(3)が成り立つことを示せ。 (1)a≦bならば、a＋c≦b＋c、かつ、a・c≦b・c (2)c≦aならば、（a・b）＋c≦a・（b＋c） (3)a＋（b・c）≦（a＋b）・（a＋c）

  • 離散数学の証明問題

    離散数学の証明問題 合同でないことを≡×と表します。 Pを素数とし、a≡×0(mod p)とする。また、aの位数をdとする。 このとき、次のことを示せ。 (1)整数nに対して、a^n≡1(mod p)であるならば、かつそのときに限り、d|n (2)dはp-1の約数である。 (3)整数i,jに対してa^i≡a^j　(mod p)であるならば、かつそのときに限り、i≡j(mod p) (1)はFermatの小定理を使うと思うのですが、いまいち解法が浮かびません。 (2)はFermatの小定理から自明に思えますが、厳密に証明しないといけないみたいです。 (3)は証明方法がまったく分かりません。 分かる方、証明お願いします。

  • グラフの証明を教えてください

    背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。

  • 数学のグラフの問題

    数学のグラフの問題について、解き方を教えてください。 問題分をそのまま記載します。 右の図(添付画像のことです)において、2点Ａ，Ｂの座標は、それぞれ（-1，4）　，（2，1）である。 また(1)は関数y＝ax＾2のグラフである。 2点Ａ，Ｂを通る直線の式はy＝-x+3である。 点Ｂを通りy軸に平行な直線と放物線(1)との交点をＣとする。直線ＡＣが直線ＯＢと平行になるとき次の問いに答えなさい 　aの値を分数で求めなさい。 解き方がさっぱりわかりません。できるだけ詳細に説明してもらえると助かります。 お願いします。

  • エクセルのグラフ作成に関して質問です。

    エクセルのグラフ作成に関して質問です。 エクセルで添付した画像のグラフを作成しました。 要望として、用紙1枚にデータ（数値）とグラフを入れるようにしました。 その為、データを折り返しています。 グラフを作成する上でグラフ上にある折り返したデータでは、グラフを作成することが出来ませんでした。 別シートに折り返しをしていないデータを別途作成し、そのデータを元にグラフを作成しています。 希望は叶えられているのですがすっきり出来ません。 グラフ上にある折り返しをしているデータだけで、グラフを作成することか可能でしょうか、出来るのであれば教えて頂きたいと思います。 希望は、添付した画像にこだわりません。 ただしデータも見やすく、グラフも入れてもシート1枚で完了し、印刷した際用紙一枚に全て収まるようにしたい。 前の質問に画像を入れる忘れました。改めて質問します。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する