问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501
你好,欢迎来到懂视!登录注册
当前位置: 首页 - 正文

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

发布网友 发布时间:2023-07-11 02:25

我来回答

2个回答

热心网友 时间:2024-12-10 06:14

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

必要性成立,如果G是树,则一定着色数为2。

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

热心网友 时间:2024-12-10 06:15

不详...
声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。
E-MAIL:11247931@qq.com
“对不起”用日语怎么讲? 数字媒体艺术专业就业方向与就业前景解读 数字媒体艺术专业就业前景和就业方向 数字媒体艺术专业就业方向及就业前景怎么样 2025数字媒体艺术就业方向 能做什么工作 数字媒体艺术就业前景和待遇 试讲与说课的区别在哪里? 小学数学教师说课和试讲的区别 腹语怎么练入门 《魔兵传奇》的厉害之处 2023年属牛几月会脱单 6月魅力指数升高? 2023年3月生肖牛的桃花运好不好 桃花朵朵开需仔细斟酌? 2023年6月生肖牛爱情与桃花运如何?要注意什么问题? 属牛2023几月份有桃花 2023年属牛人桃花最旺在几月 生肖牛桃花运最旺月份? 六十几平米的房子装修图赏析装修的注意事项 设计师装修165平样板房厚重而素雅 165平装修案例欣赏,房屋布局如何设计 165平装修设计技巧 这五款未来将国产的车型,让你离它们更近一步 以哪里有一条怎么样的小路为句式能怎么写? 仿写句子 一条干干净净的小路又出现了 一条小路伸向远方。(扩句) 街霸2红人点轻腿怎么点不快 梦见抓老虎把它按到水中的预兆 为什么有些运动员在大赛将近时把血液抽出部分冷藏,等到大赛时再输回... ...很多人都去抽血,血抽出来过滤下再输回去,还给你200多元钱,是怎么... 我是做自血臭氧治疗仪的护士,就是给人抽血然后加臭氧后... 可以这么做吗?把人体内的血抽出来再打回身体里去? 把自己的血液抽出再肌注进自己的身体,有什么作用,有没有不良反应?_百 ... 贾宝玉有多爱林黛玉? 宝玉和黛玉的感情有多深 根据你的了解,贾宝玉到底有没有有爱过林黛玉? 婴儿三个月长牙正常吗 长沙市购房契税减半什么时候截止 2022年12月份洛快办交契税后几天退补贴钱 我这辈子再也不会得到幸福了,我真的不想活下去了,好累,好痛苦了 帮忙看一下,这两条孔雀鱼为什么总喜欢在鱼缸底趴着,不爱吃东西,是怀孕... ...有人说晚上露水沾在衣服上对人体不好。是这样 同一计算机系统中有多种不同的存储器,如主存、3.5英寸软盘、硬盘、磁... 慢跑7个黄金技巧轻松跑10公里不累不喘 汉口火车站D5987几点到宜昌东? 武汉至宜昌的火车开车时间及票价? 梦见水罐是什么意思?做梦梦见水罐好不好 梦见水罐是什么征兆 福安人才网597人才网 商品退款几天会到信用卡 我想退掉我自己交的社保钱,社保局会退给我吗? 我以前的单位已经买断了 养老保险后来都是我自己交的 如果我现在... 2022年湖南省电大中专怎么报名?最新报考流程
  • 焦点

最新推荐

猜你喜欢

热门推荐