11-1-aolm-离散数学.ppt

《11-1-aolm-离散数学.ppt》由会员分享，可在线阅读，更多相关《11-1-aolm-离散数学.ppt（42页珍藏版）》请在金锄头文库上搜索。

1、第1篇 数理逻辑 第2篇 集合论 第3篇 代数结构 第4篇 图论,第4篇 图论,模型化是数学中的一个基本概念，它处于所有的数学应用之心脏，也处于某些最抽象的纯数学核心之中。 R. C. Buck,第4篇 图论,第10章 图 第11章 特殊图 第12章 树 命题逻辑和谓词逻辑是数理逻辑的基础部分,第11章 特殊图 11.1 欧拉图与Hamilton图 11.2 二分图与匹配 11.3 平面图、对偶图与地图着色 11.4 网络及最大流问题 11.5 典型例题解析,第4篇 图论,第11章 特殊图,数学知识有三个不同于其它知识的主要特征：其一是数学知识比其它知识更清晰地使其结果具有真理性；其二是数学知

2、识乃是获得其它正确知识的必经的第一步；其三是数学知识的获得并不依赖于其它知识。 Schubert H.,介绍几种特殊图的概念、性质和应用。这些图包括： 欧拉图、Hamilton图、 平面图和对偶图、二分图（偶图）、 超图以及树等。,第11章 特殊图,11.1 欧拉图与Hamilton图,11.1.1 欧拉图,18 世纪 30 年代，普鲁士的哥尼斯堡（现在俄罗斯的列宁格勒），欧洲数学家们要求遍历哥尼斯堡七桥中每座桥恰好一次后回到出发点，哥尼斯堡地图如下图所示。其中 A, B, C, D 代表四块陆地，七座桥分别将 A, B, C, D 连接在一起。,对于哥尼斯堡七桥问题，大数学家欧拉最先意识到哥

3、尼斯堡七桥问题的求解与 A, B, C, D 的大小和它们之间的长度无关，从而将问题求解转换为对多重图的遍历，即：找到一条遍历多重图每条边恰好一次的回路。若需要，回路可以重复访问结点。,左图作为哥尼斯堡七桥问题的图模型，对其进行了抽象，其中结点 AD 分别对应四块陆地，而边则分别对应了连接四块陆地的七桥。,哥尼斯堡七桥的图模型,定义11.1 给定无孤立点图 G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路。具有欧拉回路的图称为欧拉图。,欧拉在问题求解过程中注意到，哥尼斯堡多重图中每个结点的度数为奇数。因此，哥尼斯堡多重

4、图中的任何结点都不能作为起始结点，因为回路都是从某个结点出发回到该结点，然后再从该结点出发再返回，如此循环往复，那么每个起始结点的度数都应是偶数。类似的，哥尼斯堡多重图中的任何结点都不能作为中间结点，因为回路都是进入某个结点后离开，然后再进入另一个结点离开，如此循坏往复，那么这些中间结点的度数也应该是偶数。 由此，欧拉得出了存在欧拉回路的一个必要条件，后又被证明该条件同时也是充分的，如此得出了下面的定理。,定理11.1（欧拉路的充要条件） 无向图 G 具有一条欧拉路，当且仅当 G 是连通的，且有零个或两个奇数度结点。 证明：先证明必要性，再证明充分性。 （1）必要性：设 G 具有欧拉路，即有点

5、边序列v0e1v1e2v2eiviei1ekvk，其中结点可能重复出现，但边不重复，因为欧拉路经过图 G 中每一个结点，故图 G 必连通的。 对任意一个不是端点的结点 vi，在一个欧拉路中每当 vi 出现一次，必关联两条边，故虽然 vi 可重复出现，但 deg(vi) 必是偶数。 对于端点，若 v0vk，则 d(v0) 为偶数，即G 中无奇数度结点。 若端点 v0 与 vk 不同，则 d(v0) 为奇数，d(vk )为奇数，G 中就有两个奇数度结点。,（2）充分性： 若图 G 连通，有零个或两个奇数度结点，构造一条欧拉路如下： 若有两个奇数度结点，则从其中的一个结点开始构造一条迹，即从 v0

