作者mistel (Mistel)
看板Grad-ProbAsk
標題Re: [理工] 離散圖論的證明 黃子嘉6-125
時間Tue Aug 13 09:12:51 2019
※ 引述 《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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1565658773.A.4EB.html
1F：→ mathtsai: loop-free undirected graph 不就是tree？08/13 22:36
2F：→ mistel: loop free不是沒有cycle，是沒有自己到自己的邊08/14 00:14
3F：→ mathtsai: 喔喔 誤會了XDD08/14 02:39
4F：→ JKLee: 不行。這題是要你給出一個明確的著色方法，並說明該著色結08/14 08:06
5F：→ JKLee: 果符合條件08/14 08:06
6F：→ JKLee: 你提供的證明只有證Δ<=n的case08/14 08:12
7F：→ JKLee: 我錯了，Δ不會大於n 08/14 08:16
8F：→ JKLee: 我覺得你的證明是對的 08/14 08:20
感謝，其實有部分原因是因為我看不懂解答的證法（不知道為什麼不是先從degree最大的點
開始著色）
※ 編輯: mistel (223.136.150.143 臺灣), 08/14/2019 08:52:15
9F：→ JKLee: 黃的解答的著色方法，最多會用掉delta+1種顏色 08/14 23:49
10F：→ JKLee: 因為存在delta+1色的著色方法，所以X(G)<=delta+1 08/14 23:53
11F：→ JKLee: 只要顏色的選項給的夠多，不管從那一點開始著色，都不會發 08/14 23:56
12F：→ JKLee: 生顏色不夠用的情況 08/14 23:56
13F：→ JKLee: 顏色不夠用的狀況很容易出現在要對degree最大的點上色時 08/15 00:04
14F：→ JKLee: 他的鄰居全部都上色了，而且都不同色 08/15 00:05
15F：→ JKLee: 但是如果有delta+1種顏色，就不會發生這種壞狀況 08/15 00:06