作者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/cn.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