离散数学 --- 特殊图 --- 欧拉图，哈密顿图

第一部分 --- 欧拉图

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的充分必要条件