当前位置：文档之家 › 离散数学图论作业5哈密顿图

离散数学图论作业5哈密顿图

  • 格式：doc
  • 大小：79.50 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

应用离散数学图论欧拉图与哈密尔顿图题库试卷习题及答案

应用离散数学图论欧拉图与哈密尔顿图题库试卷习题及答案

§5.5 欧拉图与哈密尔顿图习题5.51．判断图5.31中哪些图是欧拉图那些图不是。

对不是欧拉图的至少要加多少条新边才能成为欧拉图？对是欧拉图的，用Fleury算法求出欧拉回路。

图5.31 习题1的图解：（a）是欧拉图。

如下图为顶点号和边的标记，则欧拉回路为（e1,e2,e6,e10,e12,e11,e7,e8,e9,e5,e4,e3）e645e106 e117 e12 8。

（b）不是欧拉图。

需要加4条新边才能成欧拉回路。

（c）是欧拉图。

如下图为顶点号和边的标记，则欧拉回路为（1，2，3，4，5，6，1，8，7，10，11，7，9，1）236 5 4（d）不是欧拉图。

需要加2条新边才能成欧拉回路。

2．画一个欧拉图，使它具有：（1）偶数个顶点，偶数条边。

（2）奇数个顶点，奇数条边。

（3）偶数个顶点，奇数条边。

（4）奇数个顶点，偶数条边。

解 四个图按顺序分别如下：3．在k （k ≥2）个长度大于或等于3的无公共点的环型图之间至少加多少条边才能使它们组成一个简单欧拉图。

解：环形图中每个点的度是2,要形成欧拉回路，就要使新图是一个连通图，并且每个点的度仍保度偶数，因此，要让新图是欧拉图，则至少要加k 条边。

4．证明：可以从连通图中任意一点出发，经过这个图中每条边恰好两次，回到出发点。

解 将每条边都增加一条平行边，则得到一个多重图，此多重图的每个顶点的度数都是偶数，所以存在欧拉闭迹。

在欧拉闭迹中，将经过平行边改成第二次经过原来的边，定理即得证。

5．完全图p K 是欧拉图吗？是哈密尔顿图吗？完全二部图n m K ,是欧拉图吗？是哈密尔顿图吗？解 （1）K p ⎩⎨⎧不是欧拉图是欧拉图 为偶数时当为奇数时当p p K p （p ≥3）为哈密尔顿图（（v 1，v 2，v 3，……，v p ）即是一个哈密尔顿回路）。

（2）因为K m,n 中顶点的度数要么为m ，要么为n ，所以K m,n ⎩⎨⎧不是欧拉图是欧拉图 为奇数时或当为偶数时和当n m n m因为K m,n 的顶点数为m+n ，而任意两点的度数之和为2m 或2n 或m+n 。

离散数学-图论-哈密顿图及其应用

离散数学-图论-哈密顿图及其应用

离散数学-图论-哈密顿图及其应⽤哈密顿图⼀、定义概念1.哈密顿通路设G=<V,E>为⼀图（⽆向图或有向图）.G中经过每个顶点⼀次且仅⼀次的通路称作哈密顿通路2.哈密顿回路G中经过每个顶点⼀次且仅⼀次的回路（通路基础上+回到起始点）称作哈密顿回路3.哈密顿图若G中存在哈密顿回路，则称它是哈密顿图4.定义详解：（1）存在哈密顿通路（回路）的图⼀定是连通图；（2）哈密顿通路是初级通路，哈密顿回路是初级回路；（3）若G中存在哈密顿回路，则它⼀定存在哈密顿通路，反之不真（看课本的话，是必要条件，⽽不是充分条件，故不可反推！）（4）只有哈密顿通路，⽆哈密顿回路的图不叫哈密顿图；即，哈密顿图是回路⼆、判定定理注意：⽬前还没有找到哈密顿图的简单的充要条件（1）设⽆向图G=<V,E>为哈密顿图，V1是V的任意真⼦集，则（注：n阶xx图指的是n个顶点，不要迷！）p(G-V1)<=|V1|其中，p(G-V1)为G中删除V1后的所得图的连通分⽀数⽬，|V1|为V1集合中包含的顶点个数。

