教材： 《离散数学》第2版kldlh dddhj张立昂高等教育出版社
源文档的高清截图在最后
第15章xfdkh和哈密顿图15.1 xfdkh 1，只通过图表中所有边一次的通路称为欧拉通路。 只通过图中所有边一次的回路称为欧拉回路。 具有欧拉回路的图为xfdkh，只具有欧拉通路的图为半xfdkh。 平凡的图(只有一个顶点的图)是xfdkh。
2、有向图g为xfdkh，且g为连通图，且仅当无奇度顶点时。
如果证明g是平凡图，显然成立。 将该图g(v，e )作为非平凡的图，拥有m条边和n个顶点。
必要性(左推)。 由于g是xfdkh，所以g中存在欧拉回路c。 对于任何vi，vjV，vi，vj都在c。 因此，vi、vj是连通的，g是连通图。 对于任意的viV，vi在c中每次出现都获得2个度(1个度和1个度)，所有的顶点在c中至少出现1次，所以g中没有奇度的顶点。
充分性(向右推)。 由于g是非平凡连通图，所以边数m1。 以下，关于m进行归纳证明。
当m=1时，g没有奇度的顶点，但由于g又连接在一起，所以g只能是一个环。 g为xfdkh。
如果当mk(k1 )时，结论都成立，则当m=k 1时，结论也成立。 因为没有g的连通性和奇度的顶点，所以g的最小度(g ) )为2。 可以证明g中一定含有圈。 设c为g中的圈，删除c中所有边后的剩余部分为g的1个生成子图g’。 g’有s个连接成分G1’、G2’、…、GS’，其中各连接成分最多有k条边，且没有奇度的顶点。 设gi’和c的共同顶点为I=1，2，…，s。 归纳假设，G1’、G2’、GS’均为xfdkh，存在欧拉回路。 设Ci为gi’的欧拉回路，I=1，2，s。 从某个顶点vr开始沿着c行走，遇到的话通过Ci，返回继续沿着c行走，最后返回vr。 于是，行走的这个回路，在g的生成部分图g的每个连接成分中，只经过一次g的一个回路c的所有共同顶点，以及生成部分图g’和c的所有边，行走的这个回路就是g的欧拉回路，g是xfdkh。
上述充分性证明是结构证明，提供了求欧拉回路的算法。 逐次插入电路法。
3、约翰内斯堡七桥问题的内容是，一个人如何不重复地走7座给定的桥(如下图)回到出发点。 很明显，要解决这个问题，要求求解这个图的欧拉回路。 但是，由于该图有4个奇度的顶点，所以没有解。
4、有向图g是半xfdkh，且g相连且正好有两个奇顶点。
证明必要性。 将该图g(v，e )作为m条边的n次无向图。 由于g是半xfdkh，所以g中存在欧拉通路，但不存在欧拉回路。 将该Euler路径设为=vi0ej1vi1ej2…ejmvim，并且设为vi0vim。 根据xfdkh的定义，g是连通的。 对于任意的vV，当v不是的端点时，如果它出现k次，则有v的度d(v )=2k。 如果v是的端点，则由于2个端点不同且不相邻，所以v作为端点只出现1次，只能得到1次。 如果v是端点，它可能多次作为非端点出现，每次获得2次。 所以d(v )是奇数。
充分性(向右推)。 设g的2个奇数顶点u，v，在g上增加新的边(u，v )，得到g(=g ()，v )。 g相连，没有奇度的顶点。 于是，g变为xfdkh，存在欧拉回路c’。 c=c’(u，v )是g的欧拉流路，g是xfdkh。
5、对于有向图，可以证明定理：
【1】有向图d为xfdkh，且只有d紧密相连，并且各顶点的入度与出度相等。
【2】有向图d为半xfdkh，且d沿一个方向相连，且正好有两个奇度顶点时。 一个顶点的入度比出度大1，另一个入度比出度大1，剩下的顶点的入度等于出度。
6、g是非平凡的xfdkh，且g相连，是几个边不重的环的并图。
用归纳法可以证明。
7、设g为非平凡的xfdkh，则g的边连通度(g ) )为2。
证明g不是一边-连通图即可。 也就是说，证g的任何一边e都不是桥(如果切掉边，去掉那一边的话，图就连接不上了)。 设c为欧拉回路，则由于e在c上，且ge的连通分支(连通分量)数p (ge )=p ) g )，所以e不是电桥。
8、闪存算法
用途：求欧拉回路。
基本思想：不过桥就不过桥。
输入： xfdkhg(v，e )。
1、任意取v0V，P0=v0，i=0。
2、假设Pi=v0e1v1e2…eivi，如果e{ E1，e2，…，ei}没有与vi相关的边，则停止计算。 否则，在以下条件下从e{ E1，e2，…，ei}中的任意一个中取边缘ei 1:
) a ) ei 1与vi的关联
) b )除非有其他可选择的边缘，否则不能是gi=g{ E1，e2，…，ei}的桥接器。
3、i=i 1，返回步骤2。
算法停止时，得到的简单电路Pm=v0e1v1e2…emvm为g的欧拉电路。
15.2汉密尔顿图1，只通过一次图表所有顶点的路径叫做汉密尔顿路径，只通过一次图表所有顶点的电路叫做汉密尔顿电路。 将具有哈密顿回路的图称为哈密顿图，将具有哈密顿回路但没有哈密顿回路的图称为半哈密顿图。
(从起点出发和到达终点不是经过) ) )。
平凡的照片是汉密尔顿的照片。 还没有找到判断哈密顿图的充分必要条件
件。2、设无向图G(V, E)是哈密顿图，则对任意的非空集，均有p(G – V1)≤|V1|。
证明 设C为G中的一条哈密顿回路。易知，当V1中的点在C上均不相邻（虽然V1的点都在C上，但两两不由一条边直连）时，p(C – V1)达到最大值|V1|（连通分量最大，即分成了尽可能多的互不连通的子图。删掉V1及其关联的边后，最多可以构造出|V1|个互不连通的子图。一种构造方法是：从起点开始依次给点编号（0或1开始均可），V1是全部编号为奇数的点）。而当V1的点在C上存在相邻情况时，总有p(C – V1) < |V1|。所以p(C – V1)≤|V1|。C是G的生成子图，所以p(G – V1)≤p(C – V1)≤|V1|。
本定理给出的是判定一个图是哈密顿图的必要条件，而不是充分条件。Peterson图满足该条件，但它不是哈密顿图。
推论 设无向图G(V, E)是半哈密顿图，则则对任意的非空集，均有p(G – V1)≤|V1| + 1。
证明 设P是G中从u到v的哈密顿通路，G’为在u，v之间加新边e得到的图，易知添加该边以后哈密顿通路变成哈密顿回路，G’为哈密顿图。于是p(G’ – V1)≤|V1|。而p(G – V1) = p(G’ – V1 – e)≤p(G’ – V1) + 1≤|V1| + 1。（提示：G – V1和G’ – V1 – e是完全相同的图，G’ – V1去掉e后可能会因为e是割边（桥）从而连通分量数 + 1）
3、设G是n阶无向简单图，若对G中任意不相邻顶点u，v，均有d(u) + d(v)≥n – 1，则G中存在哈密顿通路。
证明 （我也没搞懂，日后再更）一个图是哈密顿图首先要是连通图。设G不连通，则G至少有2个连通分量G1、G2。设u、v分别是G1、G2的一个顶点，因为G是简单图，所以（一个点的度最大的情况是该点与图中其它点都有边直连），矛盾，所以G是连通图。
下面证明G中存在哈密顿通路。设Γ = v1v2…vl为G中的一条极大路径，即Γ的起点与终点都不与Γ外的顶点相邻，l≤n。
（1）若l = n，则Γ就是G中的哈密顿通路，定理成立。
（2）若l < n，则G存在Γ外的顶点，要证明G中存在过Γ上所有顶点的圈：
【a】若v1与vl相邻，则Γ∪(v1, vl)就是这个圈。
【b】若v1与vl不相邻，设v1与Γ上的vi1 = v2，vi2，……，vik相邻（k≥2，否则d(v1) + d(vl)≤1 + l – 2≤l – 1 < n – 1，与已知条件d(u) + d(v)≥n – 1不符。因为l < n，所以d(vl)≤l – 2，因为vl至少与1个点不相邻）。vl至少与vi2，vi3，……，vik相邻的顶点之一相邻（否则d(v1) + d(vl)≤k + l – 2 – (k – 1) = l – 1 < n – 1，与已知条件d(u) + d(v)≥n – 1不符）。设vl与相邻（2≤r≤k），于是回路经过Γ上的所有顶点。
【c】下面证明存在比Γ更长的路径。因为l < n，所以C外还有顶点。由G是连通的，得存在vi+1∈V(G) – V©与C上的某个顶点vt相邻，当t < ir – 1时，删除边(vt-1, vt)得路径比Γ的长度大1。当t≥ir – 1时，可类似构造出比Γ的长度大1的路径Γ’。重复【a】到【c】，在有限步内一定可以得到G的一条哈密顿通路。
推论 设G为不少于3阶的无向简单图，若对于G中任意两个不相邻顶点u，v均有d(u) + d(v)≥n，则G中存在哈密顿回路。
证明 由上述定理，G中存在一条哈密顿通路Γ = v1v2…vn。若v1与vn相邻，就将这条边e添加到Γ中，就得到G的一条哈密顿回路Γ∪e。若不相邻，可以仿照上述的证明方法证明存在过Γ上各个顶点的圈，此圈就是哈密顿回路。
4、设u、v为n阶无向简单图G的两个不相邻顶点，且d(u) + d(v)≥n，则G为哈密顿图，当且仅当G∪(u, v)是哈密顿图，其中(u, v)是添加的新边。
5、不低于2阶的竞赛图都有哈密顿通路。
回忆：若有向图D的基图（有向边全部改成无向边后的图）为n阶无向完全图，就称D为n阶竞赛图。
证明 设D为n阶竞赛图，对n归纳证明。
当n = 2时，D的基图是二阶完全图K2，结论成立。
设n = k时结论成立，那么n = k + 1时结论也要成立。设V(D) = {v1, v2, …, vk, vk+1}，记D1 = D – vk+1，易知D1为k阶竞赛图。由归纳假设，D1存在哈密顿通路Γ1 = v1’v2’…vk’。下面，需要证明vk+1可以加入Γ 1中。若存在vr’（1≤r≤k）使(vi’, vk+1)、(vk+1, vr’)∈E(D)，i = 1，2，……，r – 1。则可以得到哈密顿通路Γ = v1’v2’…vr-1’vk+1vr’…vk’。若不存在，则任意i = 1，2，……，k，均有(vi’, vk+1)∈E(D)，则可以得到哈密顿通路Γ = v1’v2’…vk’vk+1。