以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [讨论]关于布鲁克斯(Brooks)定量  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=57195)

--  作者：xianyun
--  发布时间：12/25/2007 11:57:00 PM

--  [讨论]关于布鲁克斯(Brooks)定量
为什么Kn要限制n>=3呢？
此主题相关图片如下：
按此在新窗口浏览图片
--  作者：teng_t1986
--  发布时间：12/26/2007 9:34:00 AM

--  
n=2的时候G不是完全图就是不连通图……
而且色数肯定大于最大度
--  作者：zshao
--  发布时间：12/26/2007 11:41:00 PM

--  
xianyun

你帖子上的图是怎么贴上去的，点击那个按纽：
--  作者：xianyun
--  发布时间：12/26/2007 11:56:00 PM

--  

以下是引用zshao在2007-12-26 23:41:00的发言：
xianyun
  
你帖子上的图是怎么贴上去的，点击那个按纽：

--  作者：xianyun
--  发布时间：12/26/2007 11:58:00 PM

--  
以下是引用teng_t1986在2007-12-26 9:34:00的发言：
n=2的时候G不是完全图就是不连通图……
而且色数肯定大于最大度


所以我的意思就是不应该对n限制，因为所有的n都有 χ(Kn)≥Δ(Kn)：
1=χ(K1)≥Δ(K1)=0
2=χ(K2)≥Δ(K2)=1
……………………
n=χ(Kn)≥Δ(Kn)=n-1
--  作者：teng_t1986
--  发布时间：12/27/2007 9:31:00 AM

--  
χ(Kn)≥Δ(Kn)？？？
反了吧……
而且，定理上说“非完全图”啊，是你没仔细看吧？……


以下是引用xianyun在2007-12-26 23:58:00的发言：
[quote]以下是引用teng_t1986在2007-12-26 9:34:00的发言：
n=2的时候G不是完全图就是不连通图……
  而且色数肯定大于最大度
[/quote]
所以我的意思就是不应该对n限制，因为所有的n都有 χ(Kn)≥Δ(Kn)：
1=χ(K1)≥Δ(K1)=0
2=χ(K2)≥Δ(K2)=1
……………………
n=χ(Kn)≥Δ(Kn)=n-1


--  作者：xianyun
--  发布时间：12/27/2007 12:16:00 PM

--  
以下是引用teng_t1986在2007-12-27 9:31:00的发言：
χ(Kn)≥Δ(Kn)？？？
反了吧……
而且，定理上说“非完全图”啊，是你没仔细看吧？……

我的意思是定理为什么不这么叙述：“设连通图不是完全图Kn也不是奇圈，则χ(G)≤Δ(G)”，而要在Kn后面加上“n≥3”的限制呢？对于所有的n都有χ(Kn)≥Δ(Kn)的呀………

--  作者：buddha
--  发布时间：12/27/2007 6:44:00 PM

--  
以下是引用buddha在2007-12-27 13:23:00的发言：
[quote]以下是引用xianyun在2007-12-26 23:58:00的发言：
[quote]以下是引用teng_t1986在2007-12-26 9:34:00的发言：
  n=2的时候G不是完全图就是不连通图……
   而且色数肯定大于最大度
  [/quote]
  所以我的意思就是不应该对n限制，因为所有的n都有 χ(Kn)≥Δ(Kn)：
1=χ(K1)≥Δ(K1)=0
  2=χ(K2)≥Δ(K2)=1
  ……………………
n=χ(Kn)≥Δ(Kn)=n-1
  
[/quote]
错了吧.Kn的边色数为n-1啊.你再画画?


汗啊。离散书不在身旁，又好长时间没看离散了。概念都搞混了。
仔细想了下。确实有点问题。
比如K2不是完全图Kn(n>=3)也不是奇圈。
但χ(K2)=2>1=Δ(K2)，但并不满足χ(G)≤Δ(G)。
？？
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 46.997ms