图论第五次作业答案.doc

《图论第五次作业答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论第五次作业答案5.16设图G的次数序列是d1，d2…….dv，且此序列单调下降，即d1≥d2≥….≥dv，则:解答思路：原题等价于证明:存在k，使得χ(G)≤min(dk+1,k)若dk+1≥k，设di是顶vi的次数，则先用k种颜色对v1，v2…vk顶做正常着色对任意的m>k，有k≥min{dm+1,m},可知k≥dm+1，所以vk+1，vk+2…vv可被k正常着色.若dk+1min{dk,k-1}，又因为dk≥k-1,所以dk+1≥k-1,推出dk+1=k-1.设di是顶vi的次数，则先用k-1种颜色对v1，v2…vk-1顶做正常着色对任意m>k

2、-1,有k-1=dk+1≥dm+1，所以vk+1，vk+2…vv可被k-1正常着色.5.25A是一个n元素集合，把A的每个子集用油n个分量的0-1向量α来表示；设A={a1，a2，…，an}，一子集中含有元素ai，则α的第i个分量取1，否则取0，以所有的0-1向量α为顶集，仅当上述的两个向量只有一个同为向量相异时，在此二项间连一边，得到的图叫做n维立方体图.问：χ(n维立方体图)=?χ’(n维立方体图)=?解题思路：n维立方图可以看做由2个n-1维立方图以及对应顶点的连接所构成，由数学归纳法可以求出χ(Gn)=2χ(G2)=2，假设χ(Gn-1)=2，则将原Gn-1着色

3、的2种颜色互换，然后再将两Gn-1连接即得顶着色为2的Gn同样可用数学归纳法求出χ’(Gn)=nχ’(G2)=2,假设χ’(Gn-1)=n-1，则将两同样边着色的Gn-1用第n中颜色连接，即得边着色为n的Gn.5.32：求α(k维立方体)，β(k维立方体)解题思路:设k维立方体为Gk.α(G2)=4，α(G3)=8，用数学归纳法可求α(Gk)=β(Gk)=2k-1PS：有的同学说Gk可看做个k则二分图，也是可以的.例如当k=3时：0000100011001105.33：求证：对G的任子图H，当且仅当G是二分图.解题思路：若G是二分图，则G的子图H也是二分图，设顶集X和Y

4、是H的二分子集，则，所以。若对G的任意子图有，且G不是二分图，取G中的奇圈作为子图H’，则