欢迎来到天天文库
浏览记录
ID：57132264
大小：130.50 KB
页数：19页
时间：2020-08-01
《有关汉密尔顿回路的定理课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、汉密尔顿图与欧拉回路非常类似的问题是汉密尔顿回路的问题。1859年，威廉·汉密尔顿爵士在给他朋友的一封信中，首先谈到关于十二面体的一个数学游戏：能不能在图中找到一条回路，使它含有这个图的所有结点？他把每个结点看成一个城市，联结两个结点的边看成是交通线。于是他的问题就是能不能找到旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的出发地，他把这个问题称为周游世界问题。定义1给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图。定理1若图G=具有汉密尔顿
2、回路，则对于结点集V的每个非空子集S均有W(G-S)≤
3、S
4、成立。其中W(G-S)是G-S中连通分支数。彼得森图（Petersen）定理2设G具有n个结点的简单图，如果G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路。定理3设G是具有n个结点的简单图。如果G中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿回路。定义2给定图G=有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G’，对图G’重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包，记作C(G)。定理4当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉
5、密尔顿图。
此文档下载收益归作者所有
