- ベストアンサー
離散数学のカット枝について
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
1. 定義はここに書いてあります https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%82%B0%E3%83%A9%E3%83%95#.E8.BE.BA.E9.80.A3.E7.B5.90.E5.BA.A6 要は、「連結グラフにおいて、それを取り除くと（グラフ全体が）非連結になってしまうような辺」のことを「切断辺（橋）」という。なお、枝も辺も同じです。 2. 方針だけ書きます。細かい記述（きちんと記号等をつかって「証明っぽく」書くにはどうするか）は一度考えてみてください。 対偶をとって、「A: 辺が切断辺でない」事と「B: 辺が何らかの閉路に属する」ことの同値性を示す。 A→B 切断辺の定義から、「頂点CDをつなぐ辺eが切断辺でない」でないなら、辺eを取り除いてもそのグラフは連結であるので、頂点CとDとの間は（辺eを使わない）パスがある。そのパスと辺eを再びつなげば、それは閉路になる。 B→A 「頂点CDをつなぐ辺eがある閉路に属する」から、その閉路に着目すると、頂点CからDへ辺eを使った後、DからCへ辺eを使わずに戻るパスxがある。従って、ある頂点EからFへのパスで辺eを使うものは、辺eの部分をパスx（もしくはパスxの逆向き）に置き換え、頂点の重複をのぞけば、EからFへのパスで辺eを使わないものが作れる。 従ってそのグラフから辺eを取り除いてもグラフは連結のままで、辺eは橋ではない。
関連するQ&A
- 情報数学 単純グラフの問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか ２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 情報数学 単純グラフの問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 情報数学 単純無向グラフについての問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 最大カット問題と最小カット問題の違い
グラフ理論において辺に重みが付されているときに、最大カット問題あるいは最小カット問題というのが定義されると思うのですが、これらは学問的に別の意義を持つものなのでしょうか？ 重みの正負を逆にすれば同じ問題ではありますが、もし重みを非負としたら、最大カット問題はカットに含む辺の数が必然的にn/2に近づくので、グラフ分割問題と似た様相を呈することになるのかなーと考えています。 もし学問的に問題ごとに明確な定義が与えられているのなら是非知りたいです。 ご意見お待ちしております。
- ベストアンサー
- 数学・算数
- グラフが木であるとき、この定義があります。点の個数ｎ 枝の個数ｍ
グラフが木であるとき、この定義があります。点の個数ｎ 枝の個数ｍ そして ｍ＝ｎ－１ この詳しい証明過程を教えていただけないでしょうか
- ベストアンサー
- 数学・算数
- 数学の問題です。お願いします。友達に頼まれたのですが・・・（3）むずい・・・
（１）定理：２つの角が等しい三角形は二等辺三角形である。 （２）定理：△ＡＢＣと△ＤＥＦにおいて、ＡＢ＝ＤＥ、ＢＣ＝ＥＦ、ＣＡ＝ＦＤならば、△ＡＢＣ≡△ＤＥＦである。 （３）定義：垂直、垂線、垂直二等分線、直角三角形 定義：命題、仮定、結論、逆、対偶、必要、必要条件、十分、十分条件、必要十分条件、同値 定理：点Ｐが点Ａ、Ｂから等距離にあるための必要十分条件は、Ｐが線分ＡＢの垂直二等分線上にあることがである。 上記の三つの問題を「証明」するのですが、きちんと証明できません（というか解りません）。解けるかたいらっしゃいましたら、お願いしますm(__)m
- 締切済み
- 数学・算数
- 高1の数学の問題です。
□に当てはまるものを(1)～(4)のなかから１つ選べ。 「x^2y^2≦1」は「｜x｜＜1かつ｜y｜＜1」の□ (1)必要十分条件である。 (2)必要条件であるが十分条件でない。 (3)十分条件であるが必要条件でない。 (4)必要条件でも十分条件でもない。 できれば、図（グラフを教えてくれたらうれしいです；
- ベストアンサー
- 数学・算数
- 離散数学と言う授業で
出された問題なのですが、解けなくて困っています。 (x^{y})^{z}=x^({y}^{z})を満たす自然数x,y,zの全ての組を求めよ。 x=1のとき、(x^{y})^{z}=1, x^({y}^{z})=1 したがって(x^{y})^{z}=x^({y}^{z}) z=1のとき、(x^{y})^{z}=x^{y}, x^({y}^{z})=x^{y} したがって(x^{y})^{z}=x^({y}^{z}) y=z=2のとき、(x^{y})^{z}=x^{4}, x^({y}^{z})=x^{4} したがって(x^{y})^{z}=x^({y}^{z}) ここまでは分かりました。以上は十分条件で、必要十分条件まで考えて求めなきゃだめらしくて・・。対数とか使うらしいです。誰か教えてください。
- ベストアンサー
- 数学・算数
