推 shownlin: 問題一那是具HC的充份條件 08/24 10:12
→ shownlin: 問題二應該是為了算deg(x)跟deg(y) 08/24 10:16
→ shownlin: 因為這兩點不相連所以這兩個點的degree相加剛好會是砍 08/24 10:16
→ shownlin: 掉的邊數 08/24 10:16
→ ss455032: 謝謝 08/24 22:12
大大們您好,想請問這題為什麼證明
E>=C(n-1,2)+2
是claim :deg(x)+deg(y)>=n
問題2,為什麼要假設G'=(V-{x,y},E')去掉x,y的圖
是為了讓他不相鄰嗎?
http://i.imgur.com/i9KQoyD.jpg
覺得這種題目沒看過做不怎出來
謝謝大大們
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.4.57
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1503488757.A.7CB.html