Email:fws365@scu.edu.cn 2017年3月21日星期二 离散  数学 计算机学院 冯伟森 Email:fws365@scu.edu.cn 2017年3月21日星期二.

Slides:



Advertisements
Similar presentations
质数和合数 2 的因数( ) 6 的因数( ) 10 的因数 ( ) 12 的因数 ( ) 14 的因数 ( ) 11 的因数 ( ) 4 的因数( ) 9 的因数( ) 8 的因数( ) 7 的因数( ) 1 、 2 、 3 、 4 、 6 、 12 1 、 11 1 、 2 、 5 、 10.
Advertisements

全微分 教学目的:全微分的有关概念和意义 教学重点:全微分的计算和应用 教学难点:全微分应用于近似计算.
《解析几何》 -Chapter 3 §7 空间两直线的相关位置.
第十五章 欧拉图与哈密顿图 主要内容 欧拉图 哈密顿图 带权图与货郎担问题.
第三章 函数逼近 — 最佳平方逼近.
7-4欧拉图和汉密尔顿图 要求: 1、理解欧拉图、汉密尔顿图的定义。 2、掌握欧拉图的判定方法。 3、会判断一些图不是汉密尔顿图。
常用逻辑用语复习 知识网络 常用逻辑用语 命题及其关系 简单的逻辑联结词 全称量词与存在量词 四种命题 充分条件与必要条件 量词 全称量词 存在量词 含有一个量词的否定 或 且 非或 并集 交集 补集 运算.
1.1.3四种命题的相互关系 高二数学 选修2-1 第一章 常用逻辑用语.
常用逻辑用语复习课 李娟.
第一章 行列式 第五节 Cramer定理 设含有n 个未知量的n个方程构成的线性方程组为 (Ⅰ) 由未知数的系数组成的n阶行列式
第五节 微积分基本公式 、变速直线运动中位置函数与速度 函数的联系 二、积分上限函数及其导数 三、牛顿—莱布尼茨公式.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
定积分习题课.
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
余角、补角.
七 年 级 数 学 第二学期 (苏 科 版) 复习 三角形.
探索三角形相似的条件(2).
强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
元素替换法 ——行列式按行(列)展开(推论)
计算机数学基础 主讲老师: 邓辉文.
本节内容 平行线的性质 4.3.
28.1 锐角三角函数(2) ——余弦、正切.
使用矩阵表示 最小生成树算法.
平行四边形的性质 灵寿县第二初级中学 栗 彦.
无向树和根树.
第 五 章 图 论 (第二部分) 1. 通路 2. 图的连通性.
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
实数与向量的积.
线段的有关计算.
第四章 四边形性质探索 第五节 梯形(第二课时)
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
⑴当∠MBN绕点B旋转到AE=CF时(如图1),比较AE+CF与EF的大小关系,并证明你的结论。
4.2 证明⑶.
3.3 垂径定理 第2课时 垂径定理的逆定理.
复习.
第十章 双线性型 Bilinear Form 厦门大学数学科学学院 网址: gdjpkc.xmu.edu.cn
正切函数的图象和性质 周期函数定义: 一般地,对于函数 (x),如果存在一个非零常数T,使得当x取定义域内的每一个值时,都有
定理21.9(可满足性定理)设A是P(Y)的协调子集,则存在P(Y)的解释域U和项解释,使得赋值函数v(A){1}。
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§8.3 不变因子 一、行列式因子 二、不变因子.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
1.2 子集、补集、全集习题课.
辅助线巧添加 八年级数学专项特训: ——倍长中线法.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
树和图 tree and graph 蔡亚星.
4) 若A可逆,则 也可逆, 证明: 所以.
第4课时 绝对值.
第七、八次实验要求.
2.2矩阵的代数运算.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
2.2直接证明(一) 分析法 综合法.
平行四边形的性质 鄢陵县彭店一中 赵二歌.
高中数学必修 平面向量的基本定理.
§2 方阵的特征值与特征向量.
主讲教师 欧阳丹彤 吉林大学计算机科学与技术学院
定义5 把矩阵 A 的行换成同序数的列得到的矩阵,
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
欧拉图与汉密尔顿图.
3.2 平面向量基本定理.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
第三部分 图论 本部分主要内容 图的基本概念 树 欧拉图与哈密顿图 二部图与匹配 平面图 着色.
离散数学─图论 南京大学计算机科学与技术系
§4.5 最大公因式的矩阵求法( Ⅱ ).
离散数学─归纳与递归 南京大学计算机科学与技术系
最小生成树 最优二叉树.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
第三章 图形的平移与旋转.
1.2.2 充要条件 高二数学 选修 1-1 第一章 常用逻辑用语.
Presentation transcript:

