Re: [理工] 離散圖論的證明 黃子嘉6-125

看板Grad-ProbAsk作者 (Mistel)時間4年前 (2019/08/13 09:12), 4年前編輯推噓0(0推 0噓 15→)
留言15則, 3人參與, 4年前最新討論串2/2 (看更多)
※ 引述 《winiel559 (大漢天威)》 之銘言： : 　 : 圖論的證明寫起來都好抖... : 想請問這題可以這樣寫嗎？ : 謝謝大家 : https://i.imgur.com/3VLxMVJ.jpg
: 　 挖到古文，想請問一下，類似這位版友的證法，不知道可不可以？ https://i.imgur.com/A2LbTAs.jpg
解答 https://i.imgur.com/pd4xA5g.jpg
圖論證明感覺蠻多解法的OAO -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.243.50 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1565658773.A.4EB.html
→
08/13 22:36, 4年前 , 1F
loop-free undirected graph 不就是tree？
08/13 22:36, 1F
→
08/14 00:14, 4年前 , 2F
loop free不是沒有cycle，是沒有自己到自己的邊
08/14 00:14, 2F
→
08/14 02:39, 4年前 , 3F
喔喔 誤會了XDD
08/14 02:39, 3F
→
08/14 08:06, 4年前 , 4F
不行。這題是要你給出一個明確的著色方法，並說明該著色結
08/14 08:06, 4F
→
08/14 08:06, 4年前 , 5F
果符合條件
08/14 08:06, 5F
→
08/14 08:12, 4年前 , 6F
你提供的證明只有證Δ<=n的case
08/14 08:12, 6F
→
08/14 08:16, 4年前 , 7F
我錯了，Δ不會大於n
08/14 08:16, 7F
→
08/14 08:20, 4年前 , 8F
我覺得你的證明是對的
08/14 08:20, 8F
感謝，其實有部分原因是因為我看不懂解答的證法（不知道為什麼不是先從degree最大的點 開始著色） ※ 編輯: mistel (223.136.150.143 臺灣), 08/14/2019 08:52:15
→
08/14 23:49, 4年前 , 9F
黃的解答的著色方法，最多會用掉delta+1種顏色
08/14 23:49, 9F
→
08/14 23:53, 4年前 , 10F
因為存在delta+1色的著色方法，所以X(G)<=delta+1
08/14 23:53, 10F
→
08/14 23:56, 4年前 , 11F
只要顏色的選項給的夠多，不管從那一點開始著色，都不會發
08/14 23:56, 11F
→
08/14 23:56, 4年前 , 12F
生顏色不夠用的情況
08/14 23:56, 12F
→
08/15 00:04, 4年前 , 13F
顏色不夠用的狀況很容易出現在要對degree最大的點上色時
08/15 00:04, 13F
→
08/15 00:05, 4年前 , 14F
他的鄰居全部都上色了，而且都不同色
08/15 00:05, 14F
→
08/15 00:06, 4年前 , 15F
但是如果有delta+1種顏色，就不會發生這種壞狀況
08/15 00:06, 15F
‣ 更多 mistel 的文章
文章代碼(AID): #1TKWwLJh (Grad-ProbAsk)
‣ 更多 mistel 的文章
文章代碼(AID): #1TKWwLJh (Grad-ProbAsk)