[理工][離散][圖論] Hamitonian Path 之證明

[mickeyha (M*schief)]

原定理為 http://ppt.cc/815,

證明中要先證G為連通圖

http://ppt.cc/@o6s

但是我看不太懂這個證明@@

矛盾證法懂

但圖會連通與 deg(x)+deg(y) >= n-1 的關係在哪裡呢 ?

回到原定理的證明：

http://ppt.cc/DctP

3.的部分我也看不太懂在描述些甚麼 QAQ

http://ppt.cc/pe5I

煩請好心的強者替我解答了 感謝!!!

---

http://ppt.cc/uFG7  「ㄜ...可以不要親我嗎 = = |||」

---

--
Why Not ：-P

http://whynot-p.blogspot.com/


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.248.49.118
→ ceo890710:deg(x)+deg(y) >= n-1不是題目給的嗎..既然證明矛盾了
→ ceo890710:那不就連通了嗎?
推 genius945:證連通是第一步  之後會用到
推 wheels:關係在於di+dj>=n-1是已知，矛盾到已知就是假設不成立了
推 genius945:我覺得原PO可能一直在想那條式子是哪推來的
→ genius945:但那個定理就是過去從假設然後經由證明所出來的
→ genius945:想成在deg(x)+deg(y) >= n-1的條件下,開始證明,最後證得
→ genius945:此狀況下有H-path
→ mickeyha:對...我一直在想式子是從哪邊冒出來的XDDD
→ mickeyha:這樣我大概明白了 謝謝大家:)))
→ sneak: 那不就連通了嗎? https://daxiv.com