ようこそ ゲスト さん、新規登録（無料）して気になる疑問を解決しませんか？
はじめての方へ｜ヘルプ｜FAQ

質問
QNo.4152069 マッチングに関する問題　(グラフ理論)
質問者：hayami007 こんにちは。初投稿です。よろしくお願いします。

「すべての木は完全マッチングを高々ひとつしかもたない。」

これを証明する問題です。
直感的にはわかるんですが、うまく証明できません。
よろしくお願いします。
困り度：
  • すぐに回答を！
質問投稿日時：
08/07/05 00:45
この質問に対する回答は締め切られました。
最新から表示｜回答順に表示｜良回答のみ表示

回答良回答20pt
ANo.2 たぶん, その証明はどちらも M1 と M2 の対称差を考えることに帰着できると思います.
で, 「2つの完全マッチングの対称差をとると各頂点の次数は 0 か 2」ということに気付けば簡単です. 次数 2 の頂点のみからなる部分グラフの連結成分がどうなるか, 考えてみてください.
もしくは, 帰納法を使ってもいいかな. 「全ての木は完全マッチングを高々 1つしか持たない」という命題と「全ての森は〜」という命題は等価です. あえて後者を証明することにします. 木には必ず葉があり, 葉は次数が 1 なので完全マッチングでは葉に接続する辺を必ず選ぶ必要があります. これで 2個の頂点と それに接続する辺が消えて, あとにより小さな森が残ります.
回答者：Tacosan
種類：アドバイス
どんな人：一般人
自信：参考意見
回答日時：
08/07/05 23:52
この回答への補足理解できました。ありがとうございます。
この回答へのお礼この回答にお礼をつける(質問者のみ)

回答
ANo.1 とりあえず, 「うまい」かどうかは別にしてその直感を書いてみてください.
不安に感じる点があればそこも書いてくれると better.
回答者：Tacosan
種類：補足要求
どんな人：専門家
自信：参考意見
回答日時：
08/07/05 02:12
この回答への補足返信ありがとうございます。

証明ですが、
木Tが異なる2つの完全マッチングをもつとする。
1つの完全マッチングをM1とし、それと異なるマッチングM2を考える。
M1に含まれない、かつM2に含まれる枝eがある。
そのeから端点に向かって非マッチング枝とマッチング枝を交互に取っ
ていくと、端点で非飽和になる点にがあり、その点を飽和点にするには
閉路ができて、木であることに反する。

という感じです。
交互に取っていくと、おそらく端点で非飽和になる点ができると思うん
ですが、どうしてそうなるかわかりません。
また、Tの枝は交互にM1の枝、M2の枝となりそうなので、M1とM2の対称差を考えたんですが、うまく使えません。

「たぶん」とか「おそらく」ですみません。お願いします。
この回答へのお礼この回答にお礼をつける(質問者のみ)
 
最新から表示｜回答順に表示｜良回答のみ表示
このページのトップへ