欧拉回路及哈密顿回路

(3)
(4)
(5)
(6)
(7)
欧拉图
设G=<V，E>是连通无向图 欧拉通路：在图G中存在一条通路，经过图G 中每条边一次且仅一次。 欧拉回路：在图G中存在一条回路，经过图 G中每条边一次且仅一次。（能一笔画） 欧拉图：具有欧拉回路的图。
欧拉图的判定定理
定理7-4 无向图G=<V，E>具有欧拉回路，即是 欧拉图的充分必要条件是这个图是连通的，并且 图G中所有结点的度数都是偶数，即都与偶数条 边相连。 定理7-5 无向图G=<V，E>具有欧拉通路的充分 必要条件是图G是连通的，并且图G中恰有两个度 数是奇数的结点或者没有度数是奇数的结点。
v1
e6
e1
v5
e5
e7 e4
v2
e2
v4
e3
v3
通路和回路 给定图G V , E
通路： G中前后相互关联的点边交替序列 w=v0e1v1e2…envn称为连接v0到vn的通路。 W中边的数目K称为通路W的长。 回路：在点边序列v0e1v1e2…envn中，当 v0=vn时称此通路为回路。
图1
图2
哈密尔顿图
设G=<V，E>是连通无向图 图G中存在一条经过图中的每个结点一次且仅
一次的通（回）路，称此通路为哈密顿通（回）路
哈密顿图：具有哈密尔顿回路的图。
目前还没有找到连通无向图具有哈密顿通（回）
路的充分必要条件。
?
课堂思考题：
学习了欧拉图、哈密尔顿图，请总 结他们的区别。
哈密尔顿回路与欧拉回路的区别
连通
连通、一笔
案例3
周游世界问题
1856年,英国数学家哈 密尔顿设计了一个周游世界的 游戏，他在一个正十二面体的 二十个顶点上标上二十个著名 城市的名字，要求游戏者从一 个城市出发，经过每一个城市 一次且仅一次，然后回到出发 点。

证明（略）。
定理4. 5 设G是具有n个结点的简单图，如果G中每一对结点度数之和大 于等于n，则在G中存在一条汉密尔顿回路。 证明（略）。
（3）充要条件
定义4. 4 设给定图G=<V，E>有n个结点，若将图G中度数之和至少是n的 非邻接结点连接起来得图G’，对图G’重复上述步骤，直到不再有这样的结 点对存在为止，所得到的图，称为原图G的闭包，记作C(G)。 定理4. 6 当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。 证明:略。
证明: 设C是G的一条汉密尔顿回路，则对于V的任何一个非空子集S在C中 删去S中任一结点a1，则C－a1是连通的非回路，若再删去S中另一结点a2， 则W(C- a1- a2)≤ 2，由归纳法可得： W(C-S)≤ |S| 同时C-S是G-S的一个生成子图（包含G的每个结点的子图），因而 W(G-S)≤ W（C-S） 所以 W(G-S)≤ |S|。 证毕。
证明：
推论 无向图G具有一条欧拉回路，当且仅当G是连通的，并 且所有结点度数全为偶数。
定理4. 1 证明
必要性 设G具有欧拉路，即有点边序列v0e1v1e2…eiviei+1…ekvk，其中
结点可能重复出现，但边不重复，因为欧拉路经过图G的所有结点， 故图G必是连通的。 对任意一个不是端点的结点vi，在欧拉路中每当vi出现一次，必 关联两边，故vi虽可重复出现，但deg(vi)必是偶数。对于端点，若 v0=vk，则d(v0)为偶数，即G中无奇数度结点；若端点v0与vk不同， 则d(v0)为奇数，d(vk)为奇数，G中就有两个奇数结点。 充分性 若图G连通,有零个或两个奇数结点,我们构造一条欧拉路如下：
二、汉密尔顿图
1、正十二面体问题 2、汉密尔顿图的定义 3、汉密尔顿图的判别条件

