|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 图论中问题 (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=36979) |
|
-- 作者：shijl424 -- 发布时间：8/19/2006 10:03:00 PM -- 图论中问题 (耿,屈,王,2001)教材中,P124页定理7.11中 最后一句 λ(G)<δ(G)≤δ(G*)≤n1-1+ [λ(G)/n1] 注：这里[]暂表示下取整，未找到相应符号 我怎么也想不明白δ(G*)≤n1-1+ [λ(G)/n1]为何成立，望高手指点迷津，不胜感激 。 ------07PKU |
|
-- 作者：Logician -- 发布时间：8/20/2006 2:26:00 AM -- 考虑K_{n_1}中所有顶点的度数和S。K_{n_1}中所有顶点间都有边，共有 (n_1)*(n_1 - 1)/2 条边，这为K_{n_1}中的顶点贡献了 (n_1)*(n_1 - 1) 度。同时，E_1中每条边都有一端在K_{n_1}中。这样，E_1中的这些边又为K_{n_1}中的顶点贡献了λ(G)度。 所以，K_{n_1}中所有顶点的度数和 S = (n_1)*(n_1 - 1) + λ(G)。设v是K_{n_1}中度数最小的顶点，那么根据鸽巢原理，有 d(v) ≤ S/n_1。又由于d(v)是整数，所以对不等式的两边向下取整，就得到 d(v) = [d(v)] ≤ [S/n_1] = n_1 - 1 + [λ(G)/n]。 |
|
-- 作者：xieknight -- 发布时间：8/20/2006 1:17:00 PM -- 高见！ |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
7,875.000ms |