【哈密顿图存在的必要条件】推论：有割点的图⼀定不是哈密顿图设v是图中的割点，则p(G-v)>=2,由上述定理知G不是哈密顿图（2）设G是n(n>=3)阶⽆向简单图，若对于G中的每⼀对不相邻的顶点u,v,均有d(u)+d(v)>=n-1则G中存在哈密顿通路。

⼜若d(u)+d(v)>=n则G中存在哈密顿回路，即G为哈密顿图。

【哈密顿图存在的充分条件，不是必要条件】其中d(u),d(v)分别代表顶点u,v的度数。

推论：设G是n(n>=3)阶⽆向简单图，若G的最⼩度>=n/2,则G是哈密顿图。

由推论知，对于完全图Kn,当n>=3时，是哈密顿图，完全⼆部图Kr,s当r==s>=2时是哈密顿图。

（3）在n(n>=2)阶有向图D=<V,E>中，如果略去所有有向边的⽅向，所得⽆向图中含⽣成⼦图Kn,则D中存在哈密顿通路。

离散数学结构第十五章欧拉图与哈密顿图

离散数学结构第十五章欧拉图与哈密顿图

第十五章欧拉图与哈密顿图15」欧拉图—、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义務定义15・1通过图（无向图或有向图）中所有边一次jl仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。

具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。

从定义不难看出，欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），类似地，欧拉回路是经过所有边的简单的生成回路。

在这里做个规定，即平凡图是欧拉图。

(1) ⑵图15.1在图15」所示各图中QiSSgs为（1冲的欧拉回路所以（1禺为欧拉图oCiGSGb 为（2）中的一条欧拉通路，但图中不存在欧拉回路（为什么？），所以（2 ）为半欧拉图。

（3 ）中既没有欧拉回路，也没有欧拉通路（为什么？），所以（3 ）不是欧拉图，也不是半欧拉图。

CI6C3C4为（4）图中的欧拉回路，所以（4）图为欧拉图。

（5 ） , （ 6 ）图中都既没有欧拉回路，也没有欧拉通路（为什么？）二、判别定理拓定理15・1无向图G是欧拉图当11仅当G是连通图，11 G中没有奇度顶点。

证若G是平凡图，结论显然成立，下面设G为非平凡图，设G是m条边的n阶无向图。

并设G的顶点集V ={v h v2,...,v n}.必要性。

因为G为欧拉图，所以G中存在欧拉回路，设C为G中任意一条欧拉回路，VVi,VjeV , v 都在C上，因而Vi,Vj连通，所以G为连通图。

又V Vi eV，"在C 上每出现一次获得2度，若岀现k次就获得2k度，即d(Vi)二2k ,所以G中无奇度顶点。

充分性，由于G为非平凡的连通图可知，G中边数m21.对m作归纳法。

(1) m=l时，由G的连通性及无奇度顶点可知，G只能是一个环，因而G为欧拉图。

(2) 设mwk(k21)时结论成立，要证明m二K+1时，结论也成立。

由G的连通性及无奇度顶点可知，&(G)、2•类似于例14.8 ,用扩大路径法可以证明G中存在长度大于或等于3的置，设C为G中一个圏，删除C上的全部边，得G的生成子图G,设G有s个连通分支G I,G‘2,...,G；,每个连通分支至多有k条边，且无奇度顶点，并且设G i与C*的公共顶点为, i=l,2，…,S ,由归纳假设可知，G I,G‘2，…,G；都是欧拉图,因而都存在欧拉回路Cl , i=l,2，…,s.最后将C还原(即将删除的边重新加上)，并从C上的某顶*点*开始行遍,每遇到% ,就行遍G'i中的欧拉回路Cl , i二1,2,…,s ,最后回到v r,得回路V「... ... ... "... "... b ... b ...Vr，此回路经过G中每条边一次且仅一次并行遍G中所有顶点，因而它是G中的欧拉回路(演示这条欧拉回路)，故G为欧拉图。

离散数学图论作业5-哈密顿图

离散数学图论作业5-哈密顿图

离散数学图论作业5-哈密顿图
Problem1
下方所示各图是否拥有哈密顿通路？若有哈密顿通路，则求出这样一条通路。

若没有哈密顿通路，则论证为什么这样的通路不存在。

(1)(2)(3)
Problem2
对哪些m和n值来说，完全二部图K m,n具有哈密顿回路？
Problem3
证明：每当n是正整数时，就存在n阶格雷码，或者等价地证明：n>1的n维立方体(n-cube)Q，总是具有哈密顿回路。

