欧拉图
欧拉图的定义
欧拉通路（回路）：设\(G\)是无孤立结点的无向图或有向图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路).
欧拉图：具有欧拉回路的图称为欧拉图.(平凡图也是是欧拉图)
欧拉图的判定
无向图
- 欧拉通路：无向图\(G=<V,E>\)具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。（若连通的无向图有两个奇度数结点,则它们是G中每条欧拉通路的端点）
- 欧拉回路：无向图\(G=<V,E>\)具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数
有向图
- 欧拉通路：有向图\(G\)具有一条欧拉通路,当且仅当\(G\)是连通的,且除了两个结点以外，其余结点的人度等于出度，而这两个例外的结点中，一个结点的人度比出度大1，另一个结点的出度比入度大1.
- 欧拉回路：有向图\(G\)具有一条欧拉回路，当且仅当$G是连通的，且所有结点的入度都等于出度.
找欧拉图的3种技巧
- 直接一笔画
- 使用构造性定理：
如果图中所有的边已用这种方式经过了，显然这就是所求的欧拉通路。
如果图中不是所有的边都经过了，就去掉已经过的边，得到一个由剩余的边组成的子图，这个子图必与已经过的通路在一个或多个结点相接。从这些结点中的一个开始，再通过边构造通路，这条通路一定最终回到始点。将这条回路加到已构造好的通路中间组合成一条通路。将这一过程重复下去，直到得到一条通过图中所有边的通路 - Fleury算法：
哈密顿图
哈密顿图的定义
哈密顿通路（回路）：对于无向图或有向图，经过图中每个结点一次且仅一次的通路(回路)称为哈密顿通路(回路)
哈密顿图：存在哈密顿回路的图称为哈密顿图.(平凡图为哈密顿图)
平行边与自回路存在与否不影响图中是否存在哈密顿通路(回路)，因而约定在以后讨论的图均为连通的简单图
哈密顿图的判定
无向图中哈密顿的判定
必要条件（删点数连通）
- 哈密顿图：
- 哈密顿通路：
删点时可以找一些度数较高的点去试
必要条件多用于证伪（证不存在）
充分条件（数度数）
- 哈密顿通路：
- 哈密顿图：
其它充分条件（少用）
- 标记法：会失效，少用。如果标完后存在两个相邻结点标记相同则失效。
例题：
判定图a是否存在哈密顿回路
（b）图b为使用必要条件求解，删掉若干点后连通数量过多即能说明不存在哈密顿图
（c）图c为使用定义进行推断：
利用哈密顿回路的性质,若存在哈密顿回路,则该回路组成的图中任何结点的度数均为⒉因此度数为2的结点所关联的边都在哈密顿回路中,度数大于n (n>2)的结点所关联的边中有n-2条不在哈密顿回路中,应予以删除,如果这样得到的图不连通,则图中不存在哈密顿回路．
*不重要内容：
利用扩大基本通路法+寻找基本回路对定理11.3.1的巧妙证明
有向图中哈密顿的判定
*哈密顿图的应用
抄近路算法求TSP近似解
算法过程
- 求\(G\)中的一棵最小生成树\(T\)
- 将\(T\)中各边均加一条与原边权值相同的平行边，设所得图为\(G'\)，显然\(G'\)是欧拉图
- 在\(E\)中按如下方法求从结点\(v\)出发的一个哈密顿回路\(H\)：从\(v\)出发,沿\(E\)访问\(G'\)中的各个结点，在没有访问完所有结点之前，一旦出现重复出现的结点，就跳过它走到下一个结点
与最优解的差距
抄近路算法过程例子：
中国邮路问题的最优解法
中国邮路问题的等价定义：在一个有奇度数结点的赋权连通图中,增加一些平行边,使得新图不含奇度数结点,并且增加边的总权值最小.
算法过程
- 确定可行方案：在配好对的奇度数结点之间各确定一条基本通路，然后将通路中的所有边均加一条平行边，这样产生的新图中无奇度数结点，因而存在欧拉回路
- 调整可行方案：
- 在最优方案中，图中每条边的重数小于或等于2.
- 在最优方案中，图中每个基本回路上平行边的总权值不大于该回路的权值的一半.
算法过程例子：
其中(a)是原图，(b)是可行方案，(c)是不断调整后的最优方案
