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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 应用数学与力学 » 请教一个图论的题
61/1返回列表
查看: 1169  |  回复: 5
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

wodeqqfeixue

木虫 (正式写手)

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

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

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2013-04-03 16:00:10
已阅   回复此楼   关注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 的主题更新
61/1返回列表
普通表情 龙 兔 虎 猫
信息提示
关闭
请填处理意见
关闭