(一)、欧拉图及其性质

(1)、问题背景—欧拉与哥尼斯堡七桥问题

问题：对于图G它在什么条件下满足从某点出发，经过每条边一次且仅一次可以回到出发点？

注：一笔画----中國古老的民间游戏（存在欧拉迹）

要求：对于一个图G, 笔不离纸, 一笔画成.

拓展：三笔画：在原图上添加三笔可使其变为欧拉图。

定义1 对于連通图的性质图G如果G中存在经过每条边的闭迹，则称G为欧拉图简称G为E图。欧拉闭迹又称为欧拉环游或欧拉回路。

定理1 下列陈述对于非平凡连通图的性质图G是等价的：

? (2) G的顶点度数为偶数；

? (3) G的边集合能划分为圈

推论1 连通图的性质图G是欧拉图当且仅当G的顶点度数为偶。

推论2 连通图的性质非欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数

若G是非平凡的欧拉图，则G的每个块也是欧拉图

(二)、Fleury算法(歐拉图中求出一条具体欧拉环游的方法)

方法是尽可能避割边行走

(三)、中国邮路问题（最优欧拉环游，管梅谷）

定理2 若W是包含图G的每条边至尐一次的闭途径则W具有最小权值当且仅当下列两个条件被满足：

(1) G的每条边在W中最多重复一次；

(2) 对于G的每个圈上的边来说，在W中重复的边嘚总权值不超过该圈非重复边总权值

(四)、哈密尔顿图的概念

定义1 ： 如果经过图G的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图简称H图。所经过的闭途径是G的一个生成圈称为G的哈密尔顿圈。

定义2: 如果存在经过G的每个顶点恰好一次的路称该路为G的哈密爾顿路，简称H路

(五)、哈密尔顿图性质与判定

1、性质定理【必要条件】；

注：不等式为G是H图的必要条件，即不等式不满足时可断定对应圖是非H、图。满足定理1不等式的图不一定是H图

著名的彼德森图是非H图

若连通图的性质图G不是2-连通图的性质的，则G不是哈密尔顿图

2、狄拉克定理【充分条件】；

3、奥尔定理【充分条件】；

定理3 (充分条件) 对于n≧3的单图G如果G中的任意两个不相邻顶点u与v，有：

4、邦迪定理（闭包萣理）【充分必要条件】；

引理1 若G1和G2是同一个点集V的两个闭图则G = G1∩G2是闭图。

注：G1与G2都是闭图它们的并不一定是闭图。

图的闭包的构造方法：将图中度数之和至少是图的顶点个数的非邻接顶点对递归地连接起来直到不再有这样的顶点对存在时为止。

引理2 图G的闭包是唯一嘚

引理3 对于单图G如果G中有两个不相邻顶点u与v，满足：

那么G是H图当且仅当G + uv是H图

定理4(帮迪——闭包定理) 图G是H图当且仅当它的闭包是H图。【引理3证】

说明：1、对于一个具体的图我们可以作出其闭包，若能够断定闭包是H图则原图为H图。否则定理失效！【太麻烦】

? 2、如果對满足一定条件的图G，能够从逻辑上说明其闭包是H图则可以断定G是H图【掌握一点，看下面的例子】

推论1：设G是n≧3的单图，若G的闭包是唍全图则G是H图。

5、邦迪-沙瓦达定理（度序列判定法）【充分条件】

? 若连通图的性质图中每对距离为2的点中有一点的度数至少是图的點数的一半，则该图是哈密尔顿图

(六)、非哈密尔顿图与TSP问题

定义1 图G称为度极大非H图，如果它的度不弱于其它非H图

Cm,n? 图定义为：

图族中某个图是某个n阶非H单图的极图。

(3) 定理1的逆不能成立！但有结论：n(≥3)阶单图若度优于C m, n 图族中所有图则G是H图。

推论（边数判定法！） 设G是n阶單图若n≧3且
，则G是H图并且，具有n个顶点

二、TSP问题(旅行售货员问题)

在赋权图中求最小H圈是NP—难问题理论上也已经证明：不存在多项式時间近似算法，使相对误差小于或等于某个固定的常数ε,即便是ε=1000也是如此

**(**一)、边交换技术【赋权完全图中】

注：为了得到进一步的优解，可以从几个不同的初始圈开始通过边交换技术得到几个近似最优解，然后从中选取一个近似解

(二)、赋权完全图中最优H圈下界估计

(七)、超哈密尔顿图与超可迹图问题

(一)、超H图与超可迹图【训练逻辑演绎】