Email:fws365@scu.edu.cn 2017年3月21日星期二 离散  数学 计算机学院 冯伟森 Email:fws365@scu.edu.cn 2017年3月21日星期二

主要内容 哈密尔顿图及其应用 哈密尔顿道路(圈 )的定义 连通图G是哈密尔顿图的必要条件 连通图G是哈密尔顿图的充分条件 哈密尔顿图的应用(推销商问题) 2017/3/21 计算机学院

哈密尔顿图 周游世界问题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  1857(59)年爱尔兰数学家W.R.Hamilton在给他朋友的一封信中,首先谈到关于十二面体的一个数学游戏:将右图中的每个结点看成一个城市,联结两个结点的边看成是交通线,他的问题就是能不能找到一条旅行路线,使得沿着交通线经过每个城市恰好一次,再回到原来的出发地? 他把这个问题称为周游世界问题。 2017/3/21 计算机学院

哈密尔顿道路是经过图中所有结点的道路中长度最短的通路; 哈密尔顿回路是经过图中所有结点的回路中长度最短的回路。 定义13.2 设G是一个连通图,若G中存在一条包含全部结点的基本道路,则称这条道路为G的哈密尔顿道路;若G中存在一个包含全部结点的圈,则称这个圈为G的哈密尔顿圈;含有哈密尔顿圈的图称为哈密尔顿图。 规定平凡图为哈密尔顿图。 哈密尔顿道路是经过图中所有结点的道路中长度最短的通路; 哈密尔顿回路是经过图中所有结点的回路中长度最短的回路。 2017/3/21 计算机学院

例13-2.1 既存在哈密尔顿道路,又存在哈密尔顿圈,即为哈密尔顿图。 既不存在哈密尔顿道路,也不存在哈密尔顿圈。 (b) a c (a) (c) (d) 既存在哈密尔顿道路,又存在哈密尔顿圈,即为哈密尔顿图。 既不存在哈密尔顿道路,也不存在哈密尔顿圈。 既存在哈密尔顿道路,又存在哈密尔顿圈,即为哈密尔顿图。 存在哈密尔顿道路,但不存在哈密尔顿圈。 2017/3/21 计算机学院

定理13.3 此定理表明哈密尔顿 有较好的连通性 设无向连通图G=<V,E>是哈密尔顿图,S是V的任意非空真子集,则 (G-S)≤|S| 其中(G-S)是从G中删除S后所得到图的连通分支数。 证明:设C是G的一个哈密尔顿圈,则对 S(≠)V,有 (C-S)≤|S| ∵ C-S是G-S的一个生成子图 ∴ (G-S)≤(C-S)≤|S| 为什么? 2017/3/21 计算机学院

注意 定理13.3给出的是哈密尔顿图的必要条件,而不是充分条件。下图所示的彼得森图,对V的任意非空子集V1,均满足(G-V1)≤|V1|,但它不是哈密尔顿图。 定理13.3在应用中它本身用处不大,但它的逆否命题却非常有用。我们经常利用定理13.3的逆否命题来判断某些图不是哈密尔顿图,即:若存在V的某个非空子集V1使得(G-V1)>|V1|,则G不是哈密尔顿图。例如在右图中取V1={a,c},则(G-V1)=4>|V1|=2,因而该图不是哈密尔顿图。 c a 2017/3/21 计算机学院

定理13.4 设G=<V,E>是具有n个结点的简单图。如果对任意两个结点u,v∈V,均有 deg(u)+deg(v)≥n-1 证明:1、首先证明满足上述条件的G是连通图。否则G至少有两支,即 G1=<V1,E1>和G2=<V2,E2> 对v1∈V1,v2 ∈V2 , 显然 deg(v1)+deg(v2)≤|V1|-1+|V2|-1=n-2 与已知矛盾,故G是连通的。 2017/3/21 计算机学院

