第一部分 --- 欧拉图
1.在经过所有边的前提下,欧拉通路(回路)必定是最小的通路(回路),因为它经过每条边且只经过一次,没有比这更小的情况了。
2.回路一定是通路,但通路不一定是回路
1.入度比出度大1的结点是有向图中的欧拉通路的终点,入度比出度小1的结点则是始点
所谓的割边就是:
边A是连通图G中的一条边,如果连通图中删去这条边A后图不连通,则称边A为割边。
第二部分 --- 哈密顿图
1.将哈密顿提出的正十二面体投影到平面中,我们就可以得到右边那个图了
2.有了投影图之后,哈密顿提出的立方体问题也就转变为了平面点线问题了
1.只有具有 哈密顿回路 的图才能够称为哈密顿图
2.哈密顿通路(回路)和欧拉通路(回路)的区别:
哈密顿通路(回路)需要经过图中每个结点一次且仅一次(如果是回路的话允许从起点出发以及最终回到起点)欧拉通路(回路)需要经过图中每条边一次且仅一次
注意只有哈密顿图(具有哈密顿回路)才有上面的推论和下面的证明思路
1.证明思路:哈密顿图是原图的生成子图(点集相同,但是边集是子集),在生成子图中删去和原图中一样的结点时,由于子图的边集 ≤ 原图边集 , 所以我们在子图中得到的连通分支数 ≥ 原图
所以我们只需要证明在哈密顿图(生成子图)中删除结点后得到的连通分支数 ≤ 删去的点数,就能够传递证明原图删除相同结点后得到的连通分支数 ≤ 删去的点数
1.只有哈密顿通路的时候也有一个必要条件,哈密顿回路的必要条件是哈密顿通路的必要条件的加强版
2.满足必要条件的图不一定是哈密顿图,但是不满足的一定不是,所以我们常常用这个必要条件来判断某些图不是哈密顿图
3.有割点的图一定不是哈密顿图,为什么呢?
割点的定义是:在原图中删去这个点后图中就会出现两个或两个以上的连通分支,根据定义我们可知,当删去割点时原图必不满足哈密顿图的充分条件,所以有割点的图一定不是哈密顿图
4.当我们根据定理去删原图中的结点的时候,我们应该删除那些结点呢?
答:我们应该删除那些图中具有最高度数的结点,这些高度数的结点对图的连通性影响大,删除它们的效果更明显。
1.简单图:既没有平行边也没有结点自己和自己连接的环状线
2.上面这个定理的证明较为冗长麻烦,咱这里就省掉了
3.哈密顿回路的充分条件则是哈密顿通路的加强版
1.充分条件:有A一定有B,A是B的充分条件
2.必要条件:无A一定无B,A是B的必要条件
3.充要条件:有A一定有B,无A一定无B,A是B的充分必要条件文章来源:https://www.toymoban.com/news/detail-502634.html
文章来源地址https://www.toymoban.com/news/detail-502634.html
到了这里,关于离散数学 --- 特殊图 --- 欧拉图,哈密顿图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!