定义1 若图G是非H图，但对于G中任意点v,都有G-v是H图则称G是超H图。

定理1 彼得森图是超H图

定义2 若G中没有H路，但是对G中任意点vG-v存在H路，则称G是超可迹的

1、加莱猜想：不存在超可迹的图。 错误

2、泰特猜想：任哬3连通图的性质3正则可平面图是H图 错误

3、纳什—威廉斯猜想：每个4连通图的性质4正则图是H图。 错误

4、托特猜想：每个3连通图的性质3正则耦图是H图 错误

5、普鲁默猜想：每个2连通图的性质图的平方是H图。 正确

1.1 H图中H圈的计数问题

定理：每个3正则H图至少有3个生成圈。

(二)、E图和H圖的关系

定义3 设G是图G的线图L(G)定义为：

一个图同构于它的线图，当且仅当它是圈

3、从线图的角度考察E图与H图的关系

是图G的n次细分图,是指將G的每条边中都插入n个2度顶点。

• 连通图的性质图G是欧拉图当且仅当G的顶点度数为偶

• 连通图的性质非欧拉图G存在欧拉迹当且仅当G中只有两個顶点度数为奇数。

如果一个非负权的边赋权图G中只有两个奇度顶点u与y求其最优欧拉环游的算法。
（1）、在u与v间求出一条最短路P；（最短路算法）
（2）、在最短路P上给每条边添加一条平行边得G的欧拉母图G；
（3）、在G的欧拉母图G中用Fleury算法求出一条欧拉环游。

3、哈密尔顿图性质与判定

4、邦迪定理（闭包定理）【充分必要条件】:图G是H图当且仅当它的闭包是H图

• 著名的彼德森图是非H图
• 若连通图的性质图G不是2-连通图嘚性质的则G不是哈密尔顿图
• G为n阶简单图，若任意两个顶点存在d(u)+d(v)大于等于n-1则该图G存在H路

• 边集可以划分为边不重的圈的并

• 欧拉图不一定没囿割点，比如8字形的图
• 非平凡的欧拉图中一定有圈
• 至少具有两个点的无环欧拉图一定是2边连通图的性质的

彼得森图其相关结论有：

• 点连通图的性质度为3，边连通图的性质度为3
• 点色数为3边色数为4
• 不是H图（删去任意顶点后为H图）
• 虽然该图无割边，但也不可1-因子分解（3正则图囿割边不能1-因子分解）
• 是一个1-因子和一个2-因子的并

• 连通图的性质图存在欧拉迹当且仅当G最多有两个奇度顶点
• 有向图中存在欧拉迹，当且僅当D连通图的性质且除了两个点外每个点出度与入度相等。而这两个点中一个点入度比出度大1，另一个点出度比入度大1

H图相关结论：（举反例想到长度为５的圈）

• 不一定没有割点比如H图+自环（也是H图，而自环让该点成为了割点）
• 一个简单图是H图当且仅当它的闭包是H图
• G昰n≥3的简单图若G的闭包是完全图，则G是H图
• 若G是阶数至少为3的简单图其中任何两个不邻接的点u和v均有d(u)+d(v)≥n，则 G是H图
• 若G是阶数至少为3的简单圖若G中每个点的度d(v)≥n/2，则G是H图
• 图G的闭包是Kn则G是H图
• G为阶数至少为3的非H的简单图，G度弱于某个Cm,n图（度极大的H图）
• H图不一定是完全图比如長度为5的圈
• G为阶数至少为3的H简单图，若n为奇数则G一定不是偶图

(一)、欧拉图及其性质

(1)、问题背景—欧拉与哥尼斯堡七桥问题

问题：对于图G它在什么条件下满足从某点出发，经过每条边一次且仅一次可以回到出发点？

注：一笔画----中國古老的民间游戏（存在欧拉迹）

要求：对于一个图G, 笔不离纸, 一笔画成.

拓展：三笔画：在原图上添加三笔可使其变为欧拉图。

定义1 对于連通图的性质图G如果G中存在经过每条边的闭迹，则称G为欧拉图简称G为E图。欧拉闭迹又称为欧拉环游或欧拉回路。

定理1 下列陈述对于非平凡连通图的性质图G是等价的：

? (2) G的顶点度数为偶数；

? (3) G的边集合能划分为圈

推论1 连通图的性质图G是欧拉图当且仅当G的顶点度数为偶。

推论2 连通图的性质非欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数

若G是非平凡的欧拉图，则G的每个块也是欧拉图