证明(续1) 2、证明G中存在哈密尔顿道路。 设L=v1v2…vk为G中最长的一条基本道路,显然k≤n。 若k=n,则L为G中经过所有结点的道路,即为哈密尔顿道路。 若k<n,由L的最长性可知,v1和vk的全部邻接点都在L上。 若v1vkE,则v1v2…vkv1就构成G的一个包含L的圈。 若v1vkE,则存在L上的结点vi,使得 Why? 2017/3/21 计算机学院

证明(续2) v1viE  vi-1vkE。 (否则,即对viL, v1viE而vi-1vkE。设v1在L上与vi1,vi2,…,vit相邻(t≥2), 因为如果t=1,则v1只有一个邻接点vi1 , d(v1)=1, 而v1vkE,所以d(vk) ≤k-2, 有d(v1)+d(vk)≤k-1<n-1。(矛盾) Why? 则vk不能与vi1-1,vi2-1,…,vit-1中的任何一个相邻,这样就有d(vk)≤k-t-1,d(v1)=t,d(v1)+d(vk)≤k-1<n-1。推出矛盾。) 2017/3/21 计算机学院

证明(续3) 这样就可以构造一个圈 如图所示,这个圈包含了L中的全部结点。 这样,对a)和b),都可以构造一个包含L中的全部结点的一个圈C。 C=v1v2…vi-1vkvk-1…viv1。 v1 vk vi vi-1 vj vk-1 如图所示,这个圈包含了L中的全部结点。 这样,对a)和b),都可以构造一个包含L中的全部结点的一个圈C。 2017/3/21 计算机学院

由此可以看到,本定理的证明方法是一种构造性证明方法。 证明(续4) 因为k<n,所以V中还有一些结点不在C中,由G的连通性知,存在C外的结点u与C上结点vj相邻。 v1 vk vi vi-1 vj u 由此可以看到,本定理的证明方法是一种构造性证明方法。 vk-1 显然,可以构造一条基本道路P′=uvjvj+1…vi-1vkvk-1…viv1v2…vj-1。P′比P长,与L的最长性相矛盾。所以,必然k=n,即L必是G的一条哈密尔顿道路。 2017/3/21 计算机学院

定理13.5 设G=<V,E>是具有n个结点( n≥3)的简单图。如果对任意的两个结点 u,v∈V,均有 deg(u)+deg(v)≥n 则G必是哈密尔顿图。 证明:利用已知条件,仿照定理13.4 中b)的方法,可构造出一个包含所有结点的哈密尔顿圈。 定理13.5给出的是哈密尔顿图的充分条件,而不是必要条件。在六边形中,任意两个结点的度数之和都是4<6,但六边形是哈密尔顿图。 2017/3/21 计算机学院

例13-2.2 某地有5个风景点,若每个风景点均有两条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处? 解 将5个风景点看成是有5个结点的无向图,两风景点间的道路看成是无向图的边,因为每处均有两条道路与其他结点相通,故每个结点的度数均为2,从而任意两个结点的度数之和等于4,正好为总结点数减1。故此图中存在一条哈密尔顿道路,因此本题有解。 2017/3/21 计算机学院

例13-2.3 证明下图(a)所示的图中,不存在哈密尔顿圈。 (b) (a) d a b c f e i h j d f e i 证明在图(a)中,删除结点子集V1={a,b,c},得到图(b),在图(b)中,它的连通分支为4,显然有: (G-V1)=4>|V1|=3。由定理13.3可知:图(a)所示的图中不会存在哈密尔顿圈,即不是哈密尔顿图。 2017/3/21 计算机学院

例13-2.4 判断右图所示的图是否存在哈密尔顿圈。 解 若该图中存在哈密尔顿圈,则该圈组成的图中任何结点的度数均为2。 判断右图所示的图是否存在哈密尔顿圈。  a b c d e 1 2 3 4 5 解 若该图中存在哈密尔顿圈,则该圈组成的图中任何结点的度数均为2。 因而结点1、2、3、4、5所关联的边均在圈中,于是在结点a、b、c、d、e处均应将不与1、2、3、4、5关联的边删除,而要删除与结点a、b、c、d、e关联的其他边,这样一来,图就不连通了,因而图中不存在哈密尔顿圈。 2017/3/21 计算机学院

