作者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