離散数理

Ｇを２辺連結グラフとする。Ｇの辺集合に対して二項関係を「２辺が同じかカットセットである」と定義する。以下の問いに答えよ。
(a)この二項関係が同値関係であることを示せ。
(b)一つの同値類に含まれる辺は、Ｇの一つの閉路上にあることを示せ。
(c)一つの同値類Ｐに含まれるすべての辺をＧから除くと、残りのグラフの各連結成分は２辺連結であることを示せ。

という問題がわからないので、どなたか教えて下さい。某大学のテスト範囲の問題です。

No.2 回答者： jmh 回答日時： 2005/01/19 00:16

同値関係を～と記す。

(a) 推移、Ａ～ＢとＢ～ＣからＡ～Ｃを導く。ただし、Ａ、Ｂ、Ｃがどの２つも同じでない場合だけを考える。
Ｇ－｛Ａ，Ｂ｝は連結でない。Ｇ－｛Ａ，Ｂ｝の成分のそれぞれから１点ずつとってｘ、ｙとする。Ｇ－｛Ｂ｝は連結なので、ｘとｙを結ぶＧ－｛Ｂ｝の道はどれもＡを通っているハズ（そうでない道があるならＧ－｛Ａ，Ｂ｝でもｘとｙは繋がっている）。ｘとｙを結ぶＧ－｛Ｂ｝の道の一つをＰとする。Ｐをｘからｙに向かって歩いて行くときに、最初に通るＡの端をＡ１とする。もう一方の端をＡ２とする。
Ｇ－｛Ａ｝には、Ａ１とＡ２を結ぶ道があるハズだが、それらはどれもＢを通っていなければならない。そうでない道Ｑがあると、ｘ－Ａ１－Ｑ－Ａ２－ｙというｘからｙへのＡもＢも通らない道があることになってしまう。同様にして、Ｃの両端Ｃ１とＣ２を結ぶＧ－｛Ｃ｝の道はどれもＢを通っていなければならない。
マトメ：　Ｇ－｛Ａ｝には、Ａの両端を結ぶ道があり、それらはどれもＢを通っている、Ｇ－｛Ｃ｝には、Ｃの両端を結ぶ道があり、それらはどれもＢを通っている。
ココから、証明。
背理法：　Ｇ－｛Ａ，Ｃ｝が連結とする。
Ｂの両端をＢ１、Ｂ２とする。
Ａの両端Ａ１とＡ２を結ぶ道がある。
それらはＢを通る。
Ａ１－Ｂ１－Ｂ－Ｂ２－Ａ２という道。
Ｃの両端Ｃ１とＣ２を結ぶ道もある。
やっぱり、Ｂを通る。
Ｃ１－Ｂ１－Ｂ－Ｂ２－Ｃ２という道。
もしそうなら、Ｇ－｛Ａ｝でＡ１－Ｂ１－Ｃ１－Ｃ－Ｃ２－Ｂ２－Ａ２と行けば、Ｂを通らずに済む。矛盾した？

この回答へのお礼

ありがとうございました(*- -)(*_ _)ペコリ
お礼おくれましたがさんこうにさせていただきました。また、わからないことがあったときはよろしくお願いします。

お礼日時：2005/02/12 18:27

No.1 回答者： jmh 回答日時： 2005/01/15 20:51

教えてください。

２辺連結、カットセットとは、何ですか？

この回答への補足

教科書からの抜粋ですが・・・
カットセット：Ｇ＝(Ｖ,Ｅ)を連結グラフとする。辺集合Ｆ⊆ＥをＧから除いて得られるグラフＧ'＝(Ｖ,Ｅ－Ｆ)が連結でないとき、Ｆをカットセットという。
2辺連結：Ｇから任意の1本の辺を除いても残されたグラフは連結である（つまり、除かれた辺集合はカットセットでない）
と、記載されてます(*- -)(*_ _)ペコリ

最近勉強はじめたためよくわかってなくてもうしわけございません

補足日時：2005/01/15 21:08

この回答へのお礼

ありがとうございました。参考にさせてもらいました。自分なりに理解しなんとかテストはやりました。単位がとれてればいいなと思いますo(*^▽^*)o~♪

お礼日時：2005/02/12 18:29