Re: [理工][離散] perfect matching
※ 引述《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
不失一般性，假設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: 122.127.179.46
推
02/02 11:57, , 1F
02/02 11:57, 1F
→
02/02 11:57, , 2F
02/02 11:57, 2F
→
02/02 11:58, , 3F
02/02 11:58, 3F
→
02/02 11:58, , 4F
02/02 11:58, 4F
推
02/02 12:28, , 5F
02/02 12:28, 5F
討論串 (同標題文章)