[提示：用数学归纳法，证明如何从n−1阶格雷码产生n阶格雷码。

]
证明：下图所示的彼得森图没有哈密顿回路，但删除任意顶点v和所有与v关联的边，所获得的子图都有哈密顿回路。

Problem5
若简单图G满足V(G)≥3且δ(G)≥V(G)−1
，证明或反驳：
2
a)G一定存在哈密顿回路。

b)G一定存在哈密顿通路。

Problem6
底图是完全图的有向图称为竞赛图，试证明：
a)竞赛图一定含有哈密顿通路。

b)竞赛图含有哈密顿回路的充分必要条件是强连通。

Problem7
考虑在15天安排15门课程的考试（每天考1门课），使得同一位老师所任的任意两门课程考试不排在接连的两天中，试证明如果没有老师担任多于8门课程，则符合上述要求的考试安排总是可能的。

考虑M×N的网格，以其中的方格作为点集，任意两个点之间有边当且仅当对应的两个方格相邻，构成图G。

a)当N是偶数且M>1时，给出一种哈密顿回路的构造方法。

b)当N和M都是大于1的奇数时，证明此时G没有哈密顿回路。

哈密顿图

哈密顿图

procedure dfs(i:integer); Begin var j,k:integer; init; begin fillchar(visited,sizeof(visited),0); if (n=m)and(a[b[1],b[m]]=1) then print; found:=0; for j:=1 to n do m:=1; if (a[i,j]=1) and (visited[j]=0) then b[1]:=1; begin visited[1]:=1; visited[j]:=1; dfs(1); m:=m+1; if found=0 then writeln('no road'); b[m]:=j; end. dfs(j); visited[j]:=0; m:=m-1; end; end;
2 、安排座位
个客人围着一个桌子吃饭，每一个人都至少认识其他的2个客人。 n 个客人围着一个桌子吃饭 ， 每一个人都至少认识其他的 2 个客人 。 请设计程 序求得n个人的一种坐法，使得每个人都认识他左右的客人。 序求得n个人的一种坐法，使得每个人都认识他左右的客人。 输入: 输入: 第一行:n（吃饭人的个数）。 第一行:n（吃饭人的个数）。 :n 以下n 以下n行：第i行的第一个数k表示第i个人认识的人数，后面k个数依次为i认识的 行的第一个数k表示第i个人认识的人数，后面k个数依次为i 人的编号。 人的编号。 输出：所有座法，要求第一个人为1号作为起点，按顺时针输出其它人的编号。 输出：所有座法，要求第一个人为1号作为起点，按顺时针输出其它人的编号。
Begin init; found:=0; for i:= 1 to n do begin fillchar(visited,sizeof(visited),0); m:=1; b[1]:=i; visited[i]:=1; dfs(i); end; if found=0 then writeln('no road'); end.

离散数学--第十五章 欧拉图和哈密顿图

离散数学--第十五章 欧拉图和哈密顿图
13
实例
在上图中， (1),(2) 是哈密顿图; (3)是半哈密顿图; (4)既不是哈密顿图，也不是半哈密顿图，为什么？
14
无向哈密顿图的一个必要条件
定理15.6 设无向图G=<V,E>是哈密顿图，对于任意V1V且 V1，均有 p(GV1) |V1|
证 设C为G中一条哈密顿回路。
当V1顶点在C上均不相邻时， p(CV1)达到最大值|V1|，
求图中1所示带权图k29主要内容欧拉通路欧拉回路欧拉图半欧拉图及其判别法哈密顿通路哈密顿回路哈密顿图半哈密顿图带权图货郎担问题基本要求深刻理解欧拉图半欧拉图的定义及判别定理深刻理解哈密顿图半哈密顿图的定义
第十五章 欧拉图与哈密顿图
主要内容
➢ 欧拉图 ➢ 哈密顿图 ➢ 带权图与货郎担问题
1
15.1 欧拉图
大时，计算量惊人地大
27
例6 求图中(1) 所示带权图K4中最短哈密顿回路.
(1)
(2)
解 C1= a b c d a,
W(C1)=10
C2= a b d c a,
W(C2)=11
C3= a c b d a,
W(C3)=9
可见C3
(见图中(2))
是最短的，其权为9. 28
第十五章 习题课
主要内容 欧拉通路、欧拉回路、欧拉图、半欧拉图及其判别法 哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图 带权图、货郎担问题
点.
由vi 的任意性，结论为真. 充分性 对边数m做归纳法（第二数学归纳法）. (1) m=1时，G为一个环，则G为欧拉图. (2) 设mk（k1）时结论为真，m=k+1时如下证明：
5
从以上证明不难看出：欧拉图是若干个边不重的圈之 并，见示意图3.

