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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 应用数学与力学 » graph coloring
41/1返回列表
查看: 568  |  回复: 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返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 YLHlRHNwYkce 2026-09-02 7/350 2026-09-03 18:50 by jyNB2vrbdUpR
[硕博家园] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +4 YLHlRHNwYkce 2026-09-02 8/400 2026-09-03 18:50 by jyNB2vrbdUpR
[找工作] 售SCI一区T0P文章，我:8O.55.1.O.54,科目全,可伽急 +4 YLHlRHNwYkce 2026-09-02 11/550 2026-09-03 18:42 by jyNB2vrbdUpR
[硕博家园] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 rFEsUBKXRll0 2026-09-02 6/300 2026-09-03 16:49 by T0rGB46095mJ
[硕博家园] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 ero8OE6tv9cu 2026-09-02 5/250 2026-09-03 16:38 by T0rGB46095mJ
[教师之家] 售SCI一区T0P文章，我:8.O55.1.O.54,科目全,可十急 +3 ero8OE6tv9cu 2026-09-02 8/400 2026-09-03 14:48 by T0rGB46095mJ
[基金申请] 国社科又开始会评了，不知道这次命运如何 +10 雨打竹帘 2026-08-30 14/700 2026-09-03 13:17 by qsd10086
[公派出国] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +3 ero8OE6tv9cu 2026-09-02 4/200 2026-09-03 03:14 by rM1TE0WVDIIY
[基金申请] 科研人应该花精力去思考如何解决问题，而不是去凝练问题 +7 瞬息宇宙 2026-09-01 14/700 2026-09-02 17:33 by ma0526
[基金申请] 学科评审组评审是指会评吗？ +5 瞬息宇宙 2026-08-31 5/250 2026-09-02 10:13 by 雨冰共舞
[基金申请] 面上函评意见出来了，像什么等级？ 20+4 Tsingking1 2026-08-27 17/850 2026-09-01 19:51 by 超级无敌华子
[论文投稿] 小白求助 投论文要求的highlights应该如何写 5+3 l1963982152 2026-08-29 4/200 2026-09-01 09:04 by 北京莱茵编辑
[基金申请] 面上意见出来了 +12 黄鸟于飞Chao 2026-08-29 23/1150 2026-08-31 18:57 by 黄鸟于飞Chao
[基金申请] 能否申诉？ +7 echo8914667 2026-08-30 8/400 2026-08-31 17:00 by yihongxu
[基金申请] 中青基了要发朋友圈吗？ +7 349506619 2026-08-28 7/350 2026-08-31 13:39 by 冼亮淀粉酶
[基金申请] 29号明天会评吗 +4 笨笨唐 2026-08-28 4/200 2026-08-31 09:30 by huixian257
[基金申请] 为什么到现在没收到通知？ +5 tannykie 2026-08-29 5/250 2026-08-30 21:05 by purplejack
[考博] 找导师 +6 yuanjiabao 2026-08-29 7/350 2026-08-30 14:40 by 生科新手
[基金申请] 我就是申请一个面上项目而已，这评审意见是按照杰青的条件评的吧？ +6 gouxfjh 2026-08-28 11/550 2026-08-30 07:57 by gouxfjh
[基金申请] 国自然评审意见 +13 wangmingqi 2026-08-28 19/950 2026-08-29 10:22 by Poppy1104
信息提示
关闭
请填处理意见
关闭