今有a,b,c,d,e,f共6人，已知下列事实: a会讲德语、英语、法语和汉语; b会讲德语、朝鲜 语和意大利语;c会讲俄语、意

今有a,b,c,d,e,f共6人，已知下列事实: a会讲德语、英语、法语和汉语; b会讲德语、朝鲜 语和意大利语;c会讲俄语、意大利语、西班牙语和葡萄牙语; d会讲俄语、日语和法语,e会讲葡萄牙语、日语和英语; f会讲汉语、朝鲜语和西班牙语。试问这6个人应如何排座位，才能使每个人和他身边的人用同语言交谈?列出所有可能的排座方案。
【正确答案】：

解：利用图论来解决，以每个人为结点V，边为E={〈u，v〉|u，v∈V且u和v有共同语言}，可以画出图G如下图所示。该图为哈密顿图，存在以下4个哈密顿回路：aedcfba，aedcbfa， adecfba， adecbfa。将此6人按照上述次序围桌排座，就使得每个人都能与两侧的人用同种语言交流。

【题目解析】：本题主要是把人与语言转换为结点与边，然后运用图论理论解决问题。