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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 应用数学与力学 » graph coloring
北京石油化工学院2026年研究生招生接收调剂公告
41/1返回列表
查看: 485  |  回复: 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返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 22408 359分调剂 +3 Qshers 2026-03-27 4/200 2026-03-28 16:45 by Qshers
[考研] 本科双非材料，跨考一志愿华电085801电气，283求调剂，任何专业都可以 +5 芝士雪baoo 2026-03-28 6/300 2026-03-28 15:25 by 1018329917
[考研] 一志愿北京工业大学，324分求调剂 +4 零八# 2026-03-28 4/200 2026-03-28 15:01 by 17865157980
[考研] 材料求调剂一志愿哈工大324 +7 闫旭东 2026-03-28 9/450 2026-03-28 08:51 by Xu de nuo
[考研] 322求调剂 +6 宋明欣 2026-03-27 6/300 2026-03-28 07:08 by wangy0907
[考研] 07化学280分求调剂 +10 722865 2026-03-23 10/500 2026-03-27 15:51 by Plutoqq
[考研] 材料292调剂 +12 橘颂思美人 2026-03-23 12/600 2026-03-27 15:44 by caszguilin
[考研] 考研化学308分求调剂 +10 你好明天你好 2026-03-23 12/600 2026-03-27 14:43 by shangxh
[考研] 305求调剂 +5 哇卢卡库 2026-03-26 5/250 2026-03-27 14:01 by laoshidan
[考研] 一志愿北京化工大学材料与化工 264分各科过A区国家线 +10 哈哈157349 2026-03-21 10/500 2026-03-27 13:06 by zzll406
[考研] 调剂推荐 +5 清酒714 2026-03-26 6/300 2026-03-27 11:12 by 不吃魚的貓
[考研] 求调剂 +6 林之夕 2026-03-24 6/300 2026-03-27 08:38 by hypershenger
[考研] 325求调剂 +5 李嘉图·S·路 2026-03-23 5/250 2026-03-27 00:42 by wxiongid
[考研] 342求调剂 +3 加油a李zs 2026-03-26 3/150 2026-03-27 00:29 by wxiongid
[考研] 349求调剂 +4 李木子啊哈哈 2026-03-25 4/200 2026-03-26 22:49 by fmesaito
[考研] 生物学 296 求调剂 +4 朵朵- 2026-03-26 6/300 2026-03-26 19:01 by 不吃魚的貓
[考研] 282求调剂 +3 wcq131415 2026-03-24 3/150 2026-03-25 12:16 by userper
[考研] 0854电子信息求调剂 324 +4 Promise-jyl 2026-03-23 4/200 2026-03-25 11:36 by Sugarlight
[考研] 340求调剂 +5 话梅糖111 2026-03-24 5/250 2026-03-25 06:53 by ilovexiaobin
[考研] 306求调剂 +5 来好运来来来 2026-03-22 5/250 2026-03-22 16:17 by BruceLiu320
信息提示
关闭
请填处理意见
关闭