哈密顿图

哈密顿图

定义4.3.1 经过图G 的每个顶点恰一次的路称为G 的Hamilton 路，简称为H 路。

经过图G 的每个顶点恰一次的圈称为G 的Hamilton 圈，简称为H 圈。

具有Hamilton 圈的图称为Hamilton 图，简称为H 图。

Hamilton 图的研究起源于一种十二面体上的游戏。

1857 年，爱尔兰著名数学家William Rowan Hamilton 爵士（他也是第一个给出复数的代数描述的人）制作了一种玩具，它是一个木制的正十二面体，在正十二面体的每个顶点上有一个木栓，并标有世界著名城市的名字。

游戏者用一条细线从一个顶点出发，设法沿着十二面体的棱找出一条路，通过每个城市恰好一次，最后回到出发点。

这个游戏当时称为Icosian 游戏，也称为周游世界游戏。

将正十二面体从一个面剖开并铺展到平面上得到的图形如下图所示，称为十二面体图。

周游世界游戏用图论术语来说就是判断十二面体图是否Hamilton 图，并设法找出其Hamilton 圈。

其中一条Hamilton 圈如图中粗边所示。

十二面体图是H 图判断一个图是否Hamilton 图与判断一个图是否Euler 图似乎很相似，然而二者却有本质的不同。

目前为止尚没有找到判别一个图是否是Hamilton 图的有效充要条件。

这是图论和计算机科学中未解决的重要难题之一。

本节给出一些经典的充分条件和必要条件。

一、必要条件定理4.3.1 设G 是二部图，若G 是H 图，则G 必有偶数个顶点。

证明：设G = (X, Y ) ，由于G 的边全在X 和Y 之间，因此如果G 有Hamilton 圈C，则G的所有顶点全在C 上，且必定是X 的点和Y 的点交替在C 上出现，因此G 必有偶数个顶点。

证毕。

这个定理给出了一个二部图不是Hamilton 图的简单判断条件：如果一个二部图有奇数个顶点，则它必定不是Hamilton 图。

例如，下列Herschel 图是二部图，但有奇数个顶点，故不是H 图。

图论05-哈密尔顿图

图论05-哈密尔顿图

A F
B
A
C
F
B C
E
D
E
D
竞赛图
底图为K4的竞赛图： A
B
C
以上每个图可以看作4个选手参加的循环赛的一种结果
竞赛图与有向哈密尔顿通路
底图是完全图的有向图称为竞赛图。 利用归纳法可以证明竞赛图含有向哈密尔顿通路。
循环赛该如何排名次
A F
E
B
按照在一条有向Hamilton通路 (一定存在)上的顺序排名：
Ore定理的证明
Ore定理（1960） 设G是无向简单图，|G|=n3，若
对G中任意不相邻的顶点u和v, d(u)+d(v)n （*）
则G有哈密尔顿回图。
证明.反证法, 若存在满足（*）的图G，但是G没有Hamilton回 路. 不妨假设G是边极大的非Hamilton图，且满足（*）。若G不是 边极大的非Hamilton图，则可以不断地向G增加若干条边,把G 变成边极大的非Hamilton图G’，G’依然满足（*），因为对 vV(G), dG(v)dG’(v)。
设G是无向简单图, |G|=n2, 若G中任意不相邻的顶点对
u,v均满足：d(u)+d(v)n-1，则G是连通图。
假设G不连通，则至少含2个连通分支，设为G1, G2。取xVG1, yVG2, 则：d(x)+d(y)(n1-1)+(n2-1)n-2 (其中ni是Gi的顶பைடு நூலகம்个数)， 矛盾。
有限图G是Hamilton图充分必要其闭合图C(G)是 Hamilton图.
闭合图(举例)
a
b
f
c e
d
判定定理的盲区
从“常识”出发个案处理

离散数学课件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 )

离散-Hamilton图

