作者fragmentwing (片翼碎夢)
看板Math
標題[離散] 關於hamiltonian的問題
時間Fri Oct 23 09:13:03 2020
在讀別人的筆記時看到的
關於HC：
是看到有一題寫到不相鄰兩點x,y
deg(x)+deg(y)>=n則G必有HC
我上網查這應該其實是在講Ore's theorem
但是那理論最後是說，符合條件的會形成Hamiltonian圖形
並沒有特別指HC或HP
99年台大資工的題目，不知道是不是條件有缺還是單純他抄錯
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.174 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1603415589.A.42C.html
※ 編輯: fragmentwing (111.71.214.174 臺灣), 10/23/2020 09:36:45
1F：→ hwanger : 可以形成HC 下圖節自"Introductory Combinatorics, 10/23 10:45
2F：→ hwanger : 5th ed., Richard A. Brualdi" 10/23 10:46
4F：→ hwanger : 證明的話書裡有 10/23 10:48
5F：→ hwanger : 有HC 自然而然就有HP 10/23 10:48
6F：→ hwanger : 看到標題 當下是覺得要算量力或古典力學的題目 冏 10/23 10:49
7F：→ fragmentwing: 感謝ｈ大提供解法 10/23 12:41
8F：→ fragmentwing: 之後細看其實不算解法 不過後來有找到了 10/24 16:48
9F：→ hwanger : ??? 你原文中的問題不是滿足Ore's property的圖是有 10/24 21:12
10F：→ hwanger : HC還是HP嗎 不太懂你後來找到的意思 10/24 21:15
11F：→ fragmentwing: 他這樣寫已經足夠證明了嗎 50個點 x＝4 45個點沒有 10/24 23:38
12F：→ fragmentwing: 與該點相連且這些點degree46起跳 沒有直接說明這個 10/24 23:38
13F：→ fragmentwing: 案例怎麼連成HC 10/24 23:38
14F：→ hwanger : 冏 那不是證明 只是我要連Ore's property也節下來 10/25 00:09
15F：→ hwanger : [10/23 10:48]"證明的話書裡有">>>書裡寫了將近兩頁 10/25 00:10
16F：→ hwanger : 我沒節下來 這本書不知為何 google第一筆就是他的電 10/25 00:11
17F：→ hwanger : 子書 想說就算找不到實體書好像也還好 就沒節錄證明 10/25 00:13
18F：→ fragmentwing: 原來是這樣 我總算是看懂當初h大說證明書裡有的意思 10/25 00:14