[理工] 離散圖論 漢米爾頓

看板Grad-ProbAsk作者 (ss455032)時間8年前 (2017/08/23 19:45), 編輯推噓1(1推 0噓 4→)
留言5則, 2人參與, 最新討論串1/1
大大們您好,想請問這題為什麼證明 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
推
08/24 10:12, , 1F
問題一那是具HC的充份條件
08/24 10:12, 1F
→
08/24 10:16, , 2F
問題二應該是為了算deg(x)跟deg(y)
08/24 10:16, 2F
→
08/24 10:16, , 3F
因為這兩點不相連所以這兩個點的degree相加剛好會是砍
08/24 10:16, 3F
→
08/24 10:16, , 4F
掉的邊數
08/24 10:16, 4F
→
08/24 22:12, , 5F
謝謝
08/24 22:12, 5F
‣ 更多 ss455032 的文章
文章代碼(AID): #1PdMhrVB (Grad-ProbAsk)