当前位置：文档之家 › 离散数学课件15欧拉图与哈密顿图

离散数学课件15欧拉图与哈密顿图

  • 格式：ppt
  • 大小：832.00 KB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

离散数学课件15.1欧拉图

离散数学课件15.1欧拉图
推论 无向图G为欧拉图(具有欧拉回路)当 且仅当G是连通的,且G中无奇度顶点.
推论的证明(充分性):Fleury算法
构造性证明 1.任取一个顶点 2.寻找没有走过的并且不是余图的 桥的关联边(除非别无选择),到达下 一个顶点. 3.重复2,直至无边可走.
例
1.是欧拉图； 2.不是欧拉图，但存在欧拉通路； 3.既不是欧拉图，也不存在欧拉通路。
只具欧拉通路,无欧拉回路的图不是 欧拉图.
(1)既无欧拉回路,也无欧拉通路. (2)中存在欧拉通路,但无欧拉回路. (3)中存在欧拉回路.
例
图a)存在一条欧拉通路：v3v1v2v3v4v1； 图 (b) 中 存 在 欧 拉 回 路 v1v2v3v4v1v3v1 ， 因 而 (b) 是欧拉图； 图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因 而(c)是欧拉图。
P326: 3., 4
课堂练习
课后作业: P323: 2 ,5
有向图的Euler图
定理: 一个有向图D具有欧拉通 路,当且仅当D是连通的,且除了 两个顶点外,其余顶点的入度均 等于出度.这两个特殊的顶点中, 一个顶点的入度比出度大⒈另 一个顶点的入度比出度小1.
推论: 一个有向图D是欧拉图(具有欧 拉回路),当且仅当D是连通的,且所有 顶点的入度等于出度.
例(蚂蚁比赛问题)
甲、乙两只蚂蚁分别位 于如下图中的结点a，b 处，并设图中的边长度 是相等的。甲、乙进行 比赛：从它们所在的结 点出发，走过图中的所 有边最后到达结点c处。 如果它们的速度相同， 问谁先到达目的地？
2.一笔画问题
有向图的Euler图
给定G是一个无孤立结点的有 向图，若存在一条单向通路 (回路)，经过图中每边一次且 仅仅一次，则称此单向通路 (回路)为该图的一条单向欧拉 通路(回路)。具有单向欧拉回 路的图称为欧拉图。

第15章 欧拉图与哈密顿图

第15章 欧拉图与哈密顿图

e5
v3
v2 e1 v1
e2
e3
e4
v4
e5
v3 e3 e4 v4
v2 v1 v5
e2 e3
e1 e5
v3 e4 v4 v6
v1
e6 v5 e7 e8 v6 e2 e3
e8 v5
e8 v6 v5 e2 v6
e7
G
v2 e1 v1 v5 v6 v3 e4 v4 v5 v2
G1
e2 v3 e4 v2 e1 v1 v5 e1
定理15.7
定理15.7 设G是n阶无向简单图，若对于G中任意不相邻的顶 点vi,vj，均有 d(vi)+d(vj)≥n-1 (15.1) 则G中存在哈密顿通路。 证明 首先证明G是连通图。 否则G至少有两个连通分支， 设G1,G2是阶数为n1,n2的两个连通分支， 设v1∈V(G1)，v2∈V(G2)，因为G是简单图，所以 dG(v1)+dG(v2)＝dG1(v1)+dG2(v2)≤n1-1+n2-1≤n-2 这与(15.1)矛盾，所以G必为连通图。
例15.3的说明
哈密顿通路是经过图中所有顶点的一条初级通路。 哈密顿回路是经过图中所有顶点的初级回路。 对于二部图还能得出下面结论： 一般情况下，设二部图G＝<V1,V2,E>，|V1|≤|V2|，且 |V1|≥2，|V2|≥2，由定理15.6及其推论可以得出下面结 论： (1) 若G是哈密顿图，则|V1|＝|V2|。 (2) 若G是半哈密顿图，则|V2|＝|V1|+1。 (3) 若|V2|≥|V1|+2，则G不是哈密顿图，也不是半哈密 顿图。
§15.2 哈密顿图
设图为G2，则G2＝<V1,V2,E>，其中 V1＝{a,g,h,i,c}，V2＝{b,e,f,j,k,d}， 易知，p(G2-V1)＝|V2|＝6>|V1|＝5， 由定理15.6可知，G2不是哈密顿图， 但G2是半哈密顿图。 baegjckhfid为G2中一条哈密顿通路。 设图为G3。G3＝<V1,V2,E>，其中 V1＝{a,c,g,h,e}，V2＝{b,d,i,j,f}， G3中存在哈密顿回路。 如 abcdgihjefa， 所以G3是哈密顿图。

