应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 应用数学与力学 » graph coloring
北京石油化工学院2026年研究生招生接收调剂公告
41/1返回列表
查看: 488  |  回复: 3
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

hzsh2009

铜虫 (小有名气)

[求助] graph coloring

Suppose a map is made by drawing n intersecting circles. Show that the regions in this map can be properly 2-colored


Solve by assigning colors based on number of circles that contain a region
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2011-10-01 08:52:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

YANGZL

金虫 (小有名气)

【答案】应助回帖

★
soliton923(金币+1): 谢谢参与讨论~~你回帖就行了，没有必要每个都需要举报给版主处理，呵呵 2011-10-01 17:56:42
应该不可以。
圆圈相交后，就是平面图。用四色就可以。

关键是怎么相交的？如果相交出 Kuratowski graph k3,3 k5，那么4色也不够。
赞一下(1人) 回复此楼
真傻（求真）
2楼2011-10-01 12:57:53
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hzsh2009

铜虫 (小有名气)
引用回帖:
2楼: Originally posted by YANGZL at 2011-10-01 12:57:53:
应该不可以。
圆圈相交后，就是平面图。用四色就可以。

关键是怎么相交的？如果相交出 Kuratowski graph k3,3 k5，那么4色也不够。

首先它是一个planar graph（题目给的），然后它应该就是圆圈相交，如果只有顶点交不算相连的。所以2色够了。但不知道怎么证。。
赞一下 回复此楼
3楼2011-10-01 20:50:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

YANGZL

金虫 (小有名气)

【答案】应助回帖

不会。
下面的想法，仅供参考。
Cycle graphs shi 2着色的。2个 circles intersect，会会形成3个circles。n intersecting circles，会成不超过“组合数”的circles。
不知道这个思路有没有用。

俺不是学数学的，只是数学爱好者。没有能力保证解答的价值。

俺瞎想：
made by drawing，可不能保证结果一定平面图啊！
k3,3 k5 也是在平面上drawn的啊，只是它们的连接方式奇特了点。
赞一下 回复此楼
真傻（求真）
4楼2011-10-02 09:05:55
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 hzsh2009 的主题更新
41/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[硕博家园] 招收生物学/细胞生物学调剂 +4 IceGuo 2026-03-26 5/250 2026-03-29 01:25 by griffith2014
[考研] 调剂310 +7 温柔的晚安 2026-03-25 8/400 2026-03-29 01:09 by 我是小康
[考研] 305求调剂 +7 RuiFairyrui 2026-03-28 7/350 2026-03-29 00:40 by 544594351
[考研] 315求调剂 +4 akie... 2026-03-28 5/250 2026-03-28 21:05 by zhq0425
[考研] 085600，材料与化工321分求调剂 +9 大馋小子 2026-03-28 9/450 2026-03-28 14:56 by 神马都不懂
[考研] 347求调剂 +3 山顶见α 2026-03-25 3/150 2026-03-28 14:13 by 唐沐儿
[考研] 317求调剂 +6 十闲wx 2026-03-24 6/300 2026-03-28 13:27 by Iveryant
[考研] 材料与化工考研调剂 +17 孅華 2026-03-22 17/850 2026-03-28 08:35 by WYUMater
[考研] 086000调剂 +3 7901117076 2026-03-26 3/150 2026-03-27 21:34 by Jianing_Mi
[考研] 266求调剂 +11 阳阳哇塞 2026-03-27 12/600 2026-03-27 17:56 by yu221
[考研] 调剂 +3 李嘉图·S·路 2026-03-27 3/150 2026-03-27 11:19 by wangjy2002
[考研] 求调剂 +6 林之夕 2026-03-24 6/300 2026-03-27 08:38 by hypershenger
[考研] 总分293求调剂 +6 加一一九 2026-03-25 8/400 2026-03-26 13:30 by yujianx
[考研] 290分调剂求助 +3 吉祥止止陈 2026-03-25 3/150 2026-03-25 19:58 by barlinike
[考研] 材料专硕 335 分求调剂 +4 拒绝冷暴力 2026-03-25 4/200 2026-03-25 18:45 by haxia
[考研] 一志愿吉林大学材料与化工303分求调剂 +4 为学666 2026-03-24 4/200 2026-03-25 11:27 by BruceLiu320
[考研] 生物学学硕求调剂 +7 小羊睡着了? 2026-03-23 10/500 2026-03-25 02:24 by 清风拂扬。 m
[考研] 调剂 +4 13853210211 2026-03-24 4/200 2026-03-24 19:44 by ms629
[考研] 328求调剂 +4 LHHL66 2026-03-23 4/200 2026-03-23 14:55 by lbsjt
[考研] 275求调剂 +6 shansx 2026-03-22 8/400 2026-03-22 15:27 by barlinike
信息提示
关闭
请填处理意见
关闭