（三）

1.3节 Hamilton Cycles and Euler Circuits 哈密顿圈和欧拉回路

本篇简要的介绍了概念和相关定理。首先明确一下，下面讨论有三种图：无向图(simple graph)，有向图(directed graph)以及（有向）混合图(directed multigraph)，混合图允许自己指向自己的边(loop)。混合图的基图(underlying graph)就是删去了这些边的有向图。

1. 定义：

如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)；

如果G中的圈C恰好经过每一个顶点一次，则称圈C是一个哈密顿圈(Hamilton Cycles)。

2. 定理：

    1. 众所周知，欧拉回路的研究始自Konigsberg七桥问题。Euler指出，(TH12) 连通图G有欧拉迹iff x\y为唯二奇度顶点，以及G为欧拉图iff顶点全为偶数。对有向图（混合图），则需要入度等于出度。这一定理可用割圈的方式证明。事实上，每一个欧拉回路都是一些不相交之圈的并。

    2. 关于Hamilton圈的TH11指出，Kn能被分割成不相交的Hamilton圈 iff n 是奇数，能被分割成不相交的Hamilton路 iff n是偶数。这一定理可以归纳的证明。

    3. 下面介绍TH13。这一定理对入度等于出度的混合欧拉图适用。对图G有如下等式成立： s(G)  = ti(G)Π(d+(vj)-1)!

    其中，s(G)是G欧拉回路的个数，ti(G)是朝向(oriented towards)i的生成树（OST）的个数(明显，t1 = t2 = ... = tn)。朝向i的生成树定义为：For every j!=i, the unique path from vi to vj is oriented towards vi.也就是以下三点：每个j出度1，i出度0，没有有向圈。

    证明这一定理，构造T，边为e2,...,en,其中ei是一条欧拉迹S中最后一次离开vi的那条边。不难证明T是OST。映射Π(S)=T，即求|Π-1(T)|。用简单的组合知识即得。

    4. TH14：G是无限多边的连通混合图，则G有一条双向欧拉迹 iff 满足：1.E可数 2. 边的度是偶数或无限大 3. 每个无限边的子图G'(V,E'), G - E'有至多两个无限连通分量。（进一步地，若G‘各点均为偶数度，G - E'有一个连通分量）。