欧拉图与哈密顿图

欧拉图与哈密顿图
哈密顿回路。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
➢ 定义8.21
图G称为可2-着色（2-chromatic），
如果可用两种颜色给G的所有顶点着色， 使每个顶点着一种颜色，而同一边的两端点 必须着不同颜色。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
✓ 定理8.16
设图G是可2-着色的。如果G是哈密顿 图，那么着两种颜色的顶点数目相等；如 果G有哈密顿通路，那么着两种颜色的顶点 数目之差至多为一。
✓定理8.14
设图G为具有n个顶点的简单无向图，如果G的 每一对顶点的度数之和都不小于n – 1 ，那么G中有 一条哈密顿通路；如果G的每一对顶点的度数之和 不小于n，且n≥3，那么G为一哈密顿图。
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
✓ 定理8.15
当n为不小于3的奇数时，
Kn上恰有 n 1 条互相均无任何公共边的 2
离散数学导论
.
欧拉图与哈密顿图 1.1欧拉图与欧拉路径
➢ 定义8.19
图G称为欧拉图（Euler graph），
如果图G上有一条经过G的所有顶点、所有
边的闭路径。图G称为欧拉路径（Euler
walk），如果图G上有一条经过G 所有顶点、所有边的路径。
.
欧拉图与哈密顿图 1.1欧拉图与欧拉路径
✓ 定理8.11
.
欧拉图与哈密顿图 1.2 哈密顿图及哈密顿通路
➢ 定义8.20
无向图G称为哈密顿图（Hamilton graph），
如果G上有一条经过所有顶点的回路
（也称这一回路为哈密顿回路）。称无向图有哈密顿 通路(非哈密顿图)，如果G上有一条经过所有顶点的

《离散数学》课件-第15章欧拉图与哈密顿图

《离散数学》课件-第15章欧拉图与哈密顿图

例如
彼得松图 彼得松图满足定理15.6，但不是哈密顿图。
例15.3 下图中三个图都是二部图，判断它们 哪些是哈密顿图，哪些是半哈密顿图？
G1
G2
G3
二部图与哈密顿图的关系
设二部图G=<V1，V2，E>，
|V2||V1|。若|V2||V1|+2，则
G即不是哈密顿图，又不是半哈
G1
密顿图
（1）G1=<V1，V2，E>， 互补顶点子集为V1={a,f},V2={b,c,d,e}。 则p(G1-V1)=|V2|=4，|V1|=2， p(G1-V1)>|V1|且p(G1-V1)>|V1|+1。 所以G1即不是哈密顿图，又不是半哈密顿图。
亚瑟王和他的骑士们
◼ 亚瑟王一次召见他的p个骑士，已知每一个 骑士在骑士中的仇人不超过p/2-1个。证明：能让 这些骑士围坐在圆桌旁，使每个人都不与他的仇 人相邻。
其它重要的定理
◼ 定理1 如果G是一个n（n3）阶简单图， 且n/2，则G是哈密顿图。
◼ 定理2 如果G是一个n（n3）阶完全图， 且n为奇数，则G是哈密顿图且图中有(n-1)/2个 边不相交的哈密顿回路。
穿过每一道门，通过所有房间？
15.2 哈密顿图
1859年，爱尔兰数学家威廉·哈密尔顿发明 了一个旅游世界的游戏。将一个正十二面体的 20个顶点分别标上世界上大城市的名字，要求 玩游戏的人从某城市出发沿12面体的棱，通过 每个城市恰一次，最后回到出发的那个城市。
哈密尔顿游戏是在左图中如何 找出一个包含全部顶点的圈。
点的回路称为欧拉回路 定义（欧拉图和半欧拉图）
具有欧拉回路的图称为欧拉图 具有欧拉通路无欧拉回路的图称为半欧拉图 规定平凡图是欧拉图

