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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 应用数学与力学 » graph coloring
51/1返回列表
查看: 566  |  回复: 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的回帖

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的回帖
查看全部 4 个回答

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

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的回帖
查看全部 4 个回答
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 怎么查啊 +6 huang1991js 2026-08-26 6/300 2026-08-28 08:42 by winsaint
[基金申请] 基金系统什么内容也没有 30+4 winsaint 2026-08-27 8/400 2026-08-28 08:26 by lfy8008
[硕博家园] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +3 XLGfUIdOmEAO 2026-08-27 3/150 2026-08-28 00:49 by 3RAFyYXYSwGS
[基金申请] 哪位高人中了，把查询到的截图贴出来让我看看，让我长长见识 +5 yuleib84 2026-08-26 6/300 2026-08-28 00:02 by yudaoqian88
[基金申请] 面上合作单位盖章 +5 ssyjh 2026-08-27 5/250 2026-08-27 20:50 by gdfollow
[基金申请] 申请删除本帖 +6 lyz123lyz 2026-08-27 7/350 2026-08-27 17:31 by 宁静致远sy
[基金申请] 怎么看青基中了没有啊 +5 叶九微 2026-08-26 5/250 2026-08-27 10:35 by l_zh2008
[教师之家] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 LIbGuocjEEYw 2026-08-26 4/200 2026-08-27 04:33 by Ie9AyIAvGbvs
[基金申请] 我不理解！ +15 Edward_pc 2026-08-26 23/1150 2026-08-26 20:34 by zzuzxg
[基金申请] 2026年的国家社科基金项目通讯评审的新规则与新动向、新挑战 +7 process2012 2026-08-23 10/500 2026-08-26 19:23 by hmhminy
[基金申请] 系统查不到 +10 董八千 2026-08-26 10/500 2026-08-26 16:30 by Equinoxhua
[基金申请] 2026国自然函评费到账 +22 羊腰板 2026-08-21 25/1250 2026-08-26 15:00 by zuocuiping
[基金申请] 2026年8月25日国自然放榜前突然收到列入评审专家邮件，有关系吗？ +25 木水思豆 2026-08-25 28/1400 2026-08-26 14:53 by draco1987
[基金申请] 国合里面能看到了 +7 一怀馨秋 2026-08-26 7/350 2026-08-26 11:23 by zhaosm1982
[基金申请] 国际合作可查了，中了面上 (EPI+1)(金币+50) +18 Ldrop2023 2026-08-26 18/900 2026-08-26 11:15 by cmrandy
[基金申请] 项目信息和经费信息在系统里都可以看到了 +6 wittyboy 2026-08-26 14/700 2026-08-26 10:55 by wittyboy
[基金申请] 国合可查了 +3 paperzjh 2026-08-26 3/150 2026-08-26 10:41 by LemmonTr
[基金申请] 在坚冰还盖着北海的时候，我看到了怒放的梅花。 (金币+10) +6 ziyangfang 2026-08-25 9/450 2026-08-25 20:26 by huagongfeihu
[教师之家] 跳槽后在研项目怎么办？ +5 简单化xn 2026-08-22 10/500 2026-08-23 12:38 by 简单化xn
[基金申请] 应该是下周三26日公布了吧？ +4 哈哈蛤？ 2026-08-21 4/200 2026-08-21 10:58 by Vivilian
信息提示
关闭
请填处理意见
关闭