締切済み

ハミルトングラフ

2007/12/23 12:12

グラフ理論の証明なのですが、単純グラフＧについて、ｃ(Ｇ)をＧの閉包とするとＧがハミルトン⇔ｃ(Ｇ)がハミルトン (⇒)は明らかですが (十分条件)の証明がわかりません。十分条件の証明を教えてください。よろしくお願いします。

m0m0nnga
お礼率100% (1/1)

数学・算数
回答数1
ありがとう数1

みんなの回答 （1）
専門家の回答

みんなの回答

rabbit_cat
ベストアンサー率40% (829/2062)

2007/12/23 12:16 回答No.1

http://planetmath.org/?op=getobj&from=objects&id=6466 証明自体はそんなに難しくないです。

質問者

お礼 2007/12/24 13:08

ありがとうございます。英語ですね…がんばります！

関連するQ&A

ハミルトングラフの証明

単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加したグラフG'もハミルトングラフである。これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。なにかうまい証明方法があればお教えください。回答、よろしくお願いします。
ハミルトングラフ

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

「二部グラフＧに奇数個の点があるとき、Ｇはハミルトン・グラフでない」ことを証明してください。お願いしますm(__)m
離散数学　オイラーグラフ、ハミルトングラフの質問です。

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

点数nが３以上で、最小次数がn/2以上であるグラフGはハミルトン閉路を持つことを示したい１，Gの最長路P＝X0X1・・・・Xkを考える　　（X0,Xi+1)がE(G)に含まれる、(Xi,Xk)がE(G)に含まれる　　となるようなiが存在することを示せ２，上記iに対して、　　閉路 Xi,Xi+1,Xi+2・・・・・,Xk,Xi,Xi-1,・・・・・,X0 　　がハミルトン閉路であることを示せという問題が出てしまいました正直証明とか苦手でどうやって手を付けたらいいかわからないので教えてください！よろしくお願いします。
グラフ理論

K1,3のグラフとハミルトングラフと切断点の３つの条件を持たないようなグラフは存在するのですか？もし、するならばどういう特徴を持っているのでしょうか？ハミルトングラフでないグラフは定理がないので調べようがないので困っています・・・よろしくお願いします
グラフ理論の問題について

グラフ理論についての質問です。よろしくお願いします。「グラフGが正則でdiam(G)=3ならば、diam(~G)=2である」（~GはGの補グラフです）を証明したいです。前の設問に「diam(G)≧3ならばdiam(~G)≦3」というのがあるので（これは証明できました）、diam(~G)=1あるいはdiam(~G)=3の場合に矛盾を導く方向で考えています。 diam(~G)=1とするとGが空グラフになってしまう、というのは分かるのですが、diam(~G)=3の場合に矛盾を導くところが上手くいきません。どのような方針で話を進めていけば良いのか、あるいはストレートにdiam(~G)=2を示すもっとスマートな方法があるのか、ご教示いただければ幸いです。
グラフの証明を教えてください

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

グラフ理論についての質問です。よろしくお願いします。「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」を証明したいです。「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。（最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました）また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？以上になります。ご教示いただければ幸いです。
グラフ理論の問題

ちょっとした定理なのですが… Vを頂点集合としてKをVの部分集合とする。KがグラフGのクリークをなすための必要十分条件は、V-K がGの補グラフG^の頂点被覆になることである。図で証明は出来るのですが、数式ではキビシい感じなんです。これは一体どうすれば宜しいのでしょうか？
ハミルトン閉路とNP

ハミルトン閉路問題はNPに属する、という事を証明したいのですが… これって　HCがPに属することを証明すれば良いのでしょうか？ちょっと迷走しちゃってます…
【グラフ理論】証明問題が分かりません。【難問】

テストに向けてグラフ理論の勉強をしているのですが・・・下記の証明問題で行き詰まってしまいました。『uv ∉ E(G) → uw ∉ E(G)というグラフは完全K部グラフしか存在しない事を証明せよ。』当方、証明問題に滅法弱く、どう解けば良いのか方針すら分かりません。方針や証明の過程など詳しくご教授して頂ければ幸いです。何卒宜しくお願い致します。
グラフ理論の問題についての質問です

大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題：グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。よろしければこの問題の証明方法を教えてください。よろしくお願いします。
グラフ理論について

全然分からなくて困っています。誰か助けてください。１．グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕の染色数をそれぞれ求めよ。２．グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。３．オイラーの多面体公式を証明せよ。４．以下の問題を証明せよ。〔１〕頂点数が３以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。〔２〕４頂点以上の極大平面グラフGにおいて、　　　　　　　　　△〔G〕　　不等式　Σ　〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。〔３〕４頂点以上の平面的グラフには、次数５以下の頂点が存在する。〔４〕K5,K3,3は非平面的グラフである。〔５〕平面的グラフは５-彩色可能である。
グラフ理論

大学生です．学部のグラフ理論の授業の事で質問です． 2つの異なるオイラー部分グラフの排他的論理はまたグラフのオイラー部分グラフになることを証明せよ．が分かりません．分かる方，教えてくださいお願いします．
グラフ理論の問題

グラフ理論の問題で分からないものがあります。次の問題の答えがわかる方は、解答を教えてください。単純グラフG＝(V,E)で、分離度ｋ＝１のとき、｜V｜＝ｐ、｜E｜＝ｑであるなら、次の式が成り立つことを証明せよ。　　ｐ－１＜＝ｑ＜＝(１／２)×ｐ×(ｐ－１) よろしくお願いします。
ハミルトンとオリスで迷ってます

最近、高校の時からとてもとても大事にしていたＳＥＩＫＯの腕時計を紛失してしまいました。値段も高い時計で落ち込んでいます。まぁでも落ち込んでばかりいられないので、新たに腕時計の購入を検討しています。そこで、僕の目を引いたのは・・・ハミルトン　ハミルトンカーキ　E.T.O H77612133 オリス　ダイバーズデイト　73375338454M でした。ハミルトンの方は値段を考えるとクォーツの方を選ばざるをえないと考えています。今回の時計選びの条件として・社会人になっても長く持つことができる・さりげなく、でもつけていると「良い時計してるな」と思われる・大学生なので嫌味がない時計です。どちらがお勧めでしょうか？また他にお勧めの時計がありましたら是非教えて頂きたいと思います。皆様のお力をお借りして間違いのない時計の購入をしたいと思います。お願いします。
行列　ハミルトン・ケーリーの定理

数Ｃの行列の質問です。問題としてはシグマトライIIIＣの153番の(1)です。 (1)正方行列A＝(3,-2,1,0)について (A-2E)(A-E)＝(A-E)(A-2E)＝0が成り立つことを示せ。 (証明) ハミルトン・ケーリーの定理より　A⌒2-3A+E＝0 『A≠kE』より (A-2E)(A-E)＝(A-E)(A-2E)＝0 なのですが、『A≠kE』の条件がつく理由がわかりません。回答よろしくお願いしますｍ(_ _)ｍ
保存系とハミルトン系

【１】 ---------- (1) 保存系（x' = f(x) で Div(f)がゼロ。相体積が減らない。まさつがない）ではあるが、 (2) ハミルトン系（q' = ∂H/∂p, p' = - ∂H/∂q）ではない ------------- といった例はあるのでしょうか？ (2)→(1) はすぐ分かるし、(1)(2)は似ているような気がします。けど、(2)は(1)よりずいぶん条件がきついように見えます。もし、そういった例があるとすると、次のことが気にかかります。【２】 http://oshiete1.goo.ne.jp/kotaeru.php3?qid=316948 で、ラグランジアン L が t を陽に含まないときは、時間対称性があって、t の移動に関する保存量があると教えていただきました。保存系も摩擦がないので、時刻 t を含まないと思います。すると、「ハミルトン系に時間対称性がある」、というだけでなく保存系も時間対称性がある、といっていいのでしょうか。ハミルトン系には時間対称性があって、ということばは聞くのですが。（対称性、の使っている意味が違うのでしょうか）
グラフ理論について発表する

　グラフ理論をほとんど知らない人たちの前で、グラフ理論について発表することになりました。グラフ理論の紹介をしようと思うのですが、私自身もグラフ理論については少し学んだだけで、その歴史や特徴は詳しく知らないので、質問させていただきます。　１．現在、グラフ理論は生活のどのようなところに応用されていますか。また、これからどのように応用されると思いますか。　２．グラフ理論を紹介する上で外せないと思うポイントがありましたら教えてください。

ハミルトングラフ

みんなの回答

お礼 2007/12/24 13:08

関連するQ&A

ハミルトングラフの証明

ハミルトングラフ

グラフ理論

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

ハミルトンに関する質問

グラフ理論

グラフ理論の問題について

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

オイラーグラフの十分条件について

グラフ理論の問題

ハミルトン閉路とNP

【グラフ理論】証明問題が分かりません。【難問】

グラフ理論の問題についての質問です

グラフ理論について

グラフ理論

グラフ理論の問題

ハミルトンとオリスで迷ってます

行列　ハミルトン・ケーリーの定理

保存系とハミルトン系

グラフ理論について発表する

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

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

ハミルトングラフ

みんなの回答

お礼 2007/12/24 13:08

関連するQ&A

ハミルトングラフの証明

ハミルトングラフ

グラフ理論

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

ハミルトンに関する質問

グラフ理論

グラフ理論の問題について

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

オイラーグラフの十分条件について

グラフ理論の問題

ハミルトン閉路とNP

【グラフ理論】証明問題が分かりません。【難問】

グラフ理論の問題についての質問です

グラフ理論について

グラフ理論

グラフ理論の問題

ハミルトンとオリスで迷ってます

行列 ハミルトン・ケーリーの定理

保存系とハミルトン系

グラフ理論について発表する

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

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

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

行列　ハミルトン・ケーリーの定理

カテゴリ
一覧

専門家に質問してみよう
専門家登録