欧拉图和哈密尔顿图ppt课件

欧拉图和哈密尔顿图ppt课件
有欧拉通路
全部结点为偶结点， 有欧拉回路
有欧拉通路
。a
a、b、c、e
。a
全部结点为
b。 。c 都为奇结点， 。 。 。 无欧拉通路
b。
。c
d
e
f 与欧拉回路 。 。 。
偶结点， 有欧拉回路
d e f 有欧拉通路
ppt课件
8
例7-8 如图街道，是否存在一条投递线路使 邮递员从邮局a出发通过所有街到一次在回 到邮局a?
可达的：在图G中，结点u和结点v之间存在一
条路，则称结点u到结点v是可达的。
ppt课件
2
无向图的连通性
连通：在无向图G中，结点u和结点v之间存在一 条路，则称结点u与结点v是连通的。约定：任一 结点与自身总是连通的。 连通图：若图G中，任意两个结点均连通，则称G 是连通图，否则称非连通图。对非连通图可分成几
个无公共结点的连通分支。无向图中结点间的连通
关系是等价关系。 图是连通的判定法则：从图中任意一结点出发，
通过某些边一定能到达其它任意一结点，则称
图是连通的。
ppt课件
3
练习1：连通图的判定
指出下列各图是否连通
(1)
(2)
(3)
(4)
(5)
(6)
ppt课件 (7)
(8)
4
欧拉图
设G=<V，E>是连通无向图 欧拉通路：在图G中存在一条通路，经过图G 中每条边一次且仅一次。
第二节 图的连通性
通路和回路 无向图的连通性 有向图的连通性 欧拉图 哈密顿图
ppt课件
1
通路和回路 给定图G V , E
通路： G中前后相互关联的点边交替序列 w=v0e1v1e2…envn称为连接v0到vn的通路。 W中边的数目K称为通路W的长。

离散数学课件15欧拉图与哈密顿图

离散数学课件15欧拉图与哈密顿图

04
欧拉图与哈密顿图的应用 场景
欧拉图的应用场景
路径规划
欧拉图可以用于表示从一 个点到另一个点的路径， 常用于物流、交通和旅行 等领域。
网络流问题
欧拉图可以用于解决最大 流和最小割等问题，在网 络优化、资源分配和计划 制定等方面有广泛应用。
组合优化
欧拉图可以用于表示组合 优化问题，如旅行商问题、 排班问题等，是求解这些 问题的常用工具。
一个图存在哈密顿回路当且仅当其所有顶点的度都大于等于2 。
哈密顿图的性质
哈密顿图中的所有顶点的度都 大于等于2。
一个图存在哈密顿回路当且仅 当其所有顶点的度都大于等于2。回 路。
哈密顿图的构造方法
添加边法
在所有顶点的度都大于等于2的图 中，不断添加边，直到所有顶点的 度都大于等于2，最后得到的图就 是哈密顿图。
哈密顿图的应用场景
社交网络分析
哈密顿图可以用于表示社交网络 中的路径，分析人际关系和信息
传播路径。
生物信息学
哈密顿图可以用于表示基因组、蛋 白质组等生物信息数据，进行基因 序列比对、蛋白质相互作用分析等。
推荐系统
哈密顿图可以用于表示用户和物品 之间的关系，进行个性化推荐和智 能推荐。
欧拉图与哈密顿图在计算机科学中的应用
欧拉图的构造方法
欧拉图的构造方法1
总结词
通过添加一条边将所有顶点连接起来， 从而形成一个欧拉图。
详细描述了两种构造欧拉图的方法， 为实际应用中构造欧拉图提供了思路。
欧拉图的构造方法2
通过将两个欧拉图合并，并连接它们 的所有顶点，从而形成一个新的欧拉 图。
02
哈密顿图
哈密顿图的定义
哈密顿图（Hamiltonian Graph）是指一个图存在一个遍历其 所有边且每条边只遍历一次的路径，这个路径称为哈密顿路径， 如果该路径的起点和终点是同一点，则称这个路径为哈密顿回 路。

