マッチングに関する問題 (グラフ理論)

質問

こんにちは。初投稿です。よろしくお願いします。

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

これを証明する問題です。
直感的にはわかるんですが、うまく証明できません。
よろしくお願いします。

回答No.2

Tacosan · ベストアンサー

たぶん, その証明はどちらも M1 と M2 の対称差を考えることに帰着できると思います.
で, 「2つの完全マッチングの対称差をとると各頂点の次数は 0 か 2」ということに気付けば簡単です. 次数 2 の頂点のみからなる部分グラフの連結成分がどうなるか, 考えてみてください.
もしくは, 帰納法を使ってもいいかな. 「全ての木は完全マッチングを高々 1つしか持たない」という命題と「全ての森は～」という命題は等価です. あえて後者を証明することにします. 木には必ず葉があり, 葉は次数が 1 なので完全マッチングでは葉に接続する辺を必ず選ぶ必要があります. これで 2個の頂点と それに接続する辺が消えて, あとにより小さな森が残ります.

補足

理解できました。ありがとうございます。

回答No.1

Tacosan

とりあえず, 「うまい」かどうかは別にしてその直感を書いてみてください.
不安に感じる点があればそこも書いてくれると better.

補足

返信ありがとうございます。

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

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

「たぶん」とか「おそらく」ですみません。お願いします。