离散数学第七章图论ppt课件

除用图形表示图外 还可用矩阵表示图 它的优点 1 将图的问题变为数学计算问题 从而可借助计算机来研究图 进行相关的计算 2 表示更清楚 知识点 1 邻接矩阵邻接矩阵求两点间不同长度的路的条数2 可达性矩阵3 完全关联矩阵由于矩阵的行和列有固定的次序 因此在用矩阵表示图时 先要将图的结点进行排序 若不具体说明排序 则默认为书写集合V时结点的顺序 7 3图的矩阵表示 1 预备知识 2 预备知识 3 一 图的邻接矩阵 以结点与结点之间的邻接关系确定的矩阵 定义7 3 1设简单图G 其中V v1 v2 vn 则n阶方阵A G aij n n 称为图G的邻接矩阵 其中第i行j列的元素 4 图的邻接矩阵例 例7 3 1 1 写出下面无向图的邻接矩阵 5 例7 3 1 2 写出下面有向图的邻接矩阵 图的邻接矩阵例 0100001111011000 A G 6 1 邻接矩阵的主对角线元素aii 0 2 主对角线以外的元素aijaij 1 ij 说明图G是完全图 aij 0 ij 说明图G是零图 3 无向图的邻接矩阵是对称的 而有向图的邻接矩阵不一定对称 因为在无向图中一条无向边应看成方向相反的两条有向边 因此无向图的邻接矩阵关于主对角线对称 图的邻接矩阵说明 7 4 结点的度数无向图 每行1的个数 每列1的个数 对应结点的度有向图 每行1的个数 对应结点的出度每列1的个数 对应结点的入度 图的邻接矩阵说明 8 图的邻接矩阵的应用 1 由邻接矩阵可计算出从vi到vj的长度为L的路的数目 也可计算从vi出发的长度为L的回路数 2 计算结点vi与vj之间的距离 3 判断G是否是连通图 及G中任意两个结点是否连通 9 图G的邻接矩阵为 A2中 G中从结点v2到结点v3长度为2路数目为0 A3中 G中从结点v2到结点v3长度为3的路数目为2 A2中 G中长度为2的路 含回路 总数为8 其中6条为回路 A3中 G中长度为3的路 含回路 总数为10 其中0条为回路 aij 2 ai1 a1j ai2 a2j ai3 a3j ain anjaij L 1 ai1 a1j L ai2 a2j L ai3 a3j L ain anj L 10 图的邻接矩阵的应用 1 由邻接矩阵可计算出从vi到vj的长度为L的路的数目 可计算从vi出发的长度为L的回路数 定理7 3 1设G是具有结点集 v1 v2 vn 和邻接矩阵A的图 则矩阵AL l 1 2 的第i行第j列的元素aij L m 表示图G中从结点vi到vj长度为L的路有m条 即路的数目 aij 2 ai1 a1j ai2 a2j ai3 a3j ain anjaij L 1 ai1 a1j L ai2 a2j L ai3 a3j L ain anj L 11 定理7 3 1设G是具有结点集 v1 v2 vn 和邻接矩阵A的图 则矩阵AL l 1 2 的第i行第j列的元素aij L m 表示图G中从结点vi到vj长度为L的路有m条 即路的数目 证明 从vi到vj的长度为l的路可看作从vi到vk的长度为1的路 再联结vk到vj的长度为l 1的路 用数学归纳法 1 当l 2时 成立 2 设l p时命题对l成立 即aij p 表示图G中有几条从结点vi到vj长度为p的路 即路的数目 12 3 证明l p 1时定理成立 由故而aik是结点vi到vk长度为1的路的数目 是结点vk到vj长度为p的路的数目 所以上式右边的每一项表示从vi经过一条边到vk 再由vk经过一条长度为p的路到vj的总长度为p 1的路的数目 对所有k求和 是所有从vi到vj的长度为p 1的路的数目 所以对l p 1成立 证毕 定理7 3 1设G是具有结点集 v1 v2 vn 和邻接矩阵A的图 则矩阵AL l 1 2 的第i行第j列的元素aij L m 表示图G中从结点vi到vj长度为L的路有m条 即路的数目 13 图的邻接矩阵求不同长度的路例 例7 3 2 求下图中图G的从结点v2到结点v3长度为2和3的路数目及所有长度为2和3的路数目 分析利用定理7 3 1 求图中长度为m的路数目 只需要先写出图的邻接矩阵 然后计算邻接矩阵的m次方即可 14 图G的邻接矩阵为 G中从结点v2到结点v3长度为2通路数目为0 G中长度为2的路 含回路 总数为8 其中6条为回路 G中从结点v2到结点v3长度为3的通路数目为2 G中长度为3的路 含回路 总数为10 其中0条为回路 15 若中至少有一个不为0 则可断定vi与vj相连接 求中不为0的最小的L即为d 2 计算结点vi与vj之间的距离 图的邻接矩阵的应用 如 d 1 d 2 d 1 d 16 3 判断G是否是连通图 及G中任意两个结点是否连通 计算B A1 A2 An bij表示从结点vi到vj有长度分别为1 2 3 n的不同长度路的总数 连通图的判断若B的每一个元素都非0 则为连通图 结点间的连通性若bij为0 那么结点vi与vj不相连接 若bij不为0 vi与vj有路相连接 图的邻接矩阵的应用 17 在许多问题中需要判断有向图的一个结点vi到另一个结点vj是否存在路的问题 如果利用图G的邻接矩阵A 则可计算A A2 A3 An 当发现其中的某个Al的 1 就表明结点vi到vj可达 二 有向图的可达矩阵 1 可达矩阵的定义 2 可达矩阵的计算方法 3 可达矩阵的应用 18 可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路 定义7 3 2设简单有向图G V E 其中V v1 v2 vn n阶方阵P pij n n 称为图G的可达性矩阵 其中第i行j列的元素 从vi到vj没有路 至少有一条路 和 0 v v 1 p j i ij 11100 11100 11100 00011 00011 一 有向图的可达性矩阵 19 设G是n阶简单有向图 由可达性矩阵的定义知 当i j时 如果vi到vj有路 则pij 1 如果vi到vj无路 则pij 0 又由定理7 2 1知 如果vi到vj有路 则必存在长度小于等于n 1的路 通过对图G的邻接矩阵A进行运算可得到G的可达性矩阵P 其方法如下 1 由A计算A2 A3 An 2 计算B A A2 An 3 将矩阵B中非零元素改为1 所得到的矩阵即为可达性矩阵P 二 图的可达性矩阵计算方法 1 20 由邻接矩阵A求可达性矩阵P的另一方法 将邻接矩阵A看作是布尔矩阵 矩阵的乘法运算和加法运算中 元素之间的加法与乘法采用布尔运算布尔乘 只有1 1 1布尔加 只有0 0 0计算过程 1 由A 计算A2 A3 An 2 计算P A A2 AnP便是所要求的可达性矩阵 图的可达性矩阵计算方法 2 无向图的可达性矩阵称为连通矩阵 也是对称的 图的可达性矩阵计算方法 3 Warshall算法 21 A 4 A 2 A 5 A 3 解 例7 3 3求右图中图G中的可达性矩阵 分析 先计算图的邻接矩阵A布尔乘法的的2 3 4 5次幂 然后做布尔加即可 P A A 2 A 3 A 4 A 5 22 图的可达性矩阵的应用 1 利用可达性矩阵判断有向图的连通性 强连通单侧连通弱连通 2 求强分图 3 利用可达性矩阵判断无向图的连通性 无向图G为连通图的充要条件是图的可达性矩阵所有元素均为1 23 2 利用可达性矩阵判断有向图的连通性 有向图G为强连通的充要条件是图的可达性矩阵所有元素均为1 有向图G为单侧连通的充要条件是图的可达性矩阵P及其转置矩阵PT所组成的矩阵P P PT 在P 中除对角线元素外所有元素均为1 原因 设PT为Q 即qij pji 若qij pij 1 则结点vi与vj可达 或vj与vi可达 若qij pij 0 则结点vi与vj不可达 有向图G为弱连通的充要条件是忽略边的方向得到矩阵B A AT 求B的可达性矩阵PB 在PB中除对角线元素外所有元素均为1 24 利用可达性矩阵判断有向图的连通性 强连通图 25 利用可达性矩阵判断有向图的连通性 单侧连通图 26 3 利用可达性矩阵P 求强分图 方法 设PT为P的转置矩阵 由P PT求强分图原因 因为对PT PijT Pji若从vi到vj可达 则Pij 1 若从vj到vi可达 则Pji 1 即PijT 1 于是当且仅当Vi和Vj相互可达时 P PT的第 i j 项Pij PijT值为1 步骤如下 计算可达性矩阵P 计算P的转置矩阵PT 计算P PT P PT第i行元素为1的在第j1 j2 jk列 则结点vi vj1 vj2 vjk在同一个强连通分支中 即 vi vj1 vj2 vjk 导出的子图是G的一个强连通分支 27 例 强分图为 v1 v3 v2 v4 v5 由可达性矩阵 求强分图例 V1 V2 V3 V4 V5 28 可达矩阵的应用 判断是否存在递归调用 设P P1 P2 Pn 表示程序中的函数集合 对应为结点 若一函数Pi调用Pj 则在有向图中用从Pi到Pj的有向边表示 设函数集合P P1 P2 P3 P4 P5 调用关系 P1调用P2 P2调用P4 P3调用P1 P4调用P5 P5调用P2 29 可达矩阵的应用 P2 P4 P5产生递归调用 P1 P2 P3 P4 P5 30 完全关联矩阵表示结点和边的关系无向图的完全关联矩阵有向图的完全关联矩阵 四 图的完全关联矩阵 结点和边关系 31 定义7 3 3给定无向图G V v1 v2 vp E e1 e2 eq 则矩阵M G mij p q 其中 称M G 为G的完全关联矩阵 无向图的完全关联矩阵 结点和边关系 32 110011111000001101000110000000 图的完全关联矩阵例 33 3 这个结果正是握手定理的内容 即各结点的度数之和等于边数的2倍 4 一行中元素全为0 其对应结点是孤立结点 5 若两列相同 则相应的两边平行 2 每行元素的和即 是结点vi的度数deg vi 1 图中的一边关联两个点 M G 中每列中只有两个1 图的完全关联矩阵性质 34 定义7 3 3给定简单有向图G V v1 v2 vp E e1 e2 eq 则矩阵M G mij p q 其中 称M G 为G的完全关联矩阵 有向图的完全关联矩阵 35 v1V2V3V4v5 M G e1e2e3e4e5e6e7 1000111 11000000 1100 1000 1100 1000 1 100 e3 e1 e2 e5 e4 e6 e7 v2 v1 v3 v4 v5 有向图的完全关联矩阵例 36 1 图中的一边关联两个点 M G 中每列中只有一个1和一个 1 2 每行中1的个数和 1的个数分别为相应结点的出度 入度 3 结点vi的度数 4 一行中元素全为0 其对应结点是孤立结点 有向图的完全关联矩阵性质 37 小结 掌握邻接矩阵 有向图 无向图 的求法及性质应用理解利用邻接矩阵求两点间不同长度的路的数目掌握有向图可达性矩阵的求法了解完全关联矩阵的求法及性质 38 7 4欧拉图和汉密尔顿图 具有某种特殊路 回路 的图 知识点 欧拉路 回路 定义 七桥问题 一笔画问题欧拉路 回路 判别定理有向图欧拉路 回路 汉密尔顿路 回路 定义 周游世界问题汉密尔顿路 回路 必要条件汉密尔顿路 回路 充分条件图的闭包 39 欧拉图与汉密尔顿图总结 欧拉图与汉密尔顿图的判别方法 全体非空连通图 满足定理7 4 1的条件 不满足定理7 4 1的条件 欧拉图 非欧拉图 全体非空连通图 汉密尔顿图 非汉密尔顿图 满足必要条件但不满足任何充分条件 至少满足一个充分条件 不满足某个必要条件 不能根据已知的充分条件或已知的必要条件判别是否是汉密尔顿图 根据给定的图的特点采用特定的方法1 若能找到汉密尔顿回路 则它是汉密尔顿图 2 反证法 假设存在一个汉密尔顿回路 如果导致发生矛盾 则它不是汉密尔顿图 3 暂时无法判别 40 1 欧拉图 1 七桥问题 一笔画 欧拉 回 路 欧拉图 2 判定欧拉图的充分必要条件 求欧拉回路的算法 41 七桥问题 1736年瑞士数学家列昂哈德 欧拉 leonhardEuler 发表了图论的第一篇论文 哥尼斯堡七桥问题 这个问题是这样的 哥尼斯堡 K nigsberg 城市有一条横贯全城的普雷格尔 PreGel 河 城的各部分用七座桥连接 每逢假日 城中的居民进行环城的逛游 这样就产生一个问题 能不能设计一次 逛游 使得从某地出发对每座跨河桥走一次 而在遍历了七桥之后却又能回到原地 42 七桥问题的图表示 图中的结点A B C D表示四块地 而边表示七座桥 哥尼斯堡七桥问题是在图中找寻经过每一条边且仅一次而回到原地的路 欧拉在1736年的一篇论文中提出了一条简单的准则 确定了哥尼斯堡七桥问题是不能解的 g f a b c d e 43 一笔画 与七桥问题类似的还有一笔画的判别问题 要判定一个图G是否可一笔画出 有两种情况 一是从图G中某一结点出发 经过图G的每一边一次且仅一次到达另一结点 另一种就是从G的某个结点出发 经过G的每一边一次且仅一次回到该结点 上述两种情况可以由欧拉路和欧拉回路的判定条件给予解决 44 欧拉图 Eulerian 定义7 4 1欧拉路 Eulertrail 无孤立结点的图 无向图或有向图 若存在一条路 经过图中所有边一次且一次 该条路称为欧拉路 欧拉回路 Eulertour circuit 若存在一条回路 经过图中所有边一次且一次 该回路称为欧拉回路 欧拉图 Eulerian 有欧拉回路的图 半欧拉图 semi Eulerian 有欧拉路的图 几点说明 平凡图是欧拉图 环不影响图的欧拉性 单向欧拉路 回路 给定有向图 通过图中每个结点一次且一次的单向路 回路 称作单向欧拉路 回路 45 欧拉图的判定例7 4 1 e1 e2 2 欧拉图 半欧拉图 非 半 欧拉图 欧拉图 半欧拉图 非 半 欧拉图 46 无向图的欧拉路及欧拉回路的判断方法 定理7 4 1无向图G具有一条欧拉路 当且仅当G是连通的 且有零个或两个奇数度数的结点 推论 无向图G具有一条欧拉回路 当且仅当G是连通的 所有结点的度数均为偶数 有向图的欧拉路及欧拉回路的判断方法 定理7 4 2有向图G具有一条单向欧拉回路 当且仅当是G是强连通的 且每个结点的入度等于出度 推论 一个有向图G具有单向欧拉路 当且仅当是G是单侧连通的 而且除两个结点外 每个结点的入度等于出度 但这两个结点中 一个结点的入度比出度大1 终点 另一个结点的入度比出度小1 起点 这个定理的证明可以看作是定理7 4 1 无向图的欧拉路 的推广 因为对于有向图的任意一个结点来说 如果入度与出度相等 则该结点的总度数为偶数 若入度和出度之差为1时 其总度数为奇数 其原理就是每个结点都要能进去多少次就能出来多少次 47 一笔画 g f a b c d e 无向图G存在欧拉路 当且仅当 A G中所有结点的度数全为偶数B G中至多有两个奇数度结点C G连通且所有结点的度数全为偶数D G连通且至多有两个奇数度结点 g f a b c d e 思考题 无向连通图含G有m个奇数度结点 问 1 至少加入多少条边才能使图G变为欧拉图 2 至少加入多少条边才能使图G变为半欧拉图 48 例7 4 3欧拉路 回路 判定 欧拉路 回路 判定 半欧拉图 欧拉图 非 半 欧拉图 欧拉图 半欧拉图 非 半 欧拉图 49 定理7 4 1无向图G具有一条欧拉路 当且仅当G是连通的 且有零个或两个奇数度数的结点 证明 设无向图G具有一条欧拉路 则G是连通的 且有零个或两个奇数度数的结点 设G有欧拉路L 即有点边序列v0e1v1e2 eiviei 1 envn 其中结点可能重复出现 但边不重复 1 证G是连通的 欧拉路L经过G的所有边 即经过所有结点 G必连通 2 证有零个或两个奇数度数 对任意一个不是端点的结点vi 每当沿欧拉路L经过vi一次 都经过该结点关联的两条边 一进一出 即给结点的度数加2 vi可重复出现 但deg vi 必是偶数 对于端点v0 vn 若v0 vn 则deg v0 必是奇数 起点仅有射出边 若在路中也出现 度数必为偶数 1 偶数 奇数 则deg vn 必是奇数 终点仅有射入边 同上 若v0 vn 则deg v0 必是偶数 2 偶数 偶数 实质为欧拉回路 50 证明 设无向图G是连通的 且有零个或两个奇数度数的结点 则G具有一条欧拉路 方法 构造法证明 思想 圈套圈 1 若有两个奇数度数结点 则从其中一个结点出发 开始构造一条边不同的路 即迹 方法 从v0出发 经关联边e1进入v1 若deg v1 为偶数 则必可由v1再关联边e2进入v2 如此下去 每边仅取一次 由于G连通 必可到达另一奇数度数结点停下来 得到一条迹L1 2 若L1通过了G的所有边 则L1为欧拉路 3 若G去掉L1 已通过的边 后得到的子图为G 由剩余的边组成 则G 中每个结点的度数为偶数 因为原G为连通的 则L1与G 至少有一个结点vi是重合的 在G 中从vi出发 重复 1 方法 得到另一迹L2 L1 L2合并在一起为新的L1 如果恰为G 即得欧拉路 否则重复 3 可得到另一迹L3 以此类推直到得到一条经过G中所有边的欧拉路 定理7 4 1无向图G具有一条欧拉路 当且仅当G是连通的 且有零个或两个奇数度数的结点 51 逐步插入回路算法举例 走法一 走法二 52 找出穆罕默德短弯刀的欧拉回路 例题 j h k 53 解在图中 仅有两个度数为奇数的结点b c 因而存在从b到c的欧拉路 蚂蚁乙走到c只要走一条欧拉路 边数为9条 而蚂蚁甲要想走完所有的边到达c 至少要先走一条边到达b 再走一条欧拉路 因而它至少要走10条边才能到达c 所以乙必胜 欧拉图应用1 蚂蚁比赛问题 例甲 乙两只蚂蚁分别位于右图中的结点a b处 并设图中的边长度是相等的 甲 乙进行比赛 从它们所在的结点出发 走过图中的所有边最后到达结点c处 如果它们的速度相同 问谁先到达目的地 54 例设G为n n 2 阶无向欧拉图 证明G中无桥 割边 即 G 2 方法一 直接证法 从桥与欧拉图定义考虑 利用闭迹的一个性质 记为 删除任意闭迹上的一条边 仍连通 因为G为欧拉图 所以存在欧拉回路 设C为其中的一条欧拉回路 则G中任何边均在C上 于是 对于任意的e E G 删除e后的图记为G G e C e 由 可知 G 仍连通 故由桥的定义可知 e不是G中的桥 由e的任意性得证 G中无桥 即 G 2 欧拉图应用2 55 方法二 反证法 利用欧拉图的性质及握手定理的推论假设G中存在桥e u v 由于G为欧拉图 所以e的两个端点在G中的度数deg u deg v 均为偶数 因为e为G中桥 所以G G e 由两个连通分支G1和G2组成 不妨设u V G1 v V G2 由于删除了e 因而在G1和G2中 deg u 与deg v 为奇度结点 而对于任意的w V G1 w u deg w 为偶数 即G1中只有一个奇度结点u 类似地 G2中也只有一个奇度结点v 这与握手定理的推论矛盾 故G中不可能含桥 即 G 2 欧拉图应用2 续 例设G为n n 2 阶无向欧拉图 证明G中无桥 割边 即 G 2 56 欧拉图应用3 例 设G是恰有2k k 1 个奇度结点的无向连通图 证明G中边能分为k条边不重的迹 P1 P2 Pk 证明 将G中的2k个奇度结点分为数目相同的两组为 u1 u2 uk v1 v2 vk 对图G加边 u1 v1 u2 v2 uk vk 共k条得图G 则G 中每个结点的度数均为偶数 故存在一条欧拉回路 即有闭迹 若在G中删去边 u1 v1 则得一条欧拉路 两端点为u1 v1 结点u2和v2在此路中 再删去边 u2 v2 则得两条不同的迹 有四个端点分别为u1 u2 v1 v2 而u3 v3在其中一条迹中 再删除边 u3 v3 则得3条不同的迹 u4 v4在其一条中 依次继续 直到删去全部加边可得到k条不同的迹 57 欧拉图主要内容 1 欧拉路 欧拉回路 欧拉图 半欧拉图的定义 2 判别定理 有向与无向 3 求欧拉图中欧拉回路的算法 欧拉图是若干个边不重的圈之并 58 2 汉密尔顿回路 1859年威廉 汉密尔顿爵士在给他的朋友的一封信中 问题1 在一个十二面体中能否找到一条回路 使它含有这个图的所有结点 问题2 把每个结点看成一个城市 联结两个结点的边看成是交通线 能否找到旅行路线 沿着交通线经过每个城市恰好一次 再回到原来的出发地 他把这个问题称为周游世界问题 59 周游世界 SirWilliamRowanHamilton 1859 Icosiangame 60 汉密尔顿图定义 定义7 4 3给定图G 若存在一条路经过图中的每一个结点恰好一次 这条路称作汉密尔顿路 若存在一条回路 经过图中的每一个结点恰好一次 这个回路称作汉密尔顿回路 具有汉密尔顿回路的图称为汉密尔顿图 具有汉密尔顿路的图称为半汉密尔顿图 几点说明 1 平凡图是汉密尔顿图 2 环与平行边不影响图的汉密尔顿性 61 例 a c b a c d 既存在汉密尔顿通路 又存在汉密尔顿回路 即为汉密尔顿图 既不存在汉密尔顿通路 也不存在汉密尔顿回路 既存在汉密尔顿通路 又存在汉密尔顿回路 即为汉密尔顿图 存在汉密尔顿通路 但不存在汉密尔顿回路 62 例 证明Kn n 3 是汉密尔顿图 证明 例用构造法来获得一个汉密尔顿回路 在Kn中 从任意一个结点v1开始前进 由于和其它的所有结点都有边相连 则可以沿着某条边到达另一个结点 设为v2 v2也与其它的所有结点有边相连 若除v1和v2外还有结点没遍历到的话 可以经过某个边到达一个新的结点v3 依次类推 由于每个结点都与其他任何结点相连接 只要有结点没遍历到的话 必然能找到新的边到达该结点 最终可以遍历所有结点后回到v2 得到汉密尔顿回路 63 欧拉图与汉密尔顿图的关系 欧拉图不一定是汉密尔顿图 汉密尔顿图也不一定是欧拉图 有的图既是欧拉图也是汉密尔顿图有的图既不是欧拉图也不是汉密尔顿图 Petersen图 64 汉密尔顿图的相关定理 无向汉密尔顿图的充分条件满足P 则汉密尔顿图 用于汉密尔顿图的判定及计算 但是不满足P 也可能是汉密尔顿图 无向汉密尔顿图的必要条件汉密尔顿图则Q 用于非汉密尔顿图的判定 即非Q则非汉密尔顿图 65 无向半汉密尔顿图的充分条件 定理7 4 4 设G是n阶无向简单图 若对G中任意结点u与v有deg u deg v n 1则G是半汉密尔顿图 图中存在汉密尔顿路 定理7 4 5 设G是n 3 阶无向简单图 若对G中任意结点u与v有deg u deg v n则G是汉密尔顿图 66 无向半汉密尔顿图的充分条件 定理7 4 4 设G是n阶无向简单图 若对G中任意结点u与v有deg u deg v n 1则G是半汉密尔顿图 图中存在汉密尔顿路 证明思想 一 G连通 二 构造汉密尔顿路 1 由极大路径得圈 路径即为通路 2 由圈得更长路径路径 极大路径 圈 更长路径 更长极大路径 更长圈 更长路径 汉密尔顿路 只要在G中构作出一条长为n 1的汉密尔顿路即可得证 67 定理7 4 4 设G是n阶无向简单图 若对G中任意结点u与v有deg u deg v n 1 则G是半汉密尔顿图 证明 一 G连通 反证法 若G不是连通图 则G至少有两个连通分支 设为G1 G2 其阶数为分别为n1 n2 设v1 V G1 v2 V G2 因为G是简单图 所以degG1 v1 n1 1degG2 v2 n2 1因此 degG v1 degG v2 degG1 v1 degG2 v2 n1 1 n2 1 n 2 n 1与已知条件 deg u deg v n 1 矛盾 所以G连通 无向半汉密尔顿图的充分条件 68 无向半汉密尔顿图的充分条件 二 构造汉密尔顿路证明汉密尔顿回路存在的过程其实就是构造这条回路的过程 分成以下几个步骤 1 构造极大路径任意找两个相邻的结点S和T 在它们基础上扩展出一条尽量长的没有重复结点的路 也就是说 如果S与结点v相邻 而且v不在路S T上 则可以把该路变成v S T 然后v成为新的S 从S和T分别向两头扩展 直到无法扩为止 即所有与S或T相邻的结点都在路S T上 令P为G中任意一条长为p 1 p n 的通路 设其结点序列为v1 v2 vp 69 2 构造圈由极大路径得圈 设极大路径 v1 vp p n 1 反复应用下面方法来扩充这一通路 直到P长度为n 1 即包括所有结点 若 v1 vp E 即v1和vp相邻 则得圈C v1 vpv1 若 v1 vp E 即v1和vp不相邻 可构造出一个回路 可以证明存在结点vi i 1 p 满足vi与v1相邻 且vi 1与vp相邻 反证法 设v1与 上的k个结点 记为vi1 vi2 vik 相邻 则vp与vi1 1 vik 1之一相邻 否则 即vp与vi1 1 vik 1均不相邻 则vp至多邻接于p 2 k结点 即deg vp p 2 k deg v1 k deg v1 deg vp k p 2 k p 2 n 3 与题设矛盾 无向半汉密尔顿图的充分条件 70 定理7 4 4 证明 2 续 找到了满足条件的结点vir以后 于是得圈C v1 vir 1vpvp 1 virv1 方法 在P中添加边 v1 vir vP vir 1 删除边 vir 1 vir v1 vp vir 1 vir v1 vp vir vir 1 71 定理7 4 4 证明 3 3 由圈得更长路径 连通考虑G中这条包含v1 v2 vp 长度为p的回路 由于p n 所以V中还有一些结点不在C中 即必有回路外结点v与回路上结点 例如vk 相邻 在C中删除边 vk 1 vk 而添加边 v vk 得到通路P vvkvk 1 vir 1vpvp 1r virv1 显然 P 比P长1 且P 上有k 1个不同的结点 如图所示 可以得到一条长度为p的 包含v1 v2 vp的通路 vvkvk 1 vir 1vpvp 1r virv1 如此继续下去 直到得到一个包含所有结点的圈为止 72 vir 1 定理7 4 4 证明 3 v v1 vp vir 1 vir vk 1 vk v v1 vp vir vk 1 vk 73 无向汉密尔顿图的充分条件 定理7 4 5 设G是n 3 阶无向简单图 若对G中任意结点u与v有deg u deg v n则G是汉密尔顿图 证明 由定理7 4 4知G连通且有汉密尔顿路 v1v2 vp 1 若 v1 vp E 则得汉密尔顿回路C v1v2 vpv1 2 若 v1 vp E 则与定理7 4 4证明 2b 类似 也存在汉密尔顿回路 74 4 1 3 6 2 5 极大路径 6 1 3 4 2 56仅与1 2 3邻接 5与1 2 4邻接其中6邻接于2 5邻接于4 汉密尔顿回路 6 1 3 4 5 2 6 6 3 2 1 5 4 75 例题汉密尔顿图的判定 判定图是否存在汉密尔顿回路 解 在图中 有5个结点 deg 1 3 deg 2 3 deg 3 4 deg 4 3 deg 5 3 由于每一对结点的度数之和都大于5 所以G中存在一条汉密尔顿回路 如1 3 2 5 4 1 利用充分条件判定汉密尔顿图例 76 汉密尔顿图判定 定理给出的是汉密尔顿图 半汉密尔顿图 的充分条件 而不是必要条件 即具有n个结点的无向图G 若对任意两个不相邻的结点u v E 均有deg u deg v n 或deg u deg v n 但是G中仍然会存在汉密尔顿路 或汉密尔顿路 例图 a 有6个结点 任意两个结点度数的和小于5 但图中存在一条汉密尔顿路 例如 图 b 六边形中 任意两个不相邻的结点度数之和都是4 4 6 但是六边形存在汉密尔顿回路 a b 77 例考虑在七天内安排七门课程的考试 使得同一位教师所任的两门课程考试不排在接连的两天中 试证明如果没有教师担任多于四门课程 则符合上述要求的考试安排总是可能的 证明 结点 每个结点对应于一门课程考试 共七个结点 边 关联的两个结点对应的课程考试是由不同教师担任的 构成7阶无向简单图 vi V deg vi 为与vi不是由同一位教师任课的数目 因为每个教师所任课程数不超过4 故每个结点的度数至少是3 即deg v 3 任两个结点的度数之和至少是6 故G总是包含一条汉密尔顿路 它对应于一个七门考试课目的一个适当的安排 汉密尔顿图应用1 78 例在某次国际会议的预备会中 共有8人参加 他们来自不同的国家 已知他们中任何两个无共同语言的人中的每一个 与其余有共同语言的人数之和大于或等于8 问能否将这8个人排在圆桌旁 使其任何人都能与两边的人交谈 证明 结点 参加会议的人 共8个 边 相关联的结点有共同语言 构成8阶无向简单图 vi V deg vi 为与vi有共同语言的人数 由已知条件可知 vi vj V且i j 均有deg vi deg vj 8 由定理7 4 5可知 G中存在汉密尔顿回路 设C为G中一条汉密尔顿回路 按这条回路的顺序安排座次即可 汉密尔顿图应用2 79 汉密尔顿图应用2的具体例子 例设已知下列事实 a会讲英语 b会讲英语和汉语 c会讲英语 意大利语和俄语 d会讲日语和汉语 e会讲德语和意大利语 f会讲法语 日语和俄语 g会讲法语 德语 问这7个人应如何排座位 才能使每个人和他身边的人交谈 解 设无向图G 其中 V a b c d e f g E u v V且u和v有共同语言 如下图所示 图G是连通图 将这七个人排座围圆桌而座 使得每个人能与两边交谈 即在图G中找汉密尔顿回路 经观察 该回路是abdfgeca a c b e d f g 80 例今有n个人 已知他们中的任何二人合起来认识其余的n 2个人 证明下列各题 1 当n 3时 这n个人能排成一列 使得中间的任何人都认识两旁的人 而两端的人认识左边 或右边 的人 2 当n 4时 这n个人能排成一个圈 使得每个人都认识两旁的人 汉密尔顿图应用3 自学 81 证明 作无向图G 其中V v v为此人群的成员 则 V n 并可将V表成V v1 v2 vn E u v u v V u v 且u与v认识 则G为n阶无向简单图 由题中给的条件可知 u v V 若u v 则deg u deg v n 2 记为 要证明G中存在汉密尔顿路或回路 需要对于vi vj V i j 分vi与vj是否认识两种情况讨论 汉密尔顿图应用3 自学 82 vi与vj认识 则deg vi deg vj 2 n 2 n vi与vj不认识 则对于任意vk V 且k i k j vi与vj都认识vk 反证法 否则vi或vj不认识vk 比如说vi不认识vk 此时 vj与vk都不认识vi 认识是彼此的 则vj与vk合起来至多认识其余的n 3个人 这与已知矛盾 于是 vi与vj都认识vk 因而由vk的任意性可知deg vi deg vj 2 n 2 1 当n 3时 2 n 2 n 1 即deg vi deg vj n 1 于是 无论vi与vj是否认识 都有deg vi deg vj n 1 由vi vj的任意性可知 G中存在汉密尔顿路 只需按 上结点的顺序排列就可以达到要求 2 当n 4时 2 n 2 n 即deg vi deg vj n因而 无论vi与vj是否认识 都有deg vi deg vj n G中存在汉密尔顿回路C 按C中顺序排圈即可达到目的 汉密尔顿图应用3 自学 83 汉密尔顿图判定 不满足充分条件 不能由此判断它是否汉密尔顿图 事实上 它不满足必要条件 故不是汉密尔顿图 84 无向汉密尔顿图的必要条件 定理7 4 3 若图G 具有汉密尔顿回路 即G是汉密尔顿图 则对于结点集V的每一个非空子集S均有W G S S 成立 其中W G S 是G S中连通分支数 S 是结点子集S中结点的个数 汉密尔顿图必有W G S S 但满足W G S S 的不一定是汉密尔顿图 用于判定非汉密尔顿图 W G S S 则为非汉密尔顿图 85 无向汉密尔顿图的必要条件W G S S 知识点 母图的连通分支数小于等于生成子图的连通分支数 删除圈中的结点产生的连通分支数 删除结点个数证明 设C是G的一条汉密尔顿回路 则对于V的任何一个非空子集S 由点不重复的回路的特性知任意删去C中 S 个点 最多将C分为 S 段 即W C S S 若在C中删去S中任一结点a1 则C a1是连通非回路 即W C a1 1 若删去S中的另一个结点a2 则当a1 a2邻接时 W C a1 a2 1 2 而当a1 a2不邻接时 W C a1 a2 2 即W C a1 a2 2 a1 a2 如此做下去 归纳可证W C S S 因为C S是G S的一个生成子图 且母图的连通分支数小于等于生成子图的连通分支数 因而W G S W C S 所以W G S S 86 例判断是否为汉密尔顿图 必要条件的应用例 在图中取 S 5 则W G S 6 S 5 因而该图不存在汉密尔顿回路 87 在图中取S v1 v4 则G S中有三个连通分支 即W G S 3 S 2 故G不是汉密尔顿图 必要条件的应用例 例判断下图是否为汉密尔顿图 因此选取非空子集S很重要 88 通过例子说明定理7 4 3是必要条件 所以并不能作为汉密尔顿图的判定条件 例7 4 7 著名的彼得森 Petersen 图 如右图所示在图中删去任一个结点或任意两个结点 不能使它不连通 S 1 W G S 1 1 S 2 W G S 1 S 删去三个结点 最多只能得到有两个连通分支的子图 S 3 W G S 2 S 89 删去四个结点 最多只能得到有三个连通分支的子图 S 4 W G S 3 S 删去五个或五个以上的结点 余下的结点数都不大于5 故必不能有5个以上的连通分支数 S 5 W G S 5 S 所以该图满足W C S S 但是可以证明它非汉密尔顿图 Petersen图满足 S W G S S Petersen图不是汉密尔顿图 穷举Petersen图是半汉密尔顿图 必要条件的应用例 90 例汉密尔顿图的判定 设G是n阶无向连通图 若G中有割点或割边 则G不是汉密尔顿图 证明 设v是图G中的割点 或与图G中割边相关联的端点中的任一个 则W G v 2 v 因此 图G不是汉密尔顿图 必要条件的应用例 91 非汉密尔顿图的判定 例证明右上图不是汉密尔顿图直接利用必要条件定理证明令V1 a h l c j e W G V1 7 6 见右图 由定理可知 该图不是汉密尔顿图 92 非汉密尔顿图的判定 证明下图 a 所示的图中 不存在汉密尔顿回路 证明在图 a 中 删除结点子集S a b c 得到图 b 在图 b 中 它的连通分支为4 显然有 W G S 4 V1 3 由定理t 4 3可知 图 a 所示的图中不会存在汉密尔顿回路 即不是汉密尔顿图 93 证明右图所示的图中没有汉密尔顿路 非汉密尔顿图的判定 证明 利用标记法证明 任取一结点如1用A标记 所有与它邻接的结点用B标记 继续不断地用A标记所有邻接于B的结点 用B标记所有邻接于A的结点 直到所有结点都标记完毕 称为标记法 如果存在汉密尔顿路 那么对于偶数阶图 A B的数目相同 对于奇数阶图 两者相差1 然而该图中有3个结点标记为A 5个结点标记为B 它们相差两个 所以该图不存在汉密尔顿路 94 汉密尔顿图的判定 标记法不是判断汉密尔顿图的充分条件 不可判断汉密尔顿路的存在性 注意 如果在标记过程中 遇到相邻结点出现相同标记时 可在此对应边上增加一个结点 并标上相异标记 Petersen图 A个数 7B个数 6 A B B B A A A B B B A A A 95 图的闭包的定义 自学 定义7 4 4给定图G V E 有n个结点 若将图G中度数之和至少是n n 的非邻接结点连接起来得图G 对图G 重复上述步骤 直到不再有这样的结点对为止 所得到的图 称为原图G的闭包 记作C G 96 如图给出了六个结点的一个图 构造它的闭包过程 在这个例子中C G 是一个完全图 一般情况下 C G 也可能不是一个完全图 图的闭包 自学 97 图的闭包例 自学 求下图的闭包 98 定理7 4 6当且仅当一个简单图的闭包是汉密尔顿图时 这个简单图是汉密尔顿图 证明 略目前关于图中有没有汉密尔顿路的判别尚未有通用的方法 判断汉密尔顿图的充分必要条件 汉密尔顿图的充分必要条件 自学 99 汉密尔顿图总结 主要内容1 汉密尔顿路 汉密尔顿回路 汉密尔顿图 半汉密尔顿图的定义 2 汉密尔顿图与半汉密尔顿图的一些必要与充分条件 学习要求1 深刻理解汉密尔顿图的必要条件和充分条件 2 能证明某些图不是汉密尔顿图或证明某些图是汉密尔顿图 3 不要将汉密尔顿图的必要条件当充分条件 也不要将充分条件当必要条件 100 欧拉图与汉密尔顿图总结 欧拉图与汉密尔顿图的判别方法 全体非空连通图 满足定理7 4 1的条件 不满足定理7 4 1的条件 欧拉图 非欧拉图 全体非空连通图 汉密尔顿图 非汉密尔顿图 满足必要条件但不满足任何充分条件 至少满足一个充分条件 不满足某个必要条件 不能根据已知的充分条件或已知的必要条件判别是否是汉密尔顿图 根据给定的图的特点采用特定的方法1 若能找到汉密尔顿回路 则它是汉密尔顿图 2 反证法 假设存在一个汉密尔顿回路 如果导致发生矛盾 则它不是汉密尔顿图 3 暂时无法判别 101 补充 二部图 二部图 G 是图 图G的两个结点子集V1 V2 满足V V1 V2 V1 V2 且图G的每一条边e均具有e vi vj 其中vi V1 vj V2 若V1中任一结点与V2中每一结点均有边相连接 则称二部图为完全二部图 若 V1 r V2 t 则记完全二部图G为Kr t 102 补充 二部图 K3 3 103