离散数学欧拉图与哈密尔顿图ppt课件

离散数学欧拉图与哈密尔顿图ppt课件

例5 设G是非平凡的欧拉图，且v ∈V(G)。证明：G 的每条具有起点v的迹都能扩展成G的欧拉环游当且仅当 G-v是森林。
证明：“必要性”
若不然，则G-v有圈C。 考虑G1=G-E(G)的含有顶点v的分支H。
由于G是非平凡欧拉图，所以G1的每个顶点度数为偶数， 从而，H是欧拉图。
12
1
0.5 n 0
15
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
16
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
17
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
18
1
0.5 n 0
如果邮路图本身是非欧拉图，那么为得到行走环游，必须重 复行走一些街道。于是问题转化为如何重复行走街道？
25
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
2、管梅谷的结论
定理2 若W是图G中一条包含所有边的闭途径，则W在 这样的闭途径中具有最短的长度当且仅当下列两个条件被 满足：
在vi与vi+k间连新边ei得图G*（1≦i≦k).则G*是欧拉图， 因此，由Fleury算法得欧拉环游C.
在C中删去ei （1≦i≦k).得k条边不重的迹Qi （1≦i≦k):
E(G) E(Q1) E(Q2 )
E(Qk )

欧拉图及哈密顿

欧拉图及哈密顿
哈密顿路径是指一条遍历图的所有顶 点的路径，这条路径的起点和终点是 同一点，但路径上的边可以重复。
哈密顿图的性质
哈密顿图具有连通性，即任意两 个顶点之间都存在一条路径。
哈密顿图的顶点数必须大于等于 3，因为至少需要3个顶点才能 形成一条遍历所有顶点的路径。
哈密顿图的边数必须为奇数，因 为只有奇数条边才能形成一条闭
欧拉图及哈密顿
• 欧拉图 • 哈密顿图 • 欧拉图与哈密顿图的应用 • 欧拉回路与哈密顿回路 • 欧拉路径与哈密顿路径
目录
01
欧拉图
欧拉图的定义
总结词
欧拉图是指一个图中存在一条路径，这条路径可以遍历图中的每条边且每条边 只遍历一次。
详细描述
欧拉图是由数学家欧拉提出的一种特殊的图，它满足特定的连通性质。在欧拉 图中，存在一条路径，这条路径从图的一个顶点出发，经过每条边一次且仅一 次，最后回到起始顶点。
互作用网络的研究。
04
欧拉回路与哈密顿回路
欧拉回路的概念与性质
概念
欧拉回路是指一个图形中，从一点出 发，沿着一条路径，可以回到起始点 的路径。
性质
欧拉回路必须是连续的，不能中断， 也不能重复经过同一条边。此外，欧 拉回路必须是闭合的，起始点和终点 必须是同一点。
哈密顿回路的概念与性质
概念
哈密顿回路是指一个图形中，存在一 条路径，该路径经过了图中的每一条 边且每条边只经过一次。
随机构造法
通过随机选择边和顶点，不断扩展图，直到满足哈密顿图的条件。这种方法需要大量的计 算和随机性，但可以用于构造大规模的哈密顿图。
03
欧拉图与哈密顿图的应用
欧拉图在计算机科学中的应用
算法设计
欧拉图理论是算法设计的重要基础，特别是在图算法和动态规划 中，用于解决诸如最短路径、最小生成树等问题。

离散数学15 欧拉图与哈密顿图

