作者chchwy (mat)
看板Grad-ProbAsk
標題Re: [理工][離散] perfect matching
時間Wed Oct 12 19:50:07 2011
抱歉
我剛剛看到這則證明有個小問題，想請教各位
※ 引述《ybite (小犬)》之銘言：
: ※ 引述《ai305428d (可愛小小羅)》之銘言：
: : A tree T contains (1) no (2) at least (3) at most one
: : perfect matching; prove your answer......
: : ans: (3)
: : ......請教一下這題應該怎麼證呢?
: : 來源是交大95資工
: 首先應該要先證Tree存在Perfect Matching，可是我還沒搞懂這點 Q____Q
: 至於「至多一個」，以下是我在網路上看到一個也許正確的證明：
: 假設M1和M2對同一棵樹的兩種不同Perfect Matching
: 那麼M1ΔM2（對稱差）的分量圖就包含了只屬於M1或M2其中之一的所有邊
: 假設M1ΔM2有一邊e = {u, v}且u是M1ΔM2一分量圖中的端點, deg(u) = 1
請問這裡為什麼可以做 deg(u) = 1 這個假設??
如果所有M1ΔM2中，所有的邊deg都不等於一，那這個證明還算有效嗎?
: 不失一般性，假設e這個邊屬於M1而不屬於M2
: 因為M2是一個Perfect matching，因此必存在另一邊e1 = {u, w}連到u上
: 但這會導致M1ΔM2中u會同時連到v和w使deg(u) = 2，與假設矛盾
: 因此M1ΔM2必定為空集合，即M1=M2，到此證明了唯一性
: ---
: 有人有更好的證明嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.158.103
推 wheels:因為M1為此Tree的一個子圖，M2也是，所以M1ΔM2也是此Tree 10/13 00:45
→ wheels:的一個子圖，所以不存在cycle，必定可以找到一個e的某一邊 10/13 00:46
→ wheels:deg為1。這題因該是要裡解成"若存在Perfect Matching，則 10/13 00:47
→ wheels:必為一"，而不是理解成Tree必有Perfect Matching吧。當然也 10/13 00:48
→ wheels:要確定Tree可能會有Perfect Matching存在，不過這個很好舉 10/13 00:48
→ wheels:例，找一個點數為偶數的樹就有了。 10/13 00:49
→ wheels:修正第三行錯字"應該" 10/13 00:50
→ wheels:還有"理解"=..= 10/13 00:51
推 wheels:還有第四行的"唯一"...我的國文老師哭了～ 10/13 01:38