Re: [理工][離散] perfect matching
抱歉
我剛剛看到這則證明有個小問題，想請教各位
※ 引述《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
推
10/13 00:45, , 1F
10/13 00:45, 1F
→
10/13 00:46, , 2F
10/13 00:46, 2F
→
10/13 00:47, , 3F
10/13 00:47, 3F
→
10/13 00:48, , 4F
10/13 00:48, 4F
→
10/13 00:48, , 5F
10/13 00:48, 5F
→
10/13 00:49, , 6F
10/13 00:49, 6F
→
10/13 00:50, , 7F
10/13 00:50, 7F
→
10/13 00:51, , 8F
10/13 00:51, 8F
推
10/13 01:38, , 9F
10/13 01:38, 9F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：