离散数学15 欧拉图与哈密顿图
穿过每一道门，通过所有房间？
15.2 哈密顿图
1859年，爱尔兰数学家威廉·哈密尔顿发明 了一个旅游世界的游戏。将一个正十二面体的 20个顶点分别标上世界上大城市的名字，要求 玩游戏的人从某城市出发沿12面体的棱，通过 每个城市恰一次，最后回到出发的那个城市。
哈密尔顿游戏是在左图中如何 找出一个包含全部顶点的圈。
定义（哈密顿通路和哈密顿回路） 经过图（有向图或无向图）每个顶点一次
且仅一次的通路称为哈密顿通路。 经过图每个结点一次且仅一次的回路（初
级回路）称为哈密顿回路。 定义（哈密顿图和半哈密顿图）
存在哈密顿回路的图称为哈密顿图。 存在哈密顿通路但不存在哈密顿回路的图 称为半哈密顿图。 平凡图是哈密顿图。
由两判定定理，立即可知 （4）为欧拉图， （5）、（6）即不是欧拉图，也不是半欧拉图。
例15.2（P296） v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2
◼ Fleury算法
◼ （1）任取v0V(G)，令P0=v0。 ◼ （2）设Pi=v0e1v1e2…..eivi已经行遍，则按下面
判断所示两图是否为欧拉图、半欧拉图？
无向欧拉图与无向半欧拉图的判断方法
定理15.1（无向欧拉图的判定）无向图G是欧拉图当 且仅当G是连通图，且G中没有奇度顶点。
定理15.2（无向半欧拉图的判定）无向图G是半欧拉 图当且仅当G是连通图，且G中恰有两个奇度顶点。
（1）
（2）
（3）
有向欧拉图与有向半欧拉图的判断方法
（1）
（2）
（3）
（4）
（5）
（6）
（1）（2）（3）（4）为哈密顿图 （5）为半哈密顿图 （6）既不是哈密顿图，又不是半哈密顿图。

欧拉图和哈密顿图

欧拉图和哈密顿图