6、出发关联 e1 “进入” v1，若 deg(v1) 为偶数，则必由 v1 再经过 e2 进入 v2，如此进行下去，每次仅取一次。由于 G 是连通的，故必可到达另一奇数度结点停下，得到一条迹 L1：v0e1v1e2v2eiviei1ekvk。若 G 中没有奇数度结点，则从任一结点 v0 出发，用上述的方法必可回到结点 v0，得到上述一条闭迹 L1。, 若 L1 通过了 G 的所有边，则 L1 就是欧拉路。 若 G 中去掉 L1 后得到子图 G，则 G中每一点的度数为偶数，因原图是连通的，故 L1 与 G至少有一个结点 vi 重合，在 G中由 vi 出发重复 的方法，得到闭迹 L2。 当 L1 与

7、 L2 组合在一起，如果恰是 G，则即得欧拉路，否则重复 可得到闭迹 L3，以此类推直到得到一条经过图 G 中所有边的欧拉路。,推论11.1（欧拉回路的充要条件） 无向图 G 具有一条欧拉回路，当且仅当 G 是连通的，并且所有结点度数为偶数。 由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的答案，因为有四个结点的度数皆为奇数，故欧拉路必不存在。 该定理可以作为欧拉回路的判定定理。 欧拉路和欧拉回路的概念可以推广到有向图。,定义11.2 给定有向图 G，通过每边一次且仅一次的一条单向路(回路)，称作单向欧拉路（回路）。 定理11.2 有向图 G 具有一条单向欧拉回路，当且仅

8、当是连通的，且每个结点的入度等于出度。一个有向图 G 具有单向欧拉路，当且仅当是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大 1。另一个结点的入度比出度小 1。,这个定理的证明可以看作是无向图的欧拉路的推广，因为对于有向图的任意一个结点来说，如果入度与出度相等，则该结点的总度数为偶数，若入度和出度之差为 1 时，其总度数为奇数。因此定理的证明与定理11.2 相似。 欧拉图广泛应用于有关合适路线的设计问题。代表性的中国邮递员问题将在 11.1.3 小节中介绍，这里举一个清洁车路线的设计问题，简单说明欧拉图的应用。,No【例11.1】设某城市的街道布局如

9、下图所示。每条边代表一条特定街道的一段街区，每个结点代表街区间的交点。扫雪车车库位于结点 d。证明存在一条路线使得扫雪车清扫每个街区恰好一次且清扫完最后一个街区正好返回车库。为这个扫雪车找出完成任务的路线。,清洁车的清洁路线图,解：首先，注意到图是连通的，并且每个结点的度数为偶数，那么，根据定理11.2 可以推知出图中存在欧拉回路。而图是扫雪街区布局的模型图， 所以可以推出存在一条使得扫雪车经过每个街区恰好一次最后回到车库的路线。,为了找到这条合适的路线，我们分两步： （1）构造回路：从结点 d 开始，构造第 1 条回路 ，然后构造出回路 ，最后构造回路 。 （2）组合：将构造的回路按照下列方

10、式进行组合：用回路 来代替 中的结点 c 得到 然后用回路 C3 代替结点 b 得到回路： 这是扫雪车完成任务的一种可能路线。,11.1.2 哈密顿（Hamilton） 图,欧拉图要求遍历图中每边仅一次并回到起点，与此类似的是遍历图中的每个结点仅一次并回到起点的问题。 这个问题的起源与一个游戏密切相关。十九世纪中期，世界上第一个给出复数的代数表示而非几何表示的爱尔兰著名数学家 William Hamilton 爵士发明了一种名为 Icosian 的游戏，亦称为周游世界游戏。该游戏要求在一个十二面体上移动木栓。十二面体由 20 个结点（体的尖角）、30 条边（面的边界）和 12 个面组成，每个面

11、的形状为五边形，如下图所示。在游戏中，每个结点代表一个著名的城市。游戏的目标是寻找一条旅行世界的路线，使得访问每个城市恰好一次后，再返回到起点城市。在构造路线时，要求沿着连接城市的边来移动木栓。 后来，这类问题就以 Hamilton 的名字来命名了。,十二面体图,十二面体由 20 个结点（体的尖角）、30 条边（面的边界）和 12 个面组成,* 定义11.3 给定图 G，若存在一条路经过图中的每一个结点恰好一次，这条路称作 Hamilton 路。若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作 Hamilton 回路。具有 Hamilton 回路的图称为 Hamilton 图。,*

