24小时热门版块排行榜    

查看: 1182  |  回复: 5

wodeqqfeixue

木虫 (正式写手)

[求助] 请教一个图论的题

有来自不同国家的6个人,已知每个人都能用相应的语言与其余至少3人相互对话。问能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人交谈?
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐,对您同样有帮助:

已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

lei50566

木虫 (小有名气)

【答案】应助回帖


wodeqqfeixue: 金币+1, 有帮助 2013-05-15 20:00:59
个人认为是可以的,每个点只与左右邻近的点通信,只需要六条边就可以做到了!
爱家人爱自己
2楼2013-05-15 14:55:40
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

dameng

银虫 (小有名气)

【答案】应助回帖


wodeqqfeixue: 金币+1, ★★★很有帮助 2013-05-17 17:46:14
现翻的书...
答案是肯定的。下面有一般化的定理:
如果G至少3个顶点,且最小度至少是顶点个数的一半,则G是哈密顿图。
具体证明过程见《图论导引》(中文第二版)的定理7.2.8

PS:楼上的肯定不对!因为是要证明:对于随机的语言组合,都可以合理安排座位。而不是先做好座位,再安排每个人的语言。
研究方向:数据库。主要面向图数据管理、图数据挖掘、社会网络等。目前正在关注动态图算法。
3楼2013-05-16 19:45:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yangrui123

金虫 (小有名气)

【答案】应助回帖

这个问题嘛,其实要安排是一个很简单的问题,但是要求有多少种安排的方法就会比较麻烦
乐观,自信,爱是我的生活态度,也希望以此能都影响大家
4楼2013-05-17 15:36:03
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

共振构型

新虫 (小有名气)

【答案】应助回帖

2楼的回答很专业啊, 知道存在Hamilton Cycle 就行了
5楼2013-07-26 16:19:33
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

308032562

金虫 (小有名气)

【答案】应助回帖

三个能交流的分别做其左右与对面。
画一圆桌,顺讯1至6编号,以1号为例,圆桌决定了左右一定是能交流的,故2,6。那么另外一个能交流的就是3,4或5了,三选一。假如是4,即1对面的位置。列表后观察,可满足上面的条件。
6楼2013-07-27 19:12:24
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 wodeqqfeixue 的主题更新
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 面上模板改不了页边距吧? +5 ieewxg 2026-02-25 6/300 2026-03-01 00:10 by addressing
[考研] 317一志愿华南理工电气工程求调剂 +5 Soliloquy_Q 2026-02-28 8/400 2026-02-28 23:36 by xyx2012xyx
[考研] 292求调剂 +3 yhk_819 2026-02-28 3/150 2026-02-28 21:57 by gaoxiaoniuma
[考研] 290求调剂 +5 材料专硕调剂; 2026-02-28 6/300 2026-02-28 21:40 by gaoxiaoniuma
[考研] 295求调剂 +5 19171856320 2026-02-28 5/250 2026-02-28 21:39 by gaoxiaoniuma
[考研] 材料学调剂 +5 提神豆沙包 2026-02-28 5/250 2026-02-28 21:34 by gaoxiaoniuma
[考研] 264求调剂 +3 巴拉巴拉根556 2026-02-28 3/150 2026-02-28 21:31 by gaoxiaoniuma
[考研] 311求调剂 +8 南迦720 2026-02-28 8/400 2026-02-28 21:30 by gaoxiaoniuma
[考研] 材料类求调剂 +6 wana_kiko 2026-02-28 6/300 2026-02-28 21:20 by gaoxiaoniuma
[考研] 高分子化学与物理调剂 +4 好好好1233 2026-02-28 7/350 2026-02-28 20:42 by 好好好1233
[考研] 085600材料工程一志愿中科大总分312求调剂 +8 吃宵夜1 2026-02-28 10/500 2026-02-28 20:27 by L135790
[考研] 276求调剂 +3 路lyh123 2026-02-28 4/200 2026-02-28 19:45 by 路lyh123
[考研] 0856材料求调剂 +10 hyf hyf hyf 2026-02-28 11/550 2026-02-28 18:50 by 无际的草原
[考研] 285求调剂 +5 满头大汗的学生 2026-02-28 5/250 2026-02-28 18:10 by 材料专硕调剂;
[考博] 博士自荐 +3 kkluvs 2026-02-28 3/150 2026-02-28 16:59 by StarAura
[考研] 265分求调剂不调专业和学校有行学上就 +4 礼堂丁真258 2026-02-28 6/300 2026-02-28 16:18 by 求调剂zz
[考研] 寻找调剂 +3 LYidhsjabdj 2026-02-28 3/150 2026-02-28 12:59 by miniwendy
[考研] 272求调剂 +3 田智友 2026-02-28 3/150 2026-02-28 12:31 by 王加浩to
[考研] 298求调剂 +4 axyz3 2026-02-28 4/200 2026-02-28 11:21 by wang_dand
[基金申请] 面上可以超过30页吧? +12 阿拉贡aragon 2026-02-22 13/650 2026-02-26 22:09 by Hahaxia
信息提示
请填处理意见