我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 证明树 >

离散数学问题:如何证明图G的着色数为2当且仅当G是树

归档日期:06-28       文本归类:证明树      文章编辑:爱尚语录

  该题结论中的充分性不成立,看图1中4点的图不是树,但却是2色的。就既使是连通图也不成立,看图2中的图,它也不是树,它也是2色的。

  证明取树G的任意一点P,对树中所有结点按下面方式着色:如果结点与P的路径长为偶数,则该结点(包括P点)着某种颜色C1,如果结点与P的路径长为奇数,则该结点着另外一种颜色C2,如果此时有相邻的两点A,B着同一种颜色,不失一般性,设A,B着颜色C1,则P到A,B各有一条路径长为偶数的路,该路与AB边就构成了回路,这与G是树矛盾,故不可能有相邻的两点着同一种颜色,于是用C1,C2两种颜色对树G进行了正常着色,故G的着色数为2。

本文链接:http://gilbertpromos.com/zhengmingshu/210.html