- 締切済み
情報数学 単純無向グラフについての問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- akaheru0228
- お礼率61% (8/13)
- 数学・算数
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
定義は?
関連するQ&A
- 情報数学 単純グラフの問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 情報数学 単純グラフの問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか ２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 情報数学 単純無向グラフについての問題
G が切断点を持てば,G は橋を持つ 正しくない G = (V, E) が連結,かつ |E| < |V | ならば,G は無向木である 正しい すべての完全グラフの直径は 1 である 正しい 節点数 5 の完全グラフ K5 は平面描画可能である 正しくない それぞれの理由を教えてほしいです。
- ベストアンサー
- 数学・算数
- 離散数学 オイラーグラフ、ハミルトングラフの質問です。
離散数学 オイラーグラフ、ハミルトングラフの質問です。 添付データの画像のグラフについて考えています。 括弧の中に書いてあることが正しいのかと、このグラフはハミルトングラフであるか？ また、その理由を教えてください。 このグラフは位数（５）の（完全）グラフであり（４）次の（４-正則）グラフ ３辺形は（5Ｃ3＝ １０個） ４辺形は（5C4 * 2 = 10個) （すべての辺から偶数個の辺が出ているためオイラーグラフ）
- ベストアンサー
- 数学・算数
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 （最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました） また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？ 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
- ケー二スバルグの橋の問題（一筆書き）
以前、他の方が、聞いてましたが、もっと具体的にケー二スバルグの橋の問題（一筆書き）を。 (1) 連結な平面グラフの各頂点が偶数個の辺に隣接している⇒ 連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。 (2) 連結な平面グラフのちょうど２つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能 (1)、(2)をそれぞれ、数学的帰納法を用いて、証明したいんです。自分でやってみたんですが、うまくいかないんです。 力を貸して頂けないでしょうか？ どなたか教えていただけないでしょうか？
- 締切済み
- 数学・算数
- グラフの性質の問題について
以下の問題、よろしくお願いします。 点の集合と点同士とを結ぶ辺の集合とからなる図形をグラフと呼びます。以下では立方体の頂点と辺からなるグラフを一般化して出来るグラフの性質を考察します。正方形は2次元の立方体なので２-cubeと呼ばれます。立方体は３-cubeです。数学では次元の低い方にも一般化を行います。 ２点と２点を結ぶ直線からなるグラフは１-cubeです。n-cubeはn次元ユークリッド空間の超立方体の頂点と辺とからなるグラフです。nーcubeに関して以下の問に答えなさい。 問１ 全ての辺の長さを１とします。ある点を１度だけ通過して点と点をつなぐ辺を辿り、異なる２点を結ぶ経路をパスと呼びます。あるグラフの上で、任意の２点ｘ，yを結ぶパスp(ｘ，ｙ)の中でその長さ[p（ｘ，ｙ)] の最小値[p（ｘ，ｙ）］を点ｘ，ｙの距離と呼びます。グラフ上で［p（ｘ，ｙ）］の最大値のグラフを直径と呼びます。n-cubeの直径をnの式で表しなさい。 問２ 点の位置や辺の長さを自在に変えて曲線も許すとき、辺が交わらないように平面に作図可能なグラフを平面グラフと呼びます。２-cube、３-cubeは平面グラフですが、４-cubeはそうではありません。平面に描けないグラフを平面に描ける幾つかの部分に分解することができます。このとき、分解の最小数をグラフの厚さと呼びます。n-cubeの厚さをnの式で表しなさい。
- ベストアンサー
- 数学・算数
- 離散数学のカット枝について
以下のような問題がありました。回答が掲載されていないので回答例を教えてください 1.切断枝（カット枝、橋）の定義を書け 2.グラフの枝がカット枝であるための必要十分条件は、その枝がどの閉路にも属さないことであることを証明せよ。 よろしくお願いします。
- ベストアンサー
- 数学・算数
