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

24小时热门版块排行榜    

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

金虫 (小有名气)

【答案】应助回帖

不会。
下面的想法，仅供参考。
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 个回答

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的回帖
查看全部 4 个回答
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 基金系统什么内容也没有 30+4 winsaint 2026-08-27 9/450 2026-08-28 11:06 by maolC
[基金申请] 怎么查啊 +6 huang1991js 2026-08-26 6/300 2026-08-28 08:42 by winsaint
[基金申请] 哪位高人中了，把查询到的截图贴出来让我看看，让我长长见识 +5 yuleib84 2026-08-26 6/300 2026-08-28 00:02 by yudaoqian88
[基金申请] 申请删除本帖 +6 lyz123lyz 2026-08-27 7/350 2026-08-27 17:31 by 宁静致远sy
[基金申请] 基金不中，共勉 +10 eulota 2026-08-26 10/500 2026-08-27 17:23 by lqllinqiaoli
[基金申请] 基金未中，这种答复是模板吗？ +5 zhaosm1982 2026-08-27 6/300 2026-08-27 16:00 by lfy8008
[文学芳草园] 梦想 +3 myrtle 2026-08-26 3/150 2026-08-27 10:01 by angelyueyi
[基金申请] 为什么 国际(地区)合作与交流项目 没有放榜？ 10+3 majunge000 2026-08-26 11/550 2026-08-27 08:42 by 北京莱茵编辑
[基金申请] 2026年的国家社科基金项目通讯评审的新规则与新动向、新挑战 +7 process2012 2026-08-23 10/500 2026-08-26 19:23 by hmhminy
[基金申请] 2026国自然函评费到账 +22 羊腰板 2026-08-21 25/1250 2026-08-26 15:00 by zuocuiping
[基金申请] 为什么国自然不能直接公布 +4 bjdxyxy 2026-08-26 4/200 2026-08-26 13:12 by qingmu1201
[基金申请] 国合里面能看到了 +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
[基金申请] 今天务委会开完了，明天出结果吗 +19 angus9576 2026-08-25 23/1150 2026-08-26 10:03 by zp519
[职场人生] 学生撞见辅导员送外卖，第二天全班都沉默了 +3 鲸鱼融金_浙江_� 2026-08-22 3/150 2026-08-26 09:01 by zzuzxg
[基金申请] 国合现在查不到了吗？ +10 chengyan1220 2026-08-24 20/1000 2026-08-26 08:57 by peasantsprig
[基金申请] 在坚冰还盖着北海的时候，我看到了怒放的梅花。 (金币+10) +6 ziyangfang 2026-08-25 9/450 2026-08-25 20:26 by huagongfeihu
[基金申请] 明天应该可查了！？ +6 chengyan1220 2026-08-23 6/300 2026-08-25 19:45 by zfd97
[基金申请] 如果此刻你正在为国基感到焦虑，不妨来听听这首《基金之外》 +8 scalable 2026-08-24 8/400 2026-08-25 12:52 by jnhyjjm
信息提示
关闭
请填处理意见
关闭