[理工][離散] perfect matching

看板Grad-ProbAsk作者 (可愛小小羅)時間15年前 (2011/02/02 10:39), 編輯推噓7(7推 0噓 15→)
留言22則, 5人參與, 最新討論串1/3 (看更多)
A tree T contains (1) no (2) at least (3) at most one perfect matching; prove your answer...... ans: (3) ......請教一下這題應該怎麼證呢? 來源是交大95資工 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.255.9.66 ※ 編輯: ai305428d 來自: 111.255.9.66 (02/02 10:40)
推
02/02 10:41, , 1F
樹的奇數層互不相連, 同理偶數也是一樣
02/02 10:41, 1F
→
02/02 10:42, , 2F
而自root開始都只能跟child互相配對
02/02 10:42, 2F
推
02/02 10:47, , 3F
不過我覺得如果考慮樹左右子樹的方向性應該是有兩個
02/02 10:47, 3F
→
02/02 11:17, , 4F
答案確實是at most one
02/02 11:17, 4F
→
02/02 11:17, , 5F
證明正在想qqqqqq
02/02 11:17, 5F
→
02/02 11:22, , 6F
c大,抱歉 我不太董你意思@@ 可以再說明一下嗎....
02/02 11:22, 6F
推
02/02 11:40, , 7F
抱歉 tree不用考慮左右子樹的方向性, 這樣一個是對的
02/02 11:40, 7F
推
02/02 11:44, , 8F
請問perfect matching是什麼意思..
02/02 11:44, 8F
推
02/02 11:46, , 9F
給原po , 我也不知道怎麼解釋比較好 XD"
02/02 11:46, 9F
推
02/02 11:51, , 10F
就是每個點都找的到人跟他配對
02/02 11:51, 10F
→
02/02 11:52, , 11F
樓上是在說perfect matching
02/02 11:52, 11F
→
02/02 11:58, , 12F
Matching: 在一個圖中取數個邊，使無兩邊共用同一個端點
02/02 11:58, 12F
→
02/02 11:59, , 13F
Perfect Matching: 圖中的所有點都包含在Matching中
02/02 11:59, 13F
→
02/02 12:03, , 14F
例子：對雙分圖K3,3，兩側分別有abc和xyz三點來說
02/02 12:03, 14F
推
02/02 12:03, , 15F
謝謝:)
02/02 12:03, 15F
→
02/02 12:03, , 16F
a-x, b-y, c-z 是一種Perfect matching
02/02 12:03, 16F
→
02/02 12:04, , 17F
不過雙分圖的情況會特別叫Complete matching orz
02/02 12:04, 17F
→
02/02 12:04, , 18F
可以請問這是在tree那個章節嗎= = 怎麼沒看過..
02/02 12:04, 18F
→
02/02 12:05, , 19F
啊不對，Complete Matching不是這樣... Orz
02/02 12:05, 19F
→
02/02 12:05, , 20F
黃子嘉的書的話在演算法分析 > 配對理論 8-5
02/02 12:05, 20F
→
02/02 12:09, , 21F
OK!
02/02 12:09, 21F
→
09/11 14:12, , 22F
a-x, b-y, c https://daxiv.com
09/11 14:12, 22F
‣ 更多 ai305428d 的文章
文章代碼(AID): #1DICFrlO (Grad-ProbAsk)
‣ 更多 ai305428d 的文章
文章代碼(AID): #1DICFrlO (Grad-ProbAsk)