- 締切済み
離散数理
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- jmh
- ベストアンサー率23% (71/304)
同値関係を～と記す。 (a) 推移、Ａ～ＢとＢ～ＣからＡ～Ｃを導く。ただし、Ａ、Ｂ、Ｃがどの２つも同じでない場合だけを考える。 Ｇ－｛Ａ，Ｂ｝は連結でない。Ｇ－｛Ａ，Ｂ｝の成分のそれぞれから１点ずつとってｘ、ｙとする。Ｇ－｛Ｂ｝は連結なので、ｘとｙを結ぶＧ－｛Ｂ｝の道はどれもＡを通っているハズ（そうでない道があるならＧ－｛Ａ，Ｂ｝でもｘとｙは繋がっている）。ｘとｙを結ぶＧ－｛Ｂ｝の道の一つをＰとする。Ｐをｘからｙに向かって歩いて行くときに、最初に通るＡの端をＡ１とする。もう一方の端をＡ２とする。 Ｇ－｛Ａ｝には、Ａ１とＡ２を結ぶ道があるハズだが、それらはどれもＢを通っていなければならない。そうでない道Ｑがあると、ｘ－Ａ１－Ｑ－Ａ２－ｙというｘからｙへのＡもＢも通らない道があることになってしまう。同様にして、Ｃの両端Ｃ１とＣ２を結ぶＧ－｛Ｃ｝の道はどれもＢを通っていなければならない。 マトメ： Ｇ－｛Ａ｝には、Ａの両端を結ぶ道があり、それらはどれもＢを通っている、Ｇ－｛Ｃ｝には、Ｃの両端を結ぶ道があり、それらはどれもＢを通っている。 ココから、証明。 背理法： Ｇ－｛Ａ，Ｃ｝が連結とする。 Ｂの両端をＢ１、Ｂ２とする。 Ａの両端Ａ１とＡ２を結ぶ道がある。 それらはＢを通る。 Ａ１－Ｂ１－Ｂ－Ｂ２－Ａ２という道。 Ｃの両端Ｃ１とＣ２を結ぶ道もある。 やっぱり、Ｂを通る。 Ｃ１－Ｂ１－Ｂ－Ｂ２－Ｃ２という道。 もしそうなら、Ｇ－｛Ａ｝でＡ１－Ｂ１－Ｃ１－Ｃ－Ｃ２－Ｂ２－Ａ２と行けば、Ｂを通らずに済む。矛盾した？
- jmh
- ベストアンサー率23% (71/304)
教えてください。２辺連結、カットセットとは、何ですか？
お礼
ありがとうございました。参考にさせてもらいました。自分なりに理解しなんとかテストはやりました。単位がとれてればいいなと思いますo(*^▽^*)o~♪
補足
教科書からの抜粋ですが・・・ カットセット：Ｇ＝(Ｖ,Ｅ)を連結グラフとする。辺集合Ｆ⊆ＥをＧから除いて得られるグラフＧ'＝(Ｖ,Ｅ－Ｆ)が連結でないとき、Ｆをカットセットという。 2辺連結：Ｇから任意の1本の辺を除いても残されたグラフは連結である（つまり、除かれた辺集合はカットセットでない） と、記載されてます(*- -)(*_ _)ペコリ 最近勉強はじめたためよくわかってなくてもうしわけございません
関連するQ&A
- 【離散数理・2項関係】
【2項関係】 次の問いの答えを教えてください。 次の2項関係は反射性、対称性、反対称性、推移性、半順序性、全順序性のどれを満たすか。 １）ｘとｙが英単語のとき、ｘRｙはｘはｙよりも辞書の配列順で前にある。 ２）有向グラフG＝（V,E）において点aから点bに有向路があるとき、aRbとする。 ３）無向グラフG＝（V,E）において点aから点bに路があるとき、aRbとする。 よろしくお願いします。
- 締切済み
- 数学・算数
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 （最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました） また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？ 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- 離散数学の問題が解けずに困っています。
離散数学の問題が解けずに困っています。 どなたか教えていただけないでしょうか？ 【問題文】 A=B=C={r,y,g}とする。 ここで、 A,B,Cはそれぞれが信号機SA,SB,SCが表示できる色の集合、 r,y,gはそれぞれが赤、黄、青に対応する元を表す。 RABがAからBへの二項関係、RACがAからCへの二項関係であるとき、次式が成り立つ。 ・ RAB(r)={r,y,g}、 RAB(y)={r}、 RAB(g)={r} ・ RAC(r)={r}、 RAC(y)={y}、 RAC(g)={g} ここで、a∈A、b∈B、c∈Cのとき、RAB(a)={b|aRABb}、RAC(a)={c|aRACc}である。 このとき、以下の問いに答えよ。 (1)、RABとRACの元をそれぞれ示せ。 (2)、RABの逆関数RAB^-1を示せ。 (3)、BからCへの二項関係RBCをRAB^-1を用いて表し、RBCの元を示せ。
- ベストアンサー
- 数学・算数
- 離散数学課題
学校の離散数学の時間に課題が出ました。しかし全然分かりません。教えてください。 1≦nなる自然数nに対し、1からnまでの自然数の集合をS={1,2,...,n}で表す。以 下の問いに答えよ。 (1)SからSのべき集合2のs乗への全域関数は全部で何個存在するか。理由ととも に述べよ。 (2)Sのべき集合2のs乗から集合{0,1}への部分関数は全部で何個存在するか。理 由とともに述べよ。 (3)S上の2項関係で反対称的なものは全部で何個存在するか。理由とともに述べ よ。 (4)S上の2項関係で反射的かつ反対称なものは全部で何個存在するか。理由とと もに述べよ。 よろしくお願いします。
- 締切済み
- 数学・算数
- 離散数学についての質問です！
例えば、 集合Ｘ＝｛（ｐならばｑ）ならば（ｐ∧ｒ）、（ｐならばｑ）ならばｒ、（ｐでないならばｒ）∧（ｑならばｒ）、ｐ∧（ｑならばｒ）｝ といった論理式があるとき、論理的同値関係≡による、集合Ｘの商集合（Ｘ／≡）は、どうなるのでしょうか？ これと類似した問題を考えているのですが、ちょっと分からないんです・・良ければ、解説をしていただけないでしょうか。
- 締切済み
- 数学・算数
- 最大カット問題と最小カット問題の違い
グラフ理論において辺に重みが付されているときに、最大カット問題あるいは最小カット問題というのが定義されると思うのですが、これらは学問的に別の意義を持つものなのでしょうか？ 重みの正負を逆にすれば同じ問題ではありますが、もし重みを非負としたら、最大カット問題はカットに含む辺の数が必然的にn/2に近づくので、グラフ分割問題と似た様相を呈することになるのかなーと考えています。 もし学問的に問題ごとに明確な定義が与えられているのなら是非知りたいです。 ご意見お待ちしております。
- ベストアンサー
- 数学・算数
- 平面グラフの問いです。
平面グラフの頂点（節点）を凹凸多角形に、頂点連結用の辺（稜）を凹凸多角形の境界線に、それぞれ変換したとします。 その場合、元の平面グラフの連結性と、変換後の凹凸多角形の境界線共有性とは、同値になりますか。 つまり、平面グラフ頂点の彩色問題を、４色問題のような地図色分け問題に、変換できますか。
- ベストアンサー
- 数学・算数
お礼
ありがとうございました(*- -)(*_ _)ペコリ お礼おくれましたがさんこうにさせていただきました。また、わからないことがあったときはよろしくお願いします。