作者AAQ8 ()
看板Grad-ProbAsk
标题[理工] 离散数学 图论证明
时间Mon May 14 00:07:59 2018
https://i.imgur.com/0FYQsPV.jpg
https://i.imgur.com/5FHakou.jpg
不好意思我字有点丑
我想问的是这个定理的前提是说
"若G中任两个不相邻的点x,y，满足x和y的degree总和大於等於n，则G具有HC"
不过黄子嘉上课证明时假设的a和b是相邻的
这样不是违反前提了吗
不太懂为什麽可以这样子
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 219.70.197.208
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1526227682.A.20A.html
1F：→ TMDTMD2487: 这个证明讲述H中任两个不相邻的点degree合小於等於n-105/14 01:32
可是我不懂的是
最後是写deg(a)+deg(b) <= n-1
a和b是相邻的两个点
怎麽会可以拿来证明不相邻的两个点degree和小於等於n-1
2F：→ TMDTMD2487: 所以如果任两个不相邻的点degree合大於等於n代表他不05/14 01:33
3F：→ TMDTMD2487: 是上面所假设的H05/14 01:33
4F：→ TMDTMD2487: 不是H就不会是G 那他就是有HC的图05/14 01:37
※ 编辑: AAQ8 (219.70.197.208), 05/14/2018 15:34:22
5F：推 TMDTMD2487: ab不相邻啊05/14 21:04
6F：→ TMDTMD2487: e={a,b}不在H中05/14 21:04
哦哦我有点头绪了
https://i.imgur.com/NNkH7PD.jpg
可是为什麽一开始已经说e不在G和H中了
最後一段的证明还可以说在G和H中 deg(a)+deg(b)<=n-1
※ 编辑: AAQ8 (219.70.197.208), 05/15/2018 12:16:50
7F：→ TMDTMD2487: 首先e=ab不在H中，再来有推论出Vi与b相连则a必定不与V 05/15 18:35
8F：→ TMDTMD2487: i-1相连，因此可以由上图算出两个点的deg合的上限 05/15 18:35
9F：→ TMDTMD2487: 这个证明用矛盾证法在一开始假设一个无HC的图会存在 05/15 18:42
10F：→ TMDTMD2487: 两个不相邻的点deg和大於等於n，而最後与结果矛盾，因 05/15 18:42
11F：→ TMDTMD2487: 此得到一个小结 任一个无HC的图其中任意不相邻的两点d 05/15 18:42
12F：→ TMDTMD2487: eg和必定小於n，再用反证法得证任意不相邻两点deg和若 05/15 18:42
13F：→ TMDTMD2487: 大於等於n则必定存在HC 05/15 18:42
14F：→ TMDTMD2487: 我的讲法可能很绕，但我觉得这样讲很好理解 05/15 18:42
我懂了
谢谢T大
非常感谢
※ 编辑: AAQ8 (219.70.197.208), 05/15/2018 19:26:38