24小时热门版块排行榜    

查看: 517  |  回复: 4
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

liufu

新虫 (初入文坛)

[求助] 求助

怎样理解定理“奇圈和奇数阶轮图都是3-色图,而偶数阶轮图为4-色图。”,引自北大耿素云等编著的《离散数学教程》。
回复此楼

» 猜你喜欢

已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

liufu

新虫 (初入文坛)

引用回帖:
4楼: Originally posted by Lei_Z at 2013-01-15 19:23:36
当为奇圈时存在一个几乎完美匹配,即除去一个顶点u以外的顶点可以被一个匹配饱和.由匹配的性质易知这个奇圈在去掉u以后得到的路是2色的且端点不同色。而在奇圈上u与路的两个端点相邻且与两端点不同色。故色数大于等于 ...

谢谢lei-z
5楼2014-10-03 15:57:55
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 5 个回答

liufu

新虫 (初入文坛)

请解答者给出简单的证明或指出证明的出处。
2楼2012-12-18 12:23:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

Lei_Z

木虫 (小有名气)

lovibond: 希望可以说的详细些 2013-01-15 17:37:14
用完美匹配和几乎完美匹配可以得出结果.
不愿等到逝去时才后悔没尽力。
3楼2013-01-15 14:37:56
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

Lei_Z

木虫 (小有名气)

【答案】应助回帖

当为奇圈时存在一个几乎完美匹配,即除去一个顶点u以外的顶点可以被一个匹配饱和.由匹配的性质易知这个奇圈在去掉u以后得到的路是2色的且端点不同色。而在奇圈上u与路的两个端点相邻且与两端点不同色。故色数大于等于3.再由色数小于等于最大度+1, 可以得到结论。
当为奇数阶轮图时,可以把这个图看作是一个孤立点和一个偶圈的练图. 偶圈是2色的。由于孤立点与偶圈上每个顶点相邻,所以孤立点与圈上的顶点不同色,因此奇数阶轮图是3着色的。
同理偶数阶轮图是4着色的。
不愿等到逝去时才后悔没尽力。
4楼2013-01-15 19:23:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] B区考研调剂 +4 yqdszhdap- 2026-03-22 5/250 2026-03-25 08:51 by baoball
[考研] 一志愿武理085500机械专业总分300求调剂 +3 an10101 2026-03-24 7/350 2026-03-25 00:00 by 山鬼0-
[考研] 08工学调剂 +12 用户573181 2026-03-20 17/850 2026-03-24 21:45 by 番茄炖了西红柿
[考研] 300分,材料,求调剂,英一数二 +5 超赞的 2026-03-24 5/250 2026-03-24 21:07 by 星空星月
[考研] 274求调剂 +5 顾九笙要谦虚 2026-03-24 5/250 2026-03-24 18:43 by jhhcooi
[考研] 0854 考研调剂 招生了!AI 方向 +5 pk3725069 2026-03-19 17/850 2026-03-24 17:30 by zhouxuan..
[材料工程] 一志愿C9材料与化工专业总分300求调剂 +4 曼111 2026-03-24 5/250 2026-03-24 15:44 by 星空星月
[考研] 299求调剂 +7 某某某某位 2026-03-21 7/350 2026-03-24 15:24 by cuifj
[考研] 一志愿北京化工大学材料与化工 264分各科过A区国家线 +3 哈哈157349 2026-03-21 3/150 2026-03-24 14:11 by zhyzzh
[考研] 一志愿哈工大,085400,320,求调剂 +3 gdlf9999 2026-03-24 3/150 2026-03-24 10:08 by 搏击518
[考研] 311求调剂 +6 冬十三 2026-03-18 6/300 2026-03-22 20:18 by edmund7
[考研] 求调剂 +7 Auroracx 2026-03-22 7/350 2026-03-22 12:38 by 素颜倾城1988
[考博] 招收博士1-2人 +3 QGZDSYS 2026-03-18 4/200 2026-03-22 10:25 by QGZDSYS
[考研] 求助 +5 梦里的无言 2026-03-21 6/300 2026-03-21 17:51 by 学员8dgXkO
[考研] 311求调剂 +3 勇敢的小吴 2026-03-20 3/150 2026-03-21 17:40 by ColorlessPI
[考研] 321求调剂 +9 何润采123 2026-03-18 11/550 2026-03-20 23:19 by JourneyLucky
[考研] 330求调剂 +4 小材化本科 2026-03-18 4/200 2026-03-20 23:13 by JourneyLucky
[考研] 材料与化工 322求调剂 +4 然11 2026-03-19 4/200 2026-03-20 22:12 by luoyongfeng
[考研] 招收调剂硕士 +4 lidianxing 2026-03-19 12/600 2026-03-20 12:25 by lidianxing
[考研] 085410人工智能专硕317求调剂(0854都可以) +4 xbxudjdn 2026-03-18 4/200 2026-03-20 09:07 by 不168
信息提示
请填处理意见