24小时热门版块排行榜    

Znn3bq.jpeg
查看: 1198  |  回复: 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 的主题更新
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 求调剂 +8 张番茄不炒蛋 2026-04-10 8/400 2026-04-10 18:21 by 小小树2024
[考研] 314求调剂 +23 wakeluofu 2026-04-09 24/1200 2026-04-10 15:31 by MOF_Catal
[考研] 282,电气工程专业,求调剂,不挑专业 +9 jggshjkkm 2026-04-10 9/450 2026-04-10 14:55 by 逆水乘风
[考研] 调剂申请086000一志愿西北农林科技大学生物与医药320分-本科齐鲁工业大学 +3 美美女士 2026-04-09 3/150 2026-04-10 10:31 by liuhuiying09
[考研] 083200 305分 求二轮调剂 不接受跨专业 +8 Claireyyyy 2026-04-09 8/400 2026-04-10 10:05 by luosha500
[考研] 青岛科技大学材料学院,环境学院调剂补录4月10日以前都可以 +3 1青科大。 2026-04-09 5/250 2026-04-10 09:58 by 翩翩一书生
[考研] 085404 293求调剂 +7 勇远库爱314 2026-04-08 7/350 2026-04-09 16:02 by 猪会飞
[考研] 274求调剂 +5 山阿蔓 2026-04-07 5/250 2026-04-09 15:28 by 18828373951
[考研] 化学调剂求助 +14 LULONG1 2026-04-03 19/950 2026-04-09 10:43 by chenxi233
[考研] 285求调剂 +12 AZMK 2026-04-05 18/900 2026-04-08 20:43 by 逆水乘风
[考研] 求调剂 一志愿西南交通大学085701环境工程 282分 +15 多多爱吃汉堡 2026-04-04 16/800 2026-04-08 11:39 by i_cooler
[考研] 265求调剂 +19 小木虫085600 2026-04-06 21/1050 2026-04-08 10:38 by 逆水乘风
[考研] 求考研材料调剂 +3 材化李可 2026-04-07 3/150 2026-04-08 00:21 by JourneyLucky
[考研] 材料求调剂 +18 一样YWY 2026-04-05 18/900 2026-04-07 15:49 by dxlg
[考研] 生物学学硕求调剂:351分一志愿南京师范大学生物学专业 +6 …~、王…~ 2026-04-06 7/350 2026-04-06 18:54 by macy2011
[考研] 346分的生物与医药08600求调剂 +6 常雨阳上岸 2026-04-05 7/350 2026-04-06 12:36 by lys0704
[考研] 一志愿南航,数一英一学硕317求调剂!! +6 Acaciad 2026-04-04 6/300 2026-04-06 12:13 by 考研学校招点人
[考研] 332求调剂 +17 小小孟... 2026-04-05 18/900 2026-04-06 09:51 by 蓝云思雨
[考研] 22408 总分320,一篇论文二作,两个国三,求调剂 +3 Leomulufu 2026-04-04 5/250 2026-04-05 19:04 by chongya
[考研] 316求调剂 +9 墨辰_Orion926 2026-04-04 9/450 2026-04-04 21:35 by lbsjt
信息提示
请填处理意见