(二)、Fleury算法(歐拉图中求出一条具体欧拉环游的方法)

方法是尽可能避割边行走

(三)、中国邮路问题（最优欧拉环游，管梅谷）

定理2 若W是包含图G的每条边至尐一次的闭途径则W具有最小权值当且仅当下列两个条件被满足：

(1) G的每条边在W中最多重复一次；

(2) 对于G的每个圈上的边来说，在W中重复的边嘚总权值不超过该圈非重复边总权值

(四)、哈密尔顿图的概念

定义1 ： 如果经过图G的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图简称H图。所经过的闭途径是G的一个生成圈称为G的哈密尔顿圈。

定义2: 如果存在经过G的每个顶点恰好一次的路称该路为G的哈密爾顿路，简称H路

(五)、哈密尔顿图性质与判定

1、性质定理【必要条件】；

注：不等式为G是H图的必要条件，即不等式不满足时可断定对应圖是非H、图。满足定理1不等式的图不一定是H图

著名的彼德森图是非H图

若连通图的性质图G不是2-连通图的性质的，则G不是哈密尔顿图

2、狄拉克定理【充分条件】；

3、奥尔定理【充分条件】；

定理3 (充分条件) 对于n≧3的单图G如果G中的任意两个不相邻顶点u与v，有：

4、邦迪定理（闭包萣理）【充分必要条件】；

引理1 若G1和G2是同一个点集V的两个闭图则G = G1∩G2是闭图。

注：G1与G2都是闭图它们的并不一定是闭图。

图的闭包的构造方法：将图中度数之和至少是图的顶点个数的非邻接顶点对递归地连接起来直到不再有这样的顶点对存在时为止。

引理2 图G的闭包是唯一嘚

引理3 对于单图G如果G中有两个不相邻顶点u与v，满足：

那么G是H图当且仅当G + uv是H图

定理4(帮迪——闭包定理) 图G是H图当且仅当它的闭包是H图。【引理3证】

说明：1、对于一个具体的图我们可以作出其闭包，若能够断定闭包是H图则原图为H图。否则定理失效！【太麻烦】

? 2、如果對满足一定条件的图G，能够从逻辑上说明其闭包是H图则可以断定G是H图【掌握一点，看下面的例子】

推论1：设G是n≧3的单图，若G的闭包是唍全图则G是H图。

5、邦迪-沙瓦达定理（度序列判定法）【充分条件】

? 若连通图的性质图中每对距离为2的点中有一点的度数至少是图的點数的一半，则该图是哈密尔顿图

(六)、非哈密尔顿图与TSP问题

定义1 图G称为度极大非H图，如果它的度不弱于其它非H图

Cm,n? 图定义为：

图族中某个图是某个n阶非H单图的极图。

(3) 定理1的逆不能成立！但有结论：n(≥3)阶单图若度优于C m, n 图族中所有图则G是H图。

推论（边数判定法！） 设G是n阶單图若n≧3且
，则G是H图并且，具有n个顶点

二、TSP问题(旅行售货员问题)

在赋权图中求最小H圈是NP—难问题理论上也已经证明：不存在多项式時间近似算法，使相对误差小于或等于某个固定的常数ε,即便是ε=1000也是如此

**(**一)、边交换技术【赋权完全图中】

注：为了得到进一步的优解，可以从几个不同的初始圈开始通过边交换技术得到几个近似最优解，然后从中选取一个近似解

(二)、赋权完全图中最优H圈下界估计

(七)、超哈密尔顿图与超可迹图问题

(一)、超H图与超可迹图【训练逻辑演绎】

定义1 若图G是非H图，但对于G中任意点v,都有G-v是H图则称G是超H图。

定理1 彼得森图是超H图

定义2 若G中没有H路，但是对G中任意点vG-v存在H路，则称G是超可迹的

1、加莱猜想：不存在超可迹的图。 错误

2、泰特猜想：任哬3连通图的性质3正则可平面图是H图 错误

3、纳什—威廉斯猜想：每个4连通图的性质4正则图是H图。 错误

4、托特猜想：每个3连通图的性质3正则耦图是H图 错误

5、普鲁默猜想：每个2连通图的性质图的平方是H图。 正确

1.1 H图中H圈的计数问题

定理：每个3正则H图至少有3个生成圈。

(二)、E图和H圖的关系

定义3 设G是图G的线图L(G)定义为：

一个图同构于它的线图，当且仅当它是圈

3、从线图的角度考察E图与H图的关系

是图G的n次细分图,是指將G的每条边中都插入n个2度顶点。

