以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  PKU 《离散》问题一大堆？？期待解答，谢！  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=54811)

--  作者：zshao
--  发布时间：11/2/2007 6:18:00 PM

--  PKU 《离散》问题一大堆？？期待解答，谢！
1：定理12。10的证明，求G的着色多相式f(G,k)=f(G[V1],k) * ....
     （不好意思，教材现在 不在身边，没办法敲进去）
    
     问题：
     对于G[V1]的每种着色，为什么 有 f(Hi,k)/f(G[V1],k)种着色方式？？
     看不明白，望指点，谢谢？

2：P187，例12。6
    问题：此题证明中 ，根据“至多(n-1)/2条同色边” 为什么能推出
                                “  (n-1)/2 * X'(Kn)>=  n*(n-1)/2 ”??


3：至多，至少类型的证明，一定是用“反证法”么？            

谢谢，各位解答！


--  作者：fgffggfg
--  发布时间：11/3/2007 12:08:00 AM

--  
2：P187，例12。6  问题：此题证明中 ，根据“至多(n-1)/2条同色边” 为什么能推出
                                “  (n-1)/2 * X'(Kn)>=  n*(n-1)/2 ”??

这样理解：                       X'(Kn)
           边的总数 n*(n-1)/2=    Σ(着第i种颜色的边总数)          1式
                                 i=1
            (上标下标不会加,只好这样写了呵呵)
          因为对于每种颜色至多(n-1)/2条同色边,所以:
             着第i种颜色的边总数<=(n-1)/2      2式
           将2式代入1式右边便可得:n*(n-1)/2<=(n-1)/2 * X'(Kn)
                       


           


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 46.875ms