离散-Hamilton图
9
定理4.4.2
➢若G=(P, L)是有限图， 3， /2，
则G是Hamilton图。其中，表示图G
中点数，即 =|P(G)|，表示G中点的
最小度。
= 5;
= 32
10
证明：
➢ 反证法，若G不是Hamilton图，则在G中一 定能找到其度</2的顶点。显然，G不是完 全图 。
若G不是极大非Hamilton图，则可以不断地 向G增加若干条边，把G变成极大非 Hamilton图G0，若G是极大非Hamilton图, 则 令 G0=G， 显 然 ， 对 任 意 点 vP(G)， dG(v)dG0(v)，那么，如果在G0中能找到度 </2的点，在G中也一定能找到。
30
例：补图
G
H
31
➢ 用Km表示由m个点组成的完全图。将如 下三个图：
Kmc
Km
Kn-2m
1 m n/2
➢从左到右顺序连接起来构成的连接图记 为Cm,n。
32
例：
K2c
K2
K3
下图给出的是 C2,7的具体图
K2c
K2
K3
33
引理3
➢若1 m n/2 ，则图Cm,n 是非 Hamilton图。
6
例：
➢将图中点A，B，
C的集合记为S，
于是，删去S，
剩下的图的分支
数是4，而|S|=3。
由定理4.4.1知， 该图不是
A
Hamilton图。
C B
7
例：
8
§4.4.2 Hamilton图的充分条件
➢定义 设图G是非Hamilton图，若在G 中增加任意一条边uv，G∪{uv}就变成 Hamilton图，则G称为极大非 Hamilton图。

《离散数学》 第八章 欧拉图与哈密尔顿图

《离散数学》 第八章 欧拉图与哈密尔顿图

1 10 1
8.1 欧拉图
8.1.4 欧拉图的应用
欧拉图的应用，计算机旋转鼓轮的设计原理。
现在构造一个有向图G，G有8个顶点，每个顶点分别表示 000～111的一个二进制数。设α i∈{0，1}，从顶点α 1α 2α 3 引出两条有向边，其终点分别为α 2α 30和α 2α 31，这两条边 分别为α 1α 2α 30以及α 1α 2α 31，按照此种方法，对于八个 顶点的有向图共有16条边，在这个图的任意一条通路中，其 邻接的边必是α iα jα kα t和α jα kα tα s的形式，即前一条有 向边的后3位与后一条有向边的前3位相同。因为图中的16条 边被记成不同的4位二进制信息，即对应于图中的一条欧拉 回路。
推论 无向连通图中顶点与间存在欧拉通路，当且仅当中 与的度数为奇数，而其他顶点的度数为偶数。
8.1 欧拉图
8.1.2 欧拉图的判定
b
a
d
c
图8.1-2
v1
v2
v1
v3
v4
v5
v6
v2
(a)
图8.1-3
v4
v3 (b)
8.1 欧拉图
8.1.2 欧拉图的判定
定理8.1.3 有向图是欧拉图，当且仅当是强连通的，且 中每个顶点的入度都等于出度。
8.2 哈密尔顿图
8.2.1 哈密尔顿图
在图8.2-2中，（a）、（b）中存在哈密尔顿回路，是哈密 尔顿图，（c）中存在哈密尔顿通路，但不存在哈密尔顿回 路，是半哈密尔顿图，（d）中既无哈密尔顿回路，也无哈 密尔顿通路，不是哈密尔顿图。
（ a）
（ b）
（ c）
（ d）
8.2 哈密尔顿图
8.2.2 哈密尔顿图的判定

哈斯图

