24小时热门版块排行榜    

北京石油化工学院2026年研究生招生接收调剂公告
查看: 487  |  回复: 3
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

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
回复此楼
已阅   回复此楼   关注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色也不够。
真傻(求真)
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的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 081200-11408-276学硕求调剂 +5 崔wj 2026-03-26 5/250 2026-03-28 21:37 by 小木虫tim
[考研] 0703 化学 求调剂,一志愿山东大学 342 分 +3 Shern—- 2026-03-28 3/150 2026-03-28 21:24 by 唐沐儿
[考研] 一志愿北京化工大学材料与化工(085600)296求调剂 +11 稻妻小编 2026-03-26 11/550 2026-03-28 21:04 by 唐沐儿
[考研] 332求调剂 +5 蕉蕉123 2026-03-28 5/250 2026-03-28 20:50 by 唐沐儿
[考研] 材料求调剂一志愿哈工大324 +7 闫旭东 2026-03-28 9/450 2026-03-28 08:51 by Xu de nuo
[考研] 086502化学工程342求调剂 +6 阿姨复古不过 2026-03-27 6/300 2026-03-28 07:06 by wangy0907
[考研] 一志愿211院校 344分 东北农业大学生物学学硕,求调剂 +5 丶风雪夜归人丶 2026-03-26 8/400 2026-03-27 19:22 by 丶风雪夜归人丶
[考研] 316求调剂 +5 Pigcasso 2026-03-24 5/250 2026-03-27 12:10 by zhshch
[考研] 314求调剂 +3 溪云珂 2026-03-26 3/150 2026-03-27 11:20 by sanrepian
[考研] 304材料求调剂 +4 钟llll 2026-03-26 4/200 2026-03-27 03:42 by wxiongid
[考研] 329求调剂 +5 1() 2026-03-22 5/250 2026-03-26 20:40 by fmesaito
[考研] 化学工程085602 305分求调剂 +17 RichLi_ 2026-03-25 17/850 2026-03-26 19:44 by plmuchong
[考研] 中国科学院深圳先进技术研究院-光纤传感课题组招生-中国科学院大学、深圳理工大学联培 +5 YangTyu1 2026-03-26 5/250 2026-03-26 18:27 by 猫咪猫咪呀
[考研] 一志愿天津大学339材料与化工求调剂 +3 江往卖鱼 2026-03-26 3/150 2026-03-26 09:42 by 王小欠i
[考研] 材料与化工304求B区调剂 +3 邱gl 2026-03-25 3/150 2026-03-25 19:03 by Ainin_
[考研] 285求调剂 +3 AZMK 2026-03-24 3/150 2026-03-25 12:23 by userper
[考研] 一志愿吉林大学材料与化工303分求调剂 +4 为学666 2026-03-24 4/200 2026-03-25 11:27 by BruceLiu320
[考研] 材料考研调剂生 +3 黄粱一梦千年 2026-03-24 3/150 2026-03-24 17:00 by barlinike
[考研] 085404电子信息284分求调剂 +4 13659058978 2026-03-24 4/200 2026-03-24 12:15 by syl20081243
[考研] 求老师收我 +3 zzh16938784 2026-03-23 3/150 2026-03-23 12:56 by ztnimte
信息提示
请填处理意见