2016/12/6
IntroductionToCS--Xiaofeng Gao
10
有向连通图的欧拉回路
【推论】若有向连通图G中各节点的正负度 相等,则G中存在有向欧拉回路.
证明方法类似之前定理，由G是有穷图且每 个节点正负度相等可以断定从G的任一节点 v0出发一定存在G的一条简单回路C。若 C=E(G)，则得证。否则在G中删去C的各 边，找到新的简单回路C1，并添加至C中。 重复该步骤直至C成roductionToCS--Xiaofeng Gao
12
欧拉道路(欧拉迹)
【推论】若无向连通图G中只有2个度为奇数的顶 点。则G中存在欧拉道路。 【证明】设vi和vj是两个奇点，做G’=G+(vi,vj)。 则G’中各顶点的度都是偶数。由之前定理知，G’ 有欧拉回路，它包含(vi,vj)这条边。删去此边，即 可得到一条从vi到vj的简单道路，它恰好经过了G 的所有边，即是一条欧拉道路。
2016/12/6
IntroductionToCS--Xiaofeng Gao
7
证明(2)
充分性 ：由于G是有穷图，因此可断定从 G的任一节点v0出发一定存在G的一条简单 回路C。这是因为各节点的度都是偶数，所 以这条简单回路不可能停留在v0以外的某个 节点，而不能再向前伸延以构成闭通道C。
如果E=C, 则C就是欧拉回路，充分性得证。 否则在G中删去C的各边，得到G1=G―C。
2016/12/6
IntroductionToCS--Xiaofeng Gao
5
证明(3)
G1可能是非连通图，每个顶点的度保持为 偶数。这时，G1中一定存在某个度非零的 节点vi，同时也是C中顶点。否则C的顶点 与G1的顶点之间无边相连，与G是连通图矛 盾。同理，从vi出发，G1中所在的连通分量 内存在一条简单回路C1。C ∪ C1仍然是G 的一条简单回路，但它包括的边数比C多。 继续构造，最终有C’=C ∪ C1 ∪… ∪ Ck是 一条欧拉回路。

完全图知识点总结一、完全图的基本概念完全图是图论中的一个重要概念，它是一种特殊的图，具有很多独特的性质和特点。

完全图由n个顶点组成，其中任意两个顶点之间都有一条边相连。

完全图通常用Kn来表示，其中n代表顶点的个数。

完全图是一种特殊的简单图，因为任意两个顶点之间都有边，所以在完全图中不存在孤立的顶点或者度为0的顶点。

二、完全图的性质1. 完全图的边数在完全图中，任意两个顶点之间都有边相连，因此完全图的边数可以通过组合数学的知识计算得到。

对于n个顶点的完全图Kn，它的边数可以表示为C(n, 2)，即n个顶点中任取两个顶点相连，共有C(n, 2)条边。

2. 完全图的度完全图中每个顶点的度都是相同的，为n-1。

这是因为在完全图中，任意两个顶点之间都有边相连，所以每个顶点都与其他所有的顶点相邻，因此它的度为n-1。

3. 完全图的邻接矩阵和度矩阵完全图的邻接矩阵是一个n×n的矩阵，其中第i行第j列的元素表示第i个顶点和第j个顶点之间是否有边相连。

在完全图中，邻接矩阵是一个对称矩阵，对角线元素为0，非对角线元素为1。

完全图的度矩阵是一个n×n的矩阵，其中对角线元素为每个顶点的度，非对角线元素为0。

4. 完全图的生成对于完全图Kn，可以使用不同的方法进行生成。

一种方法是从n个顶点开始，逐个添加边直到所有的顶点之间都有边相连。

另一种方法是从n个顶点开始，对于每一对顶点，都添加一条边相连。

5. 完全图的应用完全图在实际生活中有很多应用，例如通信网络中的数据传输、交通规划中的道路建设、社交网络中的人际关系等。

在这些应用中，完全图可以帮助分析网络的拓扑结构、寻找最短路径、评估网络的稳定性等。

三、完全图的相关问题1. 完全图的最大团和最大独立集在完全图中，由于任意两个顶点都相连，因此最大团的大小为n，即完全图本身就是一个最大团。

最大独立集的大小为1，即每个顶点都是一个独立集。

2. 完全图的哈密顿回路和欧拉回路在完全图中，哈密顿回路是指通过所有顶点恰好一次的回路，而欧拉回路是指通过所有边恰好一次的回路。