作者kiwidoit (伊佛利特)
看板Grad-ProbAsk
標題[離散] 圖論
時間Sun Jan 13 22:48:05 2013
Prove that if G=(V,E) is a loop-free undirected graph with |V|= n>=3,
and |E|>=╭ ╮ +2, then G has a Hamiltonian cycle.
│n-1│
│2 │
╰ ╯
如果要證明這一題要用到其他定理
ex.deg(x)+deg(y)>=n,for all x,y不相鄰，則G有Hamiltonian cycle的話
那這個定理也要一起證明嗎? 還是直接用就不用證明...?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.237.64
※ 編輯: kiwidoit 來自: 140.123.237.64 (01/13 22:50)
推 ddczx:要證! 01/13 23:07
→ kiwidoit:唉... 01/13 23:16
→ cutemiller:這個直接畫圖給他說明不知道會有幾分... 01/14 13:21
推 a1098137129:你就直接說 已知在任何完全圖中 必存在 漢米頓 CYCLE 01/14 15:58
→ a1098137129:然後說 N-1的時候 若全圖 則再加一個點 和倆個邊 01/14 16:00
→ a1098137129:必是 漢米頓CYCLE 且因是 簡單圖無LOOP 所以新邊必與 01/14 16:01
→ a1098137129:新加的點相連 01/14 16:01
→ kiwidoit:樓上好聰明... 我都想不出來..QQ 01/14 23:47
推 ddczx:但N-1個點時若不全圖還是無法證阿... 01/15 01:26