图的闭包 定理13.5的条件很强,有些图虽然不直接满足这个条件,但可以通过在一定条件下加边的办法来满足这个条件。 定义13.3 设G=<V,E>是n阶的简单图。若存在一对不 相邻的结点u,v∈V,满足 deg(u)+deg(v)≥n 则构造图G+uv,并且在图上G+uv重复上述步 骤,直至不再存在这样的结点对为止,所得之 图称为图G的闭包,记为c(G)。 2017/3/21 计算机学院

一个简单图G是哈密尔顿图当且仅当其闭包图是哈密尔顿图。 定理13.6 一个简单图G是哈密尔顿图当且仅当其闭包图是哈密尔顿图。 证明:首先证明,若u,v是G的两个非邻接结点且deg(u)+deg(v)≥n ,则G是哈密尔顿图当且仅当G+uv是哈密尔顿图。必要性是显然的。现证充分性,即G+uv是哈密尔顿图,则G中必然存在一条以u为起点,v为终点的哈密尔顿道路L,仿照定理13.4的证明过程,由L可以构造一个哈密尔顿圈,即G也是一个哈密尔顿图。 这样,在构造c(G)的过程中,所得的图与G同为哈密尔顿图或同不为哈密尔顿图,所以结论成立。 2017/3/21 计算机学院

设G=<V,E>是一个n阶无环的连通平面图。 若G含有哈密尔顿圈C,则 定理13.7 设G=<V,E>是一个n阶无环的连通平面图。 若G含有哈密尔顿圈C,则 其中 和 分别是含在圈C内部和外部的i度面的数目。 可以利用此定理来否定某些平面图是哈密尔顿图。 2017/3/21 计算机学院

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 圈内有6个5度面,圈外也有6个5度面。 2017/3/21 计算机学院

推销商问题 f e a d b c 2 2 1 2 3 4 10 2 2 6 5 设v1,v2,‥‥,vn代表n个城市, w(vivj)表示城市vi和vj之间的距离(或旅费)。 有一个商人从其中的一个城市出发,去每个城市 经商一次,最后回到出发地。问怎样安排行程以 使总的路程最短(或旅费最少)? 实际上,这个问题就是要在一个带权的完全图中,找一个各边权之和最小的哈密尔顿圈,即最优哈密尔顿圈的问题。 a b c d 1 2 5 6 10 f e 4 3 2 2 2 2 2017/3/21 计算机学院

这个问题具有重要的实际意义,但至今仍未找到一个有效的解决办法。 现在提出的解决办法有两种:求近似解和精确解。 求近似解的代表方法有回路修正法和近邻法。 下面,介绍一种求精确解的方法——分枝定界法。这个方法比较直观,对于不太复杂的权图往往很快就能得到精确解,因而也是运筹学中常用的一种方法。 2017/3/21 计算机学院

例13-2.5 给定在4个城市间旅行所需费用的矩阵如下,如何安排行程以使旅行费用最少? 该问题实际上就是要在右图中找出一个权最小的哈密尔顿圈。 2017/3/21 计算机学院

将D变成每行都有0的矩阵。先找出每行的最小元,同时用该行元素各减去这个最小元,然后再对每列施行同样的方法,得到以下矩阵: 2017/3/21 计算机学院

在 中的 行找到最小元(1,4): 如(1,4)包含在最优解中,则从 中划去第一行和第四列,同时将元(4,1)改成(为什么?),所得矩阵记为 。 的第一行没有0元,最小元是1,于是对应的权下界累计为32。 2017/3/21 计算机学院

如最优解不包含(1,4)时,由  得到的权下界是31,比  所得下界32要小,自然选择具有最小累计下界的矩阵求解。由于已假定最优解不包含(1,4),因此在  中将(1,4)改为,所得矩阵记为  ,它的第一行的最小元素为6,从而使累计下界变成37,大于  的下界,故暂停搜索,转而处理  。 2017/3/21 计算机学院

在 中(2,3)是0。假定最优解包含(2,3),划掉 行和 列,同时将(3,2)改为,所得矩阵记为 ,它对应的权下界仍为32,是当前最小下界,因此,继续沿这一方向搜索。 2017/3/21 计算机学院

在 中(3,1)是0。假定最优解包含(3,1),划掉 行和 列后,只剩下(4,2),且元素(4,2)为0,累计权下界仍为32,是最小的下界;同时,我们已获得一条 哈密尔顿圈,其权为32。 即 8+3+18+3=32 2017/3/21 计算机学院

习题十三 9、10、12、14、16、17 2017/3/21 计算机学院