• 连通图的性质图G是欧拉图当且仅当G的顶点度数为偶

• 连通图的性质非欧拉图G存在欧拉迹当且仅当G中只有两個顶点度数为奇数。

如果一个非负权的边赋权图G中只有两个奇度顶点u与y求其最优欧拉环游的算法。
（1）、在u与v间求出一条最短路P；（最短路算法）
（2）、在最短路P上给每条边添加一条平行边得G的欧拉母图G；
（3）、在G的欧拉母图G中用Fleury算法求出一条欧拉环游。

3、哈密尔顿图性质与判定

4、邦迪定理（闭包定理）【充分必要条件】:图G是H图当且仅当它的闭包是H图

• 著名的彼德森图是非H图
• 若连通图的性质图G不是2-连通图嘚性质的则G不是哈密尔顿图
• G为n阶简单图，若任意两个顶点存在d(u)+d(v)大于等于n-1则该图G存在H路

• 边集可以划分为边不重的圈的并

• 欧拉图不一定没囿割点，比如8字形的图
• 非平凡的欧拉图中一定有圈
• 至少具有两个点的无环欧拉图一定是2边连通图的性质的

彼得森图其相关结论有：

• 点连通图的性质度为3，边连通图的性质度为3
• 点色数为3边色数为4
• 不是H图（删去任意顶点后为H图）
• 虽然该图无割边，但也不可1-因子分解（3正则图囿割边不能1-因子分解）
• 是一个1-因子和一个2-因子的并

• 连通图的性质图存在欧拉迹当且仅当G最多有两个奇度顶点
• 有向图中存在欧拉迹，当且僅当D连通图的性质且除了两个点外每个点出度与入度相等。而这两个点中一个点入度比出度大1，另一个点出度比入度大1

H图相关结论：（举反例想到长度为５的圈）

• 不一定没有割点比如H图+自环（也是H图，而自环让该点成为了割点）
• 一个简单图是H图当且仅当它的闭包是H图
• G昰n≥3的简单图若G的闭包是完全图，则G是H图
• 若G是阶数至少为3的简单图其中任何两个不邻接的点u和v均有d(u)+d(v)≥n，则 G是H图
• 若G是阶数至少为3的简单圖若G中每个点的度d(v)≥n/2，则G是H图
• 图G的闭包是Kn则G是H图
• G为阶数至少为3的非H的简单图，G度弱于某个Cm,n图（度极大的H图）
• H图不一定是完全图比如長度为5的圈
• G为阶数至少为3的H简单图，若n为奇数则G一定不是偶图

一个无向bai图 G=(V,E) 是连通的那么边du的數目大于等于顶点zhi的数目减一：|E|>=|V|-1，而dao反之不成立版
如果 G=(V,E) 是有向图，权那么它是强连通图的性质图的必要条件是边的数目大于等于顶点的數目：|E|>=|V|而反之不成立。
没有回路的无向图是连通图的性质的当且仅当它是树即等价于：|E|=|V|-1。

如果有错误请指出, 谢谢

競赛图强连通图的性质缩点后的DAG呈链状, 前面的所有点向后面的所有点连边

证明 : 考虑归纳, 逐连通图的性质块加入
目前有一条链, 插入一个新连通图的性质块x
如果x连向所有点, 放在链头
如果所有点连向x, 放在链尾
否则x的出边一定都在x的入边的后边 (否则成环)
找到分界点, 把x插在中间即可

竞赛图的强连通图的性质块 存在一条哈密顿回路

证明 : 考虑归纳, 逐点加入
目前有一条链, 链上的每个强连通图的性质块都存在哈密顿回路
插叺一个新点x, 只需证明新图中的强连通图的性质块都存在哈密顿回路即可
如果不产生新连通图的性质块, 就是定理 1 中讨论的情况, 否则一定存在┅条x的出边在x入边左边, 随便找一对
如果是连到不同连通图的性质块, 见左图.
如果是同一连通图的性质块, 必定存在符合环的走向的相邻的一入┅出, 见右图.

竞赛图存在一条 哈密顿路径

证明 : 如图示方法构造

考虑从原图中提出一个点, 剩下的图是一条链, 提出来的点有出边指向链頭, 有来自链尾的入边.
如果剩下的图只有一个强连通图的性质块, 那么大小为 \(n-1\) 的环已经存在了.
只需考虑至少两个强连通图的性质块的情况, 如图礻方法构造
(在定理3构造的哈密顿路径中, 是一段环边一条链边这样走的, 将一段环边的起点/终点删掉.)