24小时热门版块排行榜    

查看: 512  |  回复: 4

liufu

新虫 (初入文坛)

[求助] 求助

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

» 猜你喜欢

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

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的回帖

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的回帖
相关版块跳转 我要订阅楼主 liufu 的主题更新
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 生物学学硕求调剂 +6 小羊睡着了? 2026-03-23 9/450 2026-03-24 20:21 by 小羊睡着了?
[考研] 0854 考研调剂 招生了!AI 方向 +5 pk3725069 2026-03-19 17/850 2026-03-24 17:30 by zhouxuan..
[考研] 277分求调剂,跨调材料 +3 考研调剂lxh 2026-03-24 3/150 2026-03-24 13:52 by JourneyLucky
[基金申请] 请教下大家 2026年国家基金申请是双盲审吗? +3 lishucheng1 2026-03-22 5/250 2026-03-24 08:22 by gltch
[考研] 284求调剂 +10 Zhao anqi 2026-03-22 10/500 2026-03-24 00:08 by Equinoxhua
[考研] 化学308分求调剂 +3 你好明天你好 2026-03-23 3/150 2026-03-23 20:11 by macy2011
[考研] 生物学一志愿985,分数349求调剂 +6 zxts12 2026-03-21 9/450 2026-03-23 18:37 by macy2011
[考研] 求老师收我 +3 zzh16938784 2026-03-23 3/150 2026-03-23 12:56 by ztnimte
[考研] 一志愿华中农业071010,总分320求调剂 +5 困困困困坤坤 2026-03-20 6/300 2026-03-22 17:41 by hxsm
[考研] 寻找调剂 +4 倔强芒? 2026-03-21 4/200 2026-03-22 16:14 by 木托莫露露
[考研] 311求调剂 +3 26研0 2026-03-20 3/150 2026-03-22 14:46 by ColorlessPI
[考研] 一志愿东华大学控制学硕320求调剂 +3 Grand777 2026-03-21 3/150 2026-03-21 19:23 by 简之-
[考研] 材料与化工(0856)304求B区调剂 +3 邱gl 2026-03-20 7/350 2026-03-21 19:05 by 15709483992
[考研] 336求调剂 +5 rmc8866 2026-03-21 5/250 2026-03-21 17:24 by 学员8dgXkO
[考研] 0805材料320求调剂 +3 深海物语 2026-03-20 3/150 2026-03-21 15:46 by 无际的草原
[考研] 求调剂 +3 白QF 2026-03-21 3/150 2026-03-21 13:12 by zhukairuo
[考研] 华东师范大学-071000生物学-293分-求调剂 +3 研究生何瑶明 2026-03-18 3/150 2026-03-21 01:30 by JourneyLucky
[考研] 一志愿武理材料305分求调剂 +6 想上岸的鲤鱼 2026-03-18 7/350 2026-03-21 01:03 by JourneyLucky
[考研] 一志愿重庆大学085700资源与环境专硕,总分308求调剂 +3 墨墨漠 2026-03-18 3/150 2026-03-21 00:39 by JourneyLucky
[考研] 320求调剂0856 +3 不想起名字112 2026-03-19 3/150 2026-03-19 22:53 by 学员8dgXkO
信息提示
请填处理意见