12、定理11.3 （ Hamilton 回路的必要条件）若图 G(V, E) 具有 Hamilton 回路，则对于结点集 V 的每一个非空子集 S 均有 W(GS) 成立。其中 W(GS) 是 GS 中连通分支数。 证明：设 C 是 G 的一条 Hamilton 回路，则对于 V 的任何一个非空子集 S 在 C 中删去 S 中任一结点 a1，则 Ca1 是连通非回路，若删去 S 中的另一个结点 a2，则 W(C a1a2)2，由归纳法得知 W(CS) 同时 CS 是 GS 的一个生成子图，因而 W(GS)W(CS) 所以W(GS),No 定理11.3 作为图的性质，可以用来判定某些图是非 Hami

13、lton 图。右图是非 Hamilton 图，因为若取 Sv1, v4，则 GS 中有三个分图，故 G 不是 Hamilton 图。,一个非 Hamilton 图,v5,v7,v1,v2,v3,v6,v7,v4,No 定理11.3 并不总是有效的，右图所示的著名彼得森图虽然满足 W(GS) ，但它不是Hamilton图。,彼得森图,关于图中没有 Hamilton 路的判别目前没有有效的方法，下面介绍一个说明性的例子。,不存在 Hamilton 路,在上图 (a) 中，用 A 标记任意结点（比如：结点1），所有与该结点（结点1）邻接的结点均标记为 B，继续不断地用 A 标记所有邻接于标记为 B

14、的结点、用 B 标记所有邻接于标记为 A 的结点，直到所有结点标记完毕，如上图 (b) 所示。如果在图中有一条 Hamilton 路，那么它必须交替通过标记为 A 的结点和标记为 B 的结点。而图中所示有 9 个标记 A 的结点和 7 个标记 B 的结点，所以不可能存在 Hamilton 路。,注意，如果标记过程中遇到相邻结点出现相同标记时，可以在此相邻结点对应的边上增加一个结点，标记为相异标记。 虽然 Hamilton 回路在问题形式与欧拉回路颇为相似，但对于 Hamilton 回路还没有象定理11.3 那样有效的充要条件判定准则。在此仅给出 Hamilton 图的充分条件定理。,*定理11

15、.4（Hamilton 路的充分条件） 设 G 具有 n 个结点的简单图，如果 G 中每一对结点的度数之和大于等于 n1，则在 G 中存在一条 Hamilton 路。证明： 首先证明 G 是连通的。若 G 有两个或更多互不连通的分图，设一个分图有 n1 个结点，任取一个结点 v1，设另一个分图有 n2 个结点，任取一个结点 v2，因为 d(v1)n11，d(v2)n21，故 d(v1) d(v2) n1 n22n1，这表明与题设矛盾，故 G 必连通。, 其次，从一条边出发构成一条路，证明它是Hamilton路。 设在 G 中有 p1 条边的路，pn，它的结点序列为 v1, v2, , vp。

16、如果有 v1 或 vp 邻接于不在这条路上的一个结点，我们可立即扩展这条路，使它包含这一个结点，从而得到 p 条边的路。 否则，v1 和 vp 都只能邻接于这条路上的结点，证明在这种情况下，存在一条回路包含结点 v1,v2, , vp。,Hamilton路的扩充,若 v1 邻接于 vp，则 v1, v2, , vp，v1 即为所求的回路。 假设与 v1 邻接的结点集是 ，这里 2l, m, , tp1，如果是邻接于 vl1,vm1, , vj1, , vt1 中之一，譬如说 vj1，如上图(a)所示，v1v2v3vj1vpvp1vjv1 是所求的包含结点的回路 v1, v2, , vp。 如果 vp 不邻接于 vl1, vm1, , vj1, , vt1中任一个，则 vp 至少邻接于 pk1 个结点，deg(vp)pk1，deg(v1)k，