哈斯图
2013年7月14日 Deren Chen, Zhejiang Univ. 21
Relations关系
[定义]：哈森图/Ｈａｓｓｅ图 设≤是Ａ上的一个半序关系，如果ａ≤ｂ， 则将ａ画在ｂ下面，且不ｃ，使ａ≤ｃ，ｃ≤ ｂ，则ａ，ｂ间用直线连接。并符合简化的 关系图的绘制，称这样得到关系图为Ｈａｓ ｓｅ图。
Relations关系
例４： Ｎ的一个分划为：若１０ i-1≢ａ＜１０ i ， 则ａ∈Ａi，对应的等价关系 Ｒ＝｛（ａ，ｂ）｜ａ与ｂ有相同位数， ａ，ｂ∈Ｎ｝相同位的数归为一类，此Ｒ把 Ｎ分划为可列个等价类。
2013年7月14日
Deren Chen, Zhejiang Univ.
13
Relations关系
Relations关系
[定义]链：
设（Ａ，≤ Ｒ ）是半序集，ＢＡ，若（Ｂ， ≤ Ｒ ）是全序集，则称Ｂ为（Ａ，≤ Ｒ ）中的链/ Ｃｈａｉｎ。
当Ｂ是有限集时，Ｂ的基数｜Ｂ｜称 为链长/length of chain。
2013年7月14日
Deren Chen, Zhejiang Univ.
29
Relations关系
小
（1）等价关系的概念 （2）等价关系与划分
结
2013年7月14日
Deren Chen, Zhejiang Univ.
14
Relations关系
进一步的思考
1、等价关系的本质----集合中元素的相关性
2、作为二元关系的运算问题
2013年7月14日
Deren Chen, Zhejiang Univ.
6
Relations关系
注： 等价关系Ｒ把Ａ的元素分为若干类，各类之间没有 公共元素。确定的Ｒ是对集合Ａ进行的一个划分。

离散数学图论5

离散数学图论5
30
格雷码(gray code)
为了确定圆盘停止旋转后的位置, 把圆盘划分成2n个扇区, 每 个扇区分配一个n位0-1串. 要用某种电子装置读取扇区的赋值. 当圆盘停止旋转后, 如果电子装置处于一个扇区的内部, 它将 能够正确的读出这个扇区的赋值, 如果电子装置恰好处于两个 扇区的边界上, 就可能出问题. 如何赋值, 才能将可能出现的误差减少到最小?
第6章 特殊的图
6.1 二部图 6.2 欧拉图 6.3 哈密顿图 6.4 平面图
1
6.1 二部图
二部图 完全二部图 匹配
极大匹配,最大匹配,完美匹配,完备匹配
Hall定理
2
二部图
定义 设无向图 G=<V,E>, 若能将V 划分成V1 和 V2 (V1V2=V, V1V2=), 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二部图, 记为<V1,V2,E>, 称V1和V2为互补顶点子集. 又若G 是简单图, 且V1中每个顶点都与V2中每个顶点相邻, 则称G为完全二部图, 记为Kr,s, 其中r=|V1|, s=|V2|.
M1
M2
6
二部图中的匹配
定义 设G=<V1,V2,E>为二部图, |V1||V2|, M是G中最 大匹配, 若V1中顶点全是M饱和点, 则称M为G中V1 到V2的完备匹配. 当|V1|=|V2|时, 完备匹配变成完美 匹配.
例
完备,不完美
不完备
完美
7
一个应用实例
例 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、 香港去开会. 已知a只想去上海，b只想去广州，c, d, e都 表示想去广州或香港. 问该课题组在满足个人要求的条件 下，如何派遣？

离散数学中的欧拉图与哈密顿图

离散数学中的欧拉图与哈密顿图

欧拉图和哈密顿图是离散数学中的两个重要的图论概念。

它们分别研究了图中的路径问题，对于解决一些实际问题具有很大的应用价值。

欧拉图是指一个无向图中存在一条路径，经过图中的每条边一次且仅一次，这条路径称为欧拉路径。

如果这个路径的起点和终点重合，则称为欧拉回路。

而对于有向图，存在一条路径，使得经过每一个有向边恰好一次，称为欧拉有向路径，如果该路径起点和终点相同，则称为欧拉有向回路。

1722年，瑞士数学家欧拉首次提出了这个概念，并证明了一系列欧拉图的性质。

欧拉图的性质是其路径的存在性。

既然有了这个概念，那如何判断一个图是不是欧拉图就是一个非常重要的问题。

根据欧拉图的定义，我们可以发现，图中的每个节点的度数都应该是偶数，否则该节点无法成为路径中的中间节点。

因此，一个图是欧拉图的充分必要条件是该图中每个节点的度数都是偶数。

哈密顿图是指一个图中存在一条路径，经过图中的每个顶点一次且仅一次，这条路径称为哈密顿路径。

如果这个路径的起点和终点重合，则称为哈密顿回路。

哈密顿图的概念由19世纪初英国数学家哈密顿引入，其研究对象是关于骑士巡游问题。

与欧拉图不同的是，哈密顿路径并没有一个十分明显的判定条件。

