哈密尔顿圈有什么作用?
发布网友
发布时间：2024-10-16 15:15
共1个回答
热心网友
时间：2024-10-16 15:43
本题考查哈密顿图的知识，具体解题思路和答案如下：
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完全的。
参考资料来源：百度百科-哈密顿图
