推 christianSK:會說至多 是因為有些tree沒有PM 02/02 11:57
→ christianSK:像是一個兩層的tree , 有多個leaf就沒有 02/02 11:57
→ christianSK:老實說我只是很單純的認為至多一個XD" 02/02 11:58
→ christianSK:沒有想過要證明這件事 02/02 11:58
推 ai305428d:謝謝~應該就是這樣證沒錯^^ 02/02 12:28
※ 引述《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