唯一已知的是某些图是哈密顿图，比如完全图和圈图。

至于一般的图是否存在哈密顿路径，目前尚无通用的判定方法。

这也是全世界许多数学家所面临的一个著名且具有挑战性的开放问题，被命名为“哈密顿路径问题”。

欧拉图和哈密顿图在实际问题中具有广泛的应用。

欧拉图的应用包括电子电路和网络的设计，路线规划等。

而哈密顿图的应用更多地涉及路径的优化问题，比如旅行商问题。

在实际应用中，我们常常需要通过对欧拉图和哈密顿图的研究，来寻找最优解或者设计最佳路径。

总的来说，离散数学中的欧拉图和哈密顿图是两个重要的图论概念，它们研究的是图中的路径问题。

欧拉图的判定条件相对明确，而哈密顿图的判定则是一个尚未完全解答的开放问题。

这两个概念在实际中具有广泛的应用，对于解决一些路径优化问题具有重要的参考价值。

离散数学教学图论【共58张PPT】

离散数学教学图论【共58张PPT】

一 、图的基本概念
• 邻接和关联 • 无向图和有向图 • 零图和平凡图 • 简单图 • 完全图（无向完全图和有向完全图） • 有环图
一 、图的基本概念
• 有限图和无限图 设图G为< V，E，Ψ>
（l）当V和E为有限集时，称G为有限图，否则称G为无限图。 （2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足
二、生成树
1、生成树定义：
若无向图的一个生成子图T是树，则称T 为G的生 成树，T中的边称为树枝，E（G）-E（T）称为树T 的补，其中的每一边称为树T 的弦。
在任何图中，结点v的度（degree）d(v)是v所关联边的数目。
第三节 生成树、最短路径和关键路径 由结点a和它所有的后代导的子图，称为T的子树.
∴ T连通且具有m=n-1的图
{e5,e4,e8} ， {e7，e6，e5，e2，e4} 第四节 欧拉图和哈密顿图
第四节 特殊图（欧拉图和哈密顿图等）
第五节 树、二叉树和哈夫曼树
离散数学教学图论
（优选 欧拉图和哈密顿图
(3)2=>3 ∴W(T)≤W(T1) ∴W(ei+1)≥W(f) 二. 哈密顿图的由来—周游世界问题：
第二节 图的矩阵表示 第四节 欧拉图和哈密顿图
证明：若G中一个边割集和一生成 树无公共边，则表示该边割集所分离的结点不在生成树中，这导致与生成树的定义矛盾。 哈密顿图的由来—周游世界问题： c)对新图向下旋转45度。 ei之后将取f而不是ei+1
为该顶点的度,列之和一定为2. • 有向图的关联矩阵 ----- 以节点数为行,边数为列.节点与边无关系,为0,有关系,则起点为1,
终点为-1;列之和一定为0,每行绝对值之和等于该节点的度数;其 中1的个数为该节点的出度,-1的个数为对应节点的入度;所有元 素的和为0,1的个数等于-1的个数,都等于边数m.

哈密顿图

哈密顿图

13.2 哈密顿图13.2.1哈密顿图的定义与欧拉回路类似的是哈密顿回路问题。

它是1859年哈密顿首先提出的一个关于12面体的数学游戏：能否在下图中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题也被称为周游世界问题。

定义13.3给定图G，若存在一条路经过图中的每一个结点恰好一次，这条路称作哈密顿（Hamilton）路。

若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作哈密顿回路。

具有哈密顿回路的图称为哈密顿图。

具有哈密顿路但不具有哈密顿回路的图称为半哈密顿图。

(a)(b)(c)（a）中存在哈密顿路，不存在哈密顿回路，所以（a）是半哈密顿图，（b）中存在哈密顿回路，（b）是哈密顿图，（c）不是哈密顿图。

13.2.2哈密顿图的判定定理13.3（哈密顿回路的必要条件）若图G=<V, E>具有哈密顿回路，则对于结点集V的每一个非空子集S均有W(G−S)≤|S|成立。

其中W(G−S)是G−S中连通分支数。

定理13.4（奥尔定理，哈密顿路的充分条件）设G是具有n个结点的简单无向图，如果G中每一对不相邻顶点的度数之和大于等于n−1，则在G中存在一条哈密顿路。

例13.2某地有5个风景点。