例如，由定理可知，下图 (a)图为欧拉图，本图 既v成圈8 可圈画v6之v以在1并(看vc2)(成v中为3 圈v)清。4 vv晰1将5v起v2(6av见v)87分v，v1解8，将v成1v与42若个v圈3干圈vv42个画vv24边在，v6不(vb4v)8重v中5v2的v)之6，圈v并也4，的(可两v并6看个v7 不是(a)图特有性质，任何欧拉图都有这个性质。
尽管讨论哈密顿通路和哈密顿回路在形式上与欧
拉通路和欧拉回路非常相似，但遗憾的是到目前为止， 仍然没有找到一个合适的条件来作为判断哈密顿通路 或哈密顿回路存在的充要条件。不过，可以给出哈密 顿通路和哈密顿回路存在的充分条件或必要条件。
定理9.2.1设无向图G=<V, 的任意非空子集，则
E>是哈密顿图，V1是V
下面给出一些哈密顿图的充分条件。
定理9.2.2设G=<V, E>是具有n个节点的简单无向图，若
对任意的u, v∈V均有
deg(v) +deg(u) ≥n－1
则G中存在哈密顿通路。
容易看出，定理9.2.2中的条件对图中是否存在哈密顿路 是充分而不必要的。
如图9.2.6所示的六边形G，虽然任意两个节点度数之和 等于4<6-1(n=6)，但G中却显然有哈密顿路（实际上G是哈密 顿图）。
只要数一下图中节点的度数即可。
❖ 9.1.4 欧拉图的应用 一笔画问题 所谓“一笔画问题”就是画一个图形，笔不离纸，每条 边只画一次而不许重复地画完该图。“一笔画问题”本质上 就是一个无向图是否存在欧拉通路（回路）的问题。如果该 图为欧拉图，则能够一笔画完该图，并且笔又回到出发点； 如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不 到出发点；如果该图中不存在欧拉通路，则不能一笔画完该 图。

欧拉图与哈密顿

欧拉图与哈密顿
哈密顿图
通过一系列的节点，将所有节点 两两连接起来，且每条边只使用 一次。
性质的异同比较
欧拉图 哈密顿图
应用领域的ቤተ መጻሕፍቲ ባይዱ较
欧拉图
在计算机科学、运筹学、交通运输等 领域有广泛应用。
哈密顿图
在计算机科学、电子工程、通信网络 等领域有广泛应用。
05
欧拉图与哈密顿图的未来研
究展望
欧拉图的研究展望
欧拉路径与欧拉回路
通过模拟生物进化过程的遗传 算法来寻找哈密顿路径，适用 于大规模的图。
元胞自动机法
通过模拟元胞自动机的演化过 程来寻找哈密顿路径，适用于
具有特定结构的图。
03
欧拉图与哈密顿图的应用
欧拉图在计算机科学中的应用
算法设计
01
欧拉图在计算机科学中常被用于算法设计，如最短路径算法、
最小生成树算法等。
数据结构
欧拉图与哈密顿图在其他领域的应用
经济学
欧拉图和哈密顿图在经济 学中被用于描述市场供需 关系和生产网络。
社会学
欧拉图和哈密顿图在社会 学中被用于研究社会网络 和人际关系。
交通工程
欧拉图和哈密顿图在交通 工程中用于描述交通流和 路网结构。
04
欧拉图与哈密顿图的比较
构造方法的比较
欧拉图
通过一系列的边和节点，将起点 和终点连接起来，且每条边只使 用一次。
欧拉图的扩展研究
深入研究欧拉路径和欧拉回路的性质 和构造方法，探索其在图论、组合数 学和计算机科学等领域的应用。
将欧拉图的研究扩展到其他领域，如 社交网络分析、生物信息学和交通网 络规划等。
欧拉图的算法优化
针对欧拉图的算法进行优化，提高算 法的效率和稳定性，以解决大规模图 数据的计算问题。

大学离散数学欧拉图和哈密尔顿图

大学离散数学欧拉图和哈密尔顿图

(a)
(b)
推论1:哈密尔顿图无割点.
2020/9/28
24
计算机科学学院 刘芳
15.2.3 Hamilton图的判定方法
例3：
▪ 证明下述各图不是哈密顿图。
2020/9/28
25
计算机科学学院 刘芳
15.2.3 Hamilton图的判定方法
推论2：
▪ 对二部图G＝＜ V1,V2,E＞
若| V1 |≠| V2 |，则一定不是H图。 证明：
2020/9/28
14
计算机科学学院 刘芳
15.1.4 中国邮路问题
例如：
2020/9/28
15
计算机科学学院 刘芳
15.1.4 中国邮路问题
判断条件
▪ 定理：
▪ 设L是图G的包含所有边的回路，则L具有最小长 度的充分必要条件是： ▪ 每条边最多重复一次； ▪ G的每个回路上，所有重复边的长度之和，不 超过该回路长度的一半。
2020/9/28
16
计算机科学学院 刘芳
15.2 Hamilton 图
15.2.1 问题引入 15.2.2 Hamilton图的定义 15.2.3 Hamilton图的判定方法 15.2.4 应用举例
2020/9/28
17
计算机科学学院 刘芳
15.2.1 问题引入
周游世界问题(W.Hamilton, 1859年)
▪ 可以用结点表示城市，城市间的交通路线用边表示，而 城市间的交通线路距离可用附加于边的权表示。
▪ 这样，上述问题可以归结为寻找一条权的总和为最短的 哈密尔顿回路的问题。
2020/9/28
30
计算机科学学院 刘芳
分析
▪ 穷举法 ▪ 近似算法 ▪ …………

15欧拉图与哈密顿图

15欧拉图与哈密顿图
问题转化为在图中找一条哈密顿回路. ABDFGECA即可.
哈密顿图的判定 定理1(必要条件): 设无向图G=<V, E>是哈密顿 图, V1是V的任意非空子集, 则p(G-V1)≤V1. 推论: 设无向图G=<V, E>是半哈密顿图, V1是V 的任意非空子集, 则p(G-V1)≤V1+1.
在Peterson图中, 虽然对任意顶 点集V1, 都满足p(G-V1)|V1|,但 它不是哈密顿图.
基本思想：能不走桥就不走桥
15.2 哈密顿图 定义1. 经过无向(有向)图中所有顶点恰好一次 的路(圈)称为哈密顿路(圈). 定义2. 具有哈密顿圈的图称为哈密顿图. 定义3. 具有哈密顿路但不具有哈密顿圈的图 称为半哈密顿图. 例1. 判断下列图形是否哈密顿图或半哈密顿图.
半哈密顿图 哈密顿图
都不是
例4. 判断下列有向图是否欧拉图或半欧拉图.
都不是 半欧拉图
欧拉图
一笔画问题:从某点出发,不间断地画完整个图. 即在图中找出欧拉通路（回路）.
Fleury算法: (1) 任取v0∊V(G), (2) 设Pi=v0e1v1e2eivi,
若E(G)-{e1,e2,ei}中没有与vi关联的边, 则计 算停止; 否则在vi关联的边中优先选择非桥的边 添加. (3) 令i=i+1, 返回(2).
定理2(充分条件): 设G＝<V, E>是无向简单图. 若对任意两个不相邻顶点u,vV, 均有 d(u)+d(v)|V|-1, 则G中存在哈密顿路； 若对任意两个不相邻顶点u,vV, 均有 d(u)+d(v)|V|, 则G是哈密顿图.
推论: n阶无向简单图G中, n>2, (G)n/2, 则G是
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
证明 若G是平凡图，结论显然成立。
下面设G为非平凡图，设G是m条边的n阶无 向图，
并设G的顶点集V＝{v1,v2,…,vn}。 必要性。因为G为欧拉图，所以G中存在欧 拉回路，
设C为G中任意一条欧拉回路，vi,vj∈V， v2i0,2v0/7j/都23 在C上，
定理15.1的证明
充分性。由于G为非平凡的连通图可知，G中边数 m≥1。
2020/7/23
半欧拉图的判定定理
定理15.2 无向图G是半欧拉图当且仅当G是连通的 ，且G中恰有两个奇度顶点。
证明 充分性。设G的两个奇度顶点分别为u0和v0， 对G加新边（u0,v0），得G ＝G∪(u0,v0)， 则G 是连通且无奇度顶点的图， 由定理15.1可知，G 为欧拉图， 因而存在欧拉回路C ，而C＝C -(u0,v0)为G中一 条欧拉通路， 所以G为半欧拉图。
并2行从020/7遍/C23 上G 的i中某的顶欧点拉vr回开路始C行遍i，，i＝每1遇,2,到…v,s*j，i，最就后
半欧拉图的判定定理
定理15.2 无向图G是半欧拉图当且仅当G是连通的 ，且G中恰有两个奇度顶点。
证明 必要性。设G是m条边的n阶无向图，因为G为 半欧拉图， 因而G中存在欧拉通路(但不存在欧拉回路)， 设Г＝vi0ej1vi1…vim-1ejmvim为G中一条欧拉通路， vi0≠vim。 v∈V(G)，若v不在Г的端点出现，显然d(v)为偶 数， 若v在端点出现过，则d(v)为奇数，
欧拉对物理力学、天文学、弹道学、航海学、建筑学、音 乐都有研究！有许多公式、定理、解法、函数、方程、常数等 是以欧拉名字命名的。欧拉写的数学教材在当时一直被当作标 准教程。19世纪伟大的数学家高斯曾说过“研究欧拉的著作永 远是了解数学的好方法”。欧拉还是数学符号发明者，他创设 的许多数学符号，例如π，i，e，sin，cos，tg，Σ，f (x)等等， 至今202沿0/7/2用3 。
哈密顿工作勤奋，思想活跃．发表的论文一般都很简洁，别人不易读懂， 但手稿却很详细，因而很多成果都由后人整理而得．仅在三一学院图书馆中 的哈密顿手稿，就有250本笔记及大量学术通信和未发表论文．爱尔兰国家图 书馆还有一部分手稿．
他的研究工作涉及不少领域，成果最大的是光学、力学和四元数．他研究的 光学是几何光学，具有数学性质；力学则是列出动力学方程及求解；因此哈 密顿主要是数学家．但在科学史中影响最大的却是他对力学的贡献．哈密顿 量是现代物理最重要的量，当我们得到哈密顿量，就意味着得到了全部。
2020/7/23
有向欧拉图的判定定理
定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的 入度都等于出度。
定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且D中 恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出 度比入度大1，而其余顶点的入度都等于出度。(举例)
本章内容
15.1 欧拉图 15.2 哈密顿图 15.3 带权图与货郎担问题
基本要求 作业
2020/7/23
15.1 欧拉图
• 历史背景－－哥尼斯堡七桥问题
欧拉图是一笔画出的边不重复的5.1 通过图（无向图或有向图）中所有边 一次且仅一次行遍图中所有顶点的通路称为 欧拉通路，通过图中所有边一次并且仅一次 行遍所有顶点的回路称为欧拉回路。具有欧 拉回路的图称为欧拉图，具有欧拉通路而无 欧拉回路的图称为半欧拉图。
设C为G中一个圈，删除C上的全部边，得G的 生成子图G ，
设G 有s个连通分支G 1,G 2,…,G s， 每个连通分支至多有k条边，且无奇度顶点，
并且设G i与C的公共顶点为v*ji，i＝1,2,…,s，
由归纳假设可知，G ，
1,G
2,…,G
s都是欧拉图
因而都存在欧拉回路C i，i＝1,2,…,s。 最后将C还原（即将删除的边重新加上），
2020/7/23
数学家欧拉
欧拉，瑞士数学家，欧拉是科学 史上最多产的一位杰出的数学家，他从 19岁开始发表论文，直到76岁，他一生 共写下了886本书籍和论文，其中在世 时发表了700多篇论文。彼得堡科学院 为了整理他的著作，整整用了47年。在 他双目失明后的17年间，也没有停止对 数学的研究，口述了好几本书和400余 篇的论文。
哈密顿
1805年8月4日生于爱尔兰都柏林；1865年9月2日卒于都柏 林．力学、数学、光学．哈密顿的父亲阿其巴德(Archibald Rowan Hamilton)为都柏林市的一个初级律师．哈密顿自幼 聪明，被称为神童．他三岁能读英语，会算术；五岁能译拉 丁语、希腊语和希伯来语，并能背诵荷马史诗；九岁便熟悉 了波斯语，阿拉伯语和印地语．14岁时，因在都柏林欢迎波 斯大使宴会上用波斯语与大使交谈而出尽风头．
2020/7/23
匈牙利数学家厄多斯
保罗‧厄多斯(1913-2019)是一位匈牙利的数学 家。
其父母都是匈牙利的高中数学教师。 1983年以色列政府颁给十万美元“沃尔夫奖金
”（WolfPrize）就是由他和华裔美籍的陈省 身教授平分。 厄多斯是当代发表最多数学论文的数学家，也 是全世界和各种各样不同国籍的数学家合作 发表论文最多的人。他发表了近1000多篇的 论文，平均一年要写和回答1500多封有关于 数20学20/7/2问3 题的信。他可以和任何大学的数学家
对m作归纳法。 (1)m＝1时，由G的连通性及无奇度顶点可知，
G只能是一个环，因而G为欧拉图。 (2)设m≤k(k≥1)时结论成立，要证明m＝k+1时，结
论也成立。
由G的连通性及无奇度顶点可知，δ(G)≥2。 无论G是否为简单图，都可以用扩大路径法证 明G中必含圈。
2020/7/23
定理15.1的证明
说明 欧拉通路是图中经过所有边的简单的生成 通路(经过所有顶点的通路称为生成通路)。 欧拉回路是经过所有边的简单的生成回路。
2020/7/23
举例
欧拉图
半欧拉图
无欧拉通路
欧拉图
2020/7/23
无欧拉通路
无欧拉通路
无向欧拉图的判定定理
定理15.1 无向图G是欧拉图当且仅当G是连通图 ，且G中没有奇度顶点。

相关主题