第一部分 --- 欧拉图
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模板网！
![[云原生] 二进制安装K8S一部分](https://imgs.yssmx.com/Uploads/2024/02/835642-1.png)