若每个景点均有两条道路与其他景点相通，问是否可经过每个景点恰好一次而游完这5处？解将景点作为结点，道路作为边，则得到一个有5个结点的无向图。

由题意，对每个结点vi，有。

则对任意两点均有可知此图一定有一条哈密顿路，本题有解。

小结（1）深刻理解哈密顿图及半哈密顿图的定义；（2）分清哈密顿图的必要条件和充分条件，会用哈密顿图的必要条件证明某些图不是哈密顿图。

关于哈密顿图的思维形式注记图如图所示。

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

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

(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
计算机科学学院 刘芳
分析
▪ 穷举法 ▪ 近似算法 ▪ …………

5汉密尔顿图

5汉密尔顿图
v0 vi
vi+1
vn
21
无向汉密尔顿图的充分条件

推论2: 设G是n(3)阶无向简单图,若对G 中任意顶点u有 d(u)n/2 则G是汉密尔顿图. 推论3:Kn(n>2)为汉密尔顿图

22
图的闭包C(G)

定义：给定简单图G=<V,E>，|V|=n， 将图G中度数之和至少为n的非邻接顶点 连接起来得到图G '，对G '重复上述步骤， 直到不再有这样的顶点对为止，所得到 的图称为G 的闭包，记作C(G) 。
2
马的周游路线(knight’s tour)

棋盘上马的周游路线(knight’s tour on a chessboard)
3
汉密尔顿图


1. 周游世界,汉密尔顿通(回)路,汉密尔顿 图 2. 判定汉密尔顿图的必要条件 3. 判定汉密尔顿图的充分条件 4. 旅行商问题
4
马的周游路线(knight’s tour)
每个顶点对应一门考试课程两个顶点之间有边当且仅当对应两课程由不同教师担任每个顶点的度数至少是3任两个顶点度数之和至少为6因此一定存在一条汉密尔顿通路
周游世界

Sir William Rowan Hamilton, 1859, Icosian game: 是否存在一条回路，使它含有图中的所有顶点 一次且仅一次？(初级回路)

v0
v0
vi vi+1
vk
vk
20
无向汉密尔顿图的充分条件


推论1: 设G是n(3)阶无向简单图,若对G 中任意不相邻顶点u与v有 d(u)+d(v)n 则G是汉密尔顿图. 证明: 由定理4知G连通且有汉密尔顿通 路=v0v1…vn. (1) 若(v0,vn)E,则得汉密 尔顿回路C=v0v1…vnv0. (2) 若(v0,vk)E, 则与定理4证明(2b)类似,也存在汉密尔顿 回路. # v0 vn
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

失散数学图论作业5 - 哈密顿图
Problem 1
下方所示各图能否拥有哈密顿通路？如有哈密顿通路，则求出这样一条通路。

若没有哈密顿通路，则论证为什
么这样的通路不存在。

(1)(2)(3)
Problem 2
对哪些 m 和 n 值来说，完整二部图K m,n拥有哈密顿回路？
Problem 3
证明：每当n 是正整数时，就存在n 阶格雷码，或许等价地证明：n > 1 的 n 维立方体(n-cube) Q，老是拥有哈密顿回路。

[提示：用数学概括法，证明怎样从n - 1 阶格雷码产生n 阶格雷码。

]
证明：下列图所示的彼得森图没有哈密顿回路，但删除随意极点v 和全部与v 关系的边，所获取的子图都有哈密顿回路。

Problem 5
若简单图 G 知足 V (G )≥ 3 且δ(G )≥V ( G) - 1
，证明或辩驳：2
a)G 必定存在哈密顿回路。

b)G 必定存在哈密顿通路。

Problem 6
底图是完整图的有向图称为比赛图，试证明：
a)比赛图必定含有哈密顿通路。

b)比赛图含有哈密顿回路的充分必需条件是强连通。

Problem 7
考虑在 15 天安排 15 门课程的考试（每日考 1 门课），使得同一位老师所任的随意两门课程考试不排在接连的两天中，试证明假如没有老师担当多于8 门课程，则切合上述要求的考试安排老是可能的。

考虑 M × N 的网格，以此中的方格作为点集，随意两个点之间有边当且仅当对应的两个方格相邻，组成图G。

a)当 N 是偶数且 M > 1 时，给出一种哈密顿回路的结构方法。

b) 当 N 和 M 都是大于 1 的奇数时，证明此时G 没有哈密顿回路。