- 締切済み
グラフの証明を教えてください
- みんなの回答 （5）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
そ～なんですよ～, 「ツアー」とか「トレイル」ってあんまり使わない表現なので意味を確認しないとダメなんですよね～＞#4. ということで, 最低限「ツアー」と「トレイル」の定義は書いてください.
- B-juggler
- ベストアンサー率30% (488/1596)
ゴメン、Ｎｏ．１，２です。 頓珍漢なこと書いてる。 Ｃ は Ｇの一部と考えればいいのか。 すいません、訂正してお詫びいたします。 ツアー とか トレイル って グラフや生成木、枝 なんていう日本語と どう対応しているんだろうか？ (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=)
- graphaffine
- ベストアンサー率23% (55/232)
当たり前だと思うのだが。 Gの点は全て偶点、そして、Cが通る点をxとすればxに接続するCの辺は偶数本、従って、Cの辺を取り除いたときxには偶数本の接続辺が残る。
- B-juggler
- ベストアンサー率30% (488/1596)
Ｎｏ．１です。 う～ん、「分かるところまで書いてください」と、書いて 説明されてもなぁ？ どこがどういう風に分からないか？ これになっていない気がするんだけど。 まぁいいや、問題文はこれであっている？ ＧとＣ が 逆になっていないか？ まぁ意味が分かればどうとでもなるのだが・・・。 基本線、一筆書きができる状況なんだから （オイラーツアーを持たないって単純にはこういうこと）、 ＧもＣ も 一筆書き出来ているはず。 まずそこさえ分かっていれば、えっとＣ か ここでは？ Ｃ は 重複線がある状態だね。 ＃Ｇは重複線がない状態だと考えてよさそうだ。 ＃だから逆じゃないかと思ってみているんだけど。 問題の最初に、背理法を使うと書いてあるんだから、 背理法を使ったら？ Ｈの各頂点次数を、偶数ではない（つまり奇数）としておいて、 それが、成立しないことを示せばいい。 次数全て奇数の点におけるグラフは、一筆書きできる？ これで済ませてもいいと思うよ。 何か重大なところで落としているから、しっかり拾ってこようか。 (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=) σ(・・*)は専門ではないから、講師先生に聞いて確認ね。
- B-juggler
- ベストアンサー率30% (488/1596)
代数学の元非常勤です。 えっと、明らかに大学のグラフ理論だけど 「どこまで分かるか」を書いてください。 ここで講義するわけにも行かないのでね。 オイラーツアー って、なんだろう？ 頂点次数 ってなんだろう？ これだけの問題を、簡単に丸投げされると、 答えようがないよ。 この講義をやっている先生はきっと悲しいだろうね・・・。 (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=)
関連するQ&A
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 （最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました） また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？ 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフ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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- 離散数学 オイラーグラフ、ハミルトングラフの質問です。
離散数学 オイラーグラフ、ハミルトングラフの質問です。 添付データの画像のグラフについて考えています。 括弧の中に書いてあることが正しいのかと、このグラフはハミルトングラフであるか？ また、その理由を教えてください。 このグラフは位数（５）の（完全）グラフであり（４）次の（４-正則）グラフ ３辺形は（5Ｃ3＝ １０個） ４辺形は（5C4 * 2 = 10個) （すべての辺から偶数個の辺が出ているためオイラーグラフ）
- ベストアンサー
- 数学・算数
- 情報数学 単純グラフの問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 情報数学 単純無向グラフについての問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 情報数学 単純グラフの問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか ２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
補足
オイラーツアーは連結グラフGのトレイルで、Gの辺を総て含むもの 頂点次数は各頂点に対応する辺の数です 簡単な図にしたら偶数しかないことはわかるのですが どうやって証明にしたらいいかがわかりません