今有a,b,c,d,e,f,g共七个人,已知下列事实,a会讲汉语和英语;b会讲英语和韩语

Question

已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以,用离散数学的解法计算

Answer 1

本题考查哈密顿图的知识，具体解题思路和答案如下：

1、设7个顶点A、B、C、D、E、F、G对应这7名数学家，其中会用同一种语言的人对应的顶点之间连一条边，这样就得到了一个图，如下图6-2。

2、于是原来的排座问题就变成了了在图6-2中找一条哈密顿图的问题了。按圈上顶点的顺序来排座位，那么每个人和他相邻的两个人都能交谈。

3、如果按照A、B、C、D、E、F、G的顺序排座位，每个人就都可以和他的两个邻座交谈，所采用的语言种类标在图6-3中的对应边上。

扩展资料

离散数学哈密顿圈的判断定理：

1、 设无向图G是哈密顿图，V1是V的任意的非空子集， p(G-V1)≤|V1| 其中，p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得到的图的连通分支。

2、设G是n(n≥3)阶无向简单图，如果G中任何一对不相邻的顶点度数之和都大于等于n，则G是哈密顿图。

3、在n(n≥2)阶有向图D=中，如果所有有向边均用无向边代替，所得无向图中含生成子图Kn，则有向图中存在哈密顿图。推论： n(n≥3)阶有向完全图为哈密顿图。

4、哈密顿路径也称作哈密顿链，指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP完全的。

参考资料来源：百度百科-哈密顿图