离 散 数 学电子科技大学30 30 八月八月 2024 2024数学科学学院数学科学学院第第1111章章 特殊图特殊图2 211.2 11.2 欧拉图欧拉图 11.2.1 11.2.1 欧拉图的引入与定义欧拉图的引入与定义定定义义11.2.1设设G是是无无孤孤立立结结点点的的图图，若若存存在在一一条条通通路路(回回路路)，经经过过图图中中每每边边一一次次且且仅仅一一次次，则则称称此此通通路路(回回路路)为为该该图图的的一一条条欧欧拉拉通通路路(回回路路)(Eulerian Entry/Circuit)。具具有有欧欧拉拉回回路路的的图图称称为为欧欧拉拉图图(Eulerian Graph)。 规定：规定：平凡图为欧拉图。平凡图为欧拉图。 以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。 3 3例例11.2.111.2.1判判断断下下面面的的6 6个个图图中中，是是否否是是欧欧拉拉图图？是是否存在欧拉通路？否存在欧拉通路？ v v3 3v v1 1v v2 2v v4 4(c)(c)v v3 3v v1 1v v2 2v v4 4(a)(a)v v3 3v v1 1v v2 2v v4 4(b)(b)v v3 3v v1 1v v2 2v v4 4(f)(f)v v3 3v v1 1v v2 2v v4 4(d)(d)v v3 3v v1 1v v2 2v v4 4(e)(e)欧拉图欧拉图 欧欧拉拉图图 不是欧拉图，但不是欧拉图，但存在欧拉通路存在欧拉通路 不存在欧不存在欧拉通路拉通路 不不存存在在欧欧拉拉通通路路 不是欧拉图，但存在欧拉通路不是欧拉图，但存在欧拉通路 4 411.2.2-4 11.2.2-4 欧拉图的判定及应用欧拉图的判定及应用定理定理11.2.111.2.1 （含推论（含推论11.2.111.2.1） （1 1）无无向向图图G G = = V, E是是欧欧拉拉图图，当当且且仅仅当当G G是连通的，且仅有零个奇度数结点。是连通的，且仅有零个奇度数结点。（2 2）无无向向图图G G = = V, E有有欧欧拉拉通通路路但但不不是是欧欧拉拉图图，当当且且仅仅当当G G是是连连通通的的，并并且且恰恰有有两两个个奇奇度度数数结结点点。（两两个个奇奇度度数数结结点点必必是是G G中中每每条条欧欧拉拉通通路路的端点）的端点）例如例如5 5定定理理11.2.211.2.2 有有向向图图G G具具有有一一条条欧欧拉拉通通路路，当当且且仅仅当当G G是是连连通通的的，且且除除了了两两个个结结点点以以外外，其其余余结结点点的的入入度度等等于于出出度度，而而这这两两个个例例外外的的结结点点中中，一一个个结结点点的的入入度度比比出出度度大大1 1，另另一个结点的出度比入度大一个结点的出度比入度大1 1。推推论论11.2.211.2.2 有有向向图图G G具具有有一一条条欧欧拉拉回回路路，当当且且仅仅当当G G是是连通的，且所有结点的入度等于出度。连通的，且所有结点的入度等于出度。 例如，对完全图例如，对完全图 Kn，因因 d(Kn) = n-1，故当故当n为奇数时是为奇数时是欧拉图，当欧拉图，当n为偶时不是欧拉图。为偶时不是欧拉图。图图 G 有欧拉通路有欧拉通路G 能能 “一笔画一笔画”G 连通且连通且 G 中度数为奇数的点的个数不超过中度数为奇数的点的个数不超过26 6定义定义11.2.2 设设G = ，eE，如果，如果p(G-e)p(G)称称e为为G的的桥桥(Bridge)或或割边割边(Cut edge)。 显然，显然，所有的悬挂边都是桥所有的悬挂边都是桥。 求一个欧拉图的欧拉回路的求一个欧拉图的欧拉回路的FleuryFleury算法算法的简述：的简述： 从任一点出发按下法来描画一条边不重复的通路，从任一点出发按下法来描画一条边不重复的通路，使在每一步中未描画的子图的割边仅当没有别的边使在每一步中未描画的子图的割边仅当没有别的边可选择时才被描画。可选择时才被描画。7 7例例：例：8 8例例11.2.311.2.3图中的三个图能否一笔画？为什么？图中的三个图能否一笔画？为什么？ v v1 1v v2 2v v3 3v v4 4v v5 5(b(b) )v v1 1v v2 2v v3 3v v4 4(c(c) )v v1 1v v2 2v v3 3v v4 4v v5 5(a(a) )解解 因因为为图图(a)(a)和和(b)(b)中中分分别别有有0 0个个和和2 2个个奇奇度度数数结结点点，所所以以它它们们分分别别是是欧欧拉拉图图和和存存在在欧欧拉拉通通路路，因因此此能能够够一一笔笔画画，并并且且在在(a)(a)中中笔笔能能回回到到出出发发点点，而而(b)(b)中中笔笔不不能能回回到到出出发发点点。图图c c中中有有4 4个个度度数数为为3 3的的结结点点，所所以以不不存存在在欧欧拉拉通通路路，因因此此不不能一笔画。能一笔画。 9 9例例11.2.4 11.2.4 蚂蚁比赛问题蚂蚁比赛问题 甲甲、乙乙两两只只蚂蚂蚁蚁分分别别位位于于图图的的结结点点A A、B B处处，并并设设图图中中的的边边长长度度相相等等。甲甲、乙乙进进行行比比赛赛：从从它它们们所所在在的的结结点点出出发发，走走过过图图中中所所有有边边最最后后到到达达结结点点C C处处。如如果果它它们们的的速速度度相相同同，问问谁谁先先到到达达目目的地？的地？ A(甲)B(乙)C解解 图图中中仅仅有有两两个个度度数数为为奇奇数数的的结结点点B B、C C，因因而而存存在在从从B B到到C C的的欧欧拉拉通通路路，蚂蚂蚁蚁乙乙走走到到C C只只要要走走一一条条欧欧拉拉通通路路，边边数数为为9 9条条，而而蚂蚂蚁蚁甲甲要要想想走走完完所所有有的的边边到到达达C C，至至少少要要先先走走一一条条边边到到达达B B，再再走走一一条条欧欧拉拉通通路路，因因而而它它至至少少要要走走1010条边才能到达条边才能到达C C，所以乙必胜。，所以乙必胜。 101011.3 11.3 哈密顿图哈密顿图 11.2.1 11.2.1 哈密顿图的引入与定义哈密顿图的引入与定义 定定义义11.3.111.3.1 经经过过图图中中每每个个结结点点一一次次且且仅仅一一次次的的通通路路( (回回路路) )称称为为哈哈密密顿顿通通路路( (回回路路) )。存存在在哈哈密密顿顿回回路路的图称为的图称为哈密顿图哈密顿图。 规定：规定：平凡图为哈密顿图平凡图为哈密顿图。 以上定义既适合无向图，又适合有向图。以上定义既适合无向图，又适合有向图。 1111二、二、Hamilton图图例例例例2 2只有哈密尔顿通路，但不是哈密尔顿图只有哈密尔顿通路，但不是哈密尔顿图哈密尔顿图哈密尔顿图无哈密尔顿通路无哈密尔顿通路1212例：例：对下面的图对下面的图v v3 3v v1 1v v2 2v v4 4(a(a) )v v3 3v v1 1v v2 2v v4 4(d(d) )v v3 3v v1 1v v2 2v v4 4(b(b) )v v5 5v v6 6v v7 7v v3 3v v1 1v v2 2v v4 4(e(e) )v v3 3v v1 1v v2 2v v4 4(f(f) )哈密哈密顿图顿图 不存不存在哈在哈密顿密顿通路通路 哈密哈密顿图顿图 不是哈密不是哈密顿图，但顿图，但存在哈密存在哈密顿通路顿通路 不存不存在哈在哈密顿密顿通路通路 131311.3.2 11.3.2 哈密顿图的判定哈密顿图的判定 定定理理11.3.1 设设无无向向图图G = 是是哈哈密密顿顿图图，V1是是V的的任任意意非空子集，则非空子集，则p(G-V1) |V1|其中其中p(G-V1)是从是从G中删除中删除V1后所得到图的连通分支数。后所得到图的连通分支数。证明证明 设设C 是是G 中一条中一条哈密尔顿回路。任取哈密尔顿回路。任取 V 中中非空子集非空子集V ，因因 C 是是G 的的哈密尔顿回路含哈密尔顿回路含G 的所有点，故的所有点，故V 也是子图也是子图 C 的的非空子集。由点不重复的回路的特性知任意删去非空子集。由点不重复的回路的特性知任意删去C 中中 | V | 个个点，最多将点，最多将C 分为分为 | V | “段段” ，即，即 P(C-V) | V | （*） 而而 C 是是 G 的生成子图，又有的生成子图，又有 ： P (G-V) (C-V)所以所以 P (G-V) | V | 1414推推论论11.3.111.3.1设设无无向向图图G G = = V, E中中存存在在哈哈密密顿顿通通路路，则对则对V V的任意非空子集的任意非空子集V V1 1，都有，都有p(G-Vp(G-V1 1) |V) |V1 1| + 1 | + 1 v v3 3v v1 1v v2 2v v4 4v v5 5v v6 6v v7 7v v2 2v v4 4v v1 1v v5 5v v3 3例例 下列图不是哈密顿图，其中下列图不是哈密顿图，其中V1 = 蓝色记号。蓝色记号。1515例例11.3.211.3.2证明图中不存在哈密顿回路。证明图中不存在哈密顿回路。a ab bc cg gi ih h证证明明 在在图图中中，删删除除结结点点子子集集d, d, e, e, f f，得得新新图图，它它的的连连通通分分支支为为4 4个个，由由定定理理11.3.111.3.1知知，该该图图不不是是哈哈密密顿顿图图，因因而而不不会会存存在哈密顿回路。在哈密顿回路。d df fe ea ab bc cg gi ih h1616 可验证彼得森图（下图）不是哈密尔顿图，但可验证彼得森图（下图）不是哈密尔顿图，但满足满足 p(G-V1) |V1|。这表明定理。这表明定理11.3.111.3.1给出的条件给出的条件只是图只是图 G 是哈密尔顿图的是哈密尔顿图的必要条件而不是充分条必要条件而不是充分条件。件。1717例例 设设G = 是具有是具有n个结点的简单无向图。如果个结点的简单无向图。如果对任意两个不相邻的结点对任意两个不相邻的结点u, vV，均有，均有 deg(u)+deg(v)n-1则则G是连通的。是连通的。证明证明 用反证法：用反证法：假设假设G有两个或更多连通分支。设一有两个或更多连通分支。设一个连通分支有个连通分支有n1个结点，另一个连通分支有个结点，另一个连通分支有n2个结点。个结点。这二个连通分支中分别有两个结点这二个连通分支中分别有两个结点v1、v2。显然，。显然，deg(v1)n1-1，deg(v2)n2-1。从而。从而 deg(v1)+deg(v2)n1+n2-2 n-2与已知矛盾，故与已知矛盾，故G是连通的。是连通的。1818定定理理11.3.2 11.3.2 设设G G = = V, E是是具具有有n n个个结结点点的的简简单单无无向向图图。如如果对任意两个不相邻的结点果对任意两个不相邻的结点u, u, vVvV，均有，均有deg(u)+deg(v)n-1deg(u)+deg(v)n-1则则G G中存在哈密顿通路。中存在哈密顿通路。推推论论11.3.211.3.2 设设G G = = V, E是是具具有有n n个个结结点点的的简简单单无无向向图图。如果对任意两个不相邻的结点如果对任意两个不相邻的结点u, u, vVvV，均有，均有deg(u)+deg(v)ndeg(u)+deg(v)n则则G G中存在哈密顿回路。中存在哈密顿回路。推论推论11.3.311.3.3 设设G = G = 是具有是具有n n个结点的简单无向图，个结点的简单无向图，n3n3。如果对任意。如果对任意vVvV，均有，均有deg(vdeg(v) n/2) n/2，则，则G G是哈密是哈密顿图。顿图。1919由由推论推论11.3.211.3.2可知当可知当n3时时 Kn是哈密尔顿图。是哈密尔顿图。故该定理的条件是一个图是哈密尔顿图的充分条故该定理的条件是一个图是哈密尔顿图的充分条件件,但不是必要条件。但不是必要条件。是哈密尔顿图，但不是哈密尔顿图，但不满足满足推论推论11.3.211.3.2的条的条件件2020例例11.3.311.3.3某某地地有有5 5个个风风景景点点，若若每每个个风风景景点点均均有有2 2条条道道路路与与其其他他点点相相通通。问问游游人人可可否否经经过过每每个个风风景景点点恰恰好好一一次次而而游完这游完这5 5处？处？解解 将将5 5个个风风景景点点看看成成是是有有5 5个个结结点点的的无无向向图图，两两风风景景点点间间的的道道路路看看成成是是无无向向图图的的边边，因因为为每每处处均均有有两两条条道道路路与与其其他他结结点点相相通通，故故每每个个结结点点的的度度数数均均为为2 2，从从而而任任意意两两个个不不相相邻邻的的结结点点的的度度数数之之和和等等于于4 4，正正好好为为总总结结点点数数减减1 1。故故此此图图中中存存在在一一条条哈哈密密顿顿通通路路，因因此此游游人人可可以以经经过过每每个个风风景景点点恰恰好好一一次次而而游游完完这这5 5处。处。2121例例11.3.4 11.3.4 判断下图是否存在哈密顿回路。判断下图是否存在哈密顿回路。 5 5e e4 41 1a a2 2b b3 3c cd df fg gh hi ij jk km mn no op p5 54 41 12 23 3f fg gh hi ij jk km mn no op p5 5e e4 41 1a a2 2b b3 3c cd df fg gh hi ij jk km mn no op p解解 方方法法一一：在在图图中中，删删除除结结点点子子集集a, a, b, b, c, c, d, d, ee，得得到到的的图图有有7 7个个连连通通分分支支，由由定定理理11.2.111.2.1知知，该该图图不不是是哈哈密密顿顿图，因而不会存在哈密顿回路。图，因而不会存在哈密顿回路。 方方法法二二：若若图图中中存存在在哈哈密密顿顿回回路路，则则图图中中度度数数为为2 2的的结结点点1 1、2 2、3 3、4 4、5 5 所所关关联联的的边边必必在在回回路路中中，而而这这些些边边已已够够成成一一个个回回路路, ,但但此此回回路路不不是是哈哈密密顿顿回回路路, ,因因而而图图中中不不存存在在哈哈密密顿顿回回路。路。 2222例例11.3.511.3.5证证明明下下图图没没有有哈哈密密顿顿通路。通路。 1(A)1(A)2(B)2(B)8(B)8(B)3(A)3(A)4(B)4(B)5(B)5(B)6(B)6(B)7(A)7(A)证证明明 任任取取一一点点( (如如1)1)用用A A标标记记，所所有有与与1 1邻邻接接的的点点用用B B标标记记。继继续续不不断断地地用用A A标标记记所所有有邻邻接接于于B B的的结结点点，用用B B标标记记所所有有邻邻接接于于A A的的结结点点，直直到到所所有有结点都标记完毕。结点都标记完毕。 如如果果图图中中有有一一条条哈哈密密顿顿通通路路，那那么么它它必必交交替替通通过过结结点点A A和和B B，故故而而标标记记A A的的结结点点与与标标记记B B的的结结点点数数目目或或者者相相同同，或或者者相相差差1 1个个。然然而而图图中中有有3 3个个结结点点标标记记为为A A，5 5个个结结点点标标记记为为B B，它它们们相相差差两两个个，所所以以该该图不存在哈密顿通路。图不存在哈密顿通路。 2323定理定理11.3.311.3.3设设G G = = V, E是是有有n(n2)n(n2)个个结结点点的的一一些些简简单单有有向向图图。如如果果忽忽略略G G中中边边的的方方向向所所得得的的无无向向图图中中含含生生成成子图子图KnKn，则有向图，则有向图G G中存在哈密顿通路。中存在哈密顿通路。v v2 2v v3 3v v1 1v v4 4v v5 5 在在右右图图中中，它它所所对对应应的的无无向向图图中中含含完完全全图图K K5 5，由由定定理理11.3.311.3.3知知，图图中中含含有有哈哈密密顿顿通通路路。事事实实上上，通通路路v v3 3v v5 5v v4 4v v2 2v v1 1为为一一条条哈哈密密顿顿通路。通路。 242411.3.4 11.3.4 哈密顿图的应用哈密顿图的应用 1 1、巡回售货员问题简介、巡回售货员问题简介问题问题：一个一个巡回巡回售货员想访问若干城市（假定各售货员想访问若干城市（假定各城镇之间均有路可通），然后返回。问如何安排城镇之间均有路可通），然后返回。问如何安排路线使其能恰好访问每个城镇一次且走过的总路路线使其能恰好访问每个城镇一次且走过的总路程最短？这个问题称为程最短？这个问题称为巡回巡回售货员问题，它的图售货员问题，它的图论模型为：在赋权完全图论模型为：在赋权完全图G 中求具有最小权中求具有最小权 (最最短短) )的哈密尔顿的哈密尔顿回路回路。2525a ab bc cd de e8 816167 712124 4例例11.3.611.3.6回路的总距离为回路的总距离为4747a ab bc cd de e5 55 58 88 89 99 916167 712124 4一个最短一个最短的哈密尔顿的哈密尔顿回路回路为为: :cdaebccdaebc，总距离为：，总距离为：353526262 2、中国邮路问题、中国邮路问题 一一个个邮邮递递员员送送信信，要要走走完完他他负负责责投投递递的的全全部部街街道道，完完成成任任务务后后回回到到邮邮局局，应应按按怎怎样样的的路路线线走走，他他所走的路程才会最短呢？所走的路程才会最短呢？ 如如果果将将这这个个问问题题抽抽象象成成图图论论的的语语言言，就就是是给给定定一一个个连连通通图图，连连通通图图的的每每条条边边的的权权值值为为对对应应的的街街道道的的长长度度( (距距离离) )，要要在在图图中中求求一一回回路路，使使得得回回路路的的总总权值最小。权值最小。2727中国邮路问题中国邮路问题 若若图图为为欧欧拉拉图图，只只要要求求出出图图中中的的一一条条欧欧拉拉回回路路即即可可。否否则则，邮邮递递员员要要完完成成任任务务就就得得在在某某些些街街道道上上重复走若干次。重复走若干次。 如如果果重重复复走走一一次次，就就加加一一条条平平行行边边，于于是是原原来来对对应应的的图图就就变变成成了了多多重重图图。只只是是要要求求加加进进的的平平行行边边的总权值最小就行了。的总权值最小就行了。 问问题题就就转转化化为为：在在一一个个有有奇奇度度数数结结点点的的赋赋权权连连通通图图中中，增增加加一一些些平平行行边边，使使得得新新图图不不含含奇奇度度数数结结点，并且增加的边的总权值最小。点，并且增加的边的总权值最小。2828解决问题的步骤解决问题的步骤 要解决上述问题，应分下面两个大步骤。要解决上述问题，应分下面两个大步骤。 首首先先，增增加加一一些些边边，使使得得新新图图无无奇奇度度数数结结点点，我我们们称称这一步为这一步为可行方案可行方案(Feasible Scheme)(Feasible Scheme)； 其其次次，调调整整可可行行方方案案，使使其其达达到到增增加加的的边边的的总总权权值值最最小，称这个最后的方案为小，称这个最后的方案为最佳方案最佳方案(Optimal Scheme)(Optimal Scheme)。有下面的结论：一有下面的结论：一个个可行方案可行方案是最优方案中当且仅当是最优方案中当且仅当 I I）图中每条边的重数小于等于图中每条边的重数小于等于2 2； 2 2）图中每个基本回路上平行边的总权值不大于该回路图中每个基本回路上平行边的总权值不大于该回路的权值的一半的权值的一半。2929例例11.3.811.3.8在在下下图图中中，确确定定一一条条v v1 1从从v v1 1到到的的回回路路，使使它它的的权权值值最最小小。事事实实上上，所所确确定定的的回回路路从从任任何何一一个个结结点点出出发发都可以。都可以。 v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 71 12 21 13 34 41 12 22 23 33 33030平行边的总权值为：平行边的总权值为：W(v1,v2)+W(v2,v3)+W(v4,v5)+W(v5,v6)=5 v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 71 12 21 13 34 41 12 22 23 33 32 21 12 21 1 上上图图满满足足I)I)、II)II)两两条条，从从而而是是最最佳佳方方案案，即即图图中中的的任意一条欧拉回路均为邮递员的最佳送信路线。任意一条欧拉回路均为邮递员的最佳送信路线。解：解：313111.4 11.4 偶图偶图 11.4.1-2 11.4.1-2 偶图的定义及判定偶图的定义及判定定定义义11.4.111.4.1 若若无无向向图图G G = = V, E的的结结点点集集V V能能够够划划分分为为两两个个子子集集V V1 1, , V V2 2，满满足足V V1 1VV2 2 = = ，且且V V1 1VV2 2 = = V V，使使得得G G中中任任意意一一条条边边的的两两个个端端点点，一一个个属属于于V V1 1，另另一一个个属属于于V V2 2，则则称称G G为为偶偶图图(Bipartite (Bipartite Graph)Graph)或或二二分分图图( (BigraphBigraph) )。V V1 1和和V V2 2称称为为互互补补结结点点子子集集，偶图通常记为，偶图通常记为G=VG= 。 偶图没有自回路。偶图没有自回路。 平凡图和零图可看成特殊的偶图平凡图和零图可看成特殊的偶图。 3232定定义义11.4.2 偶偶图图G = 中中，若若V1中中的的每每个个结结点点与与V2中中的的每每个个结结点点都都有有且且仅仅有有一一条条边边相相关关联联，则则称称偶偶图图G为为完完全全偶偶图图或或完完全全二二分分图图，记记为为Ki,j，其其中中，i = |V1|，j = |V2|。v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 7v v1 1v v2 2v v3 3v v4 4v v5 5v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6例：下图均为偶图，图均为偶图，其中后其中后3 3个为完全个为完全偶图偶图 。3333定理定理11.4.1 11.4.1 一个无向图是偶图当且仅当它不含长度为奇的一个无向图是偶图当且仅当它不含长度为奇的回路回路。例例偶图偶图不是偶图不是偶图证证明明 必必要要性性：设设图图G是是偶偶图图G = ，令令C = v0v1v2vkv0是是G的一条回路，其长度为的一条回路，其长度为k+1。 不不失失一一般般性性，假假设设v0V1，由由偶偶图图的的定定义义知知，v1V2，v2V1。由此可知，。由此可知，v2iV1且且v2i+1V2。 又又因因为为v0V1，所所以以vkV2，因因而而k为为奇奇数数，故故C的的长长度度为偶数。为偶数。3434充充分分性性：设设G中中每每条条回回路路的的长长度度均均为为偶偶数数，若若G是是连连通通图图，任选任选v0V，定义，定义V的两个子集如下：的两个子集如下：V1 = vi | d(v0, vi)为偶数为偶数，V2 = V-V1。现证明现证明V1中任两结点间无边存在。中任两结点间无边存在。假假若若存存在在一一条条边边(vi, vj)E，其其中中vi, vjV1，则则由由v0到到vi间间的的短短程程线线(长长度度为为偶偶数数)以以及及边边(vi, vj)，再再加加上上vj到到v0间间的的短短程程线线(长度为偶数长度为偶数)所组成的回路的长度为奇数，与假设矛盾。所组成的回路的长度为奇数，与假设矛盾。同理可证同理可证V2中任两结点间无边存在。中任两结点间无边存在。故故G中中每每条条边边的的端端点点分分属属于于V1与与V1，因因此此G是是具具有有互互补补结结点点子集子集V1和和V2的偶图。的偶图。若若G不不连连通通，则则可可对对G的的每每个个连连通通分分支支重重复复上上述述论论证证，也也可可得到同样的结论。得到同样的结论。 3535例：例：v v6 6v v1 1v v4 4v v3 3v v5 5v v2 2v v1 1v v4 4v v2 2v v3 3不是不是偶图偶图 完全偶图完全偶图K K3,33,3 又由定理知至少两个点的树是偶图。又由定理知至少两个点的树是偶图。363611.4.3 11.4.3 匹配匹配 定义定义11.4.2 在偶图在偶图G = 中，中，V1 = v1, v2, , vq，若存在若存在E的子集的子集E = (v1, v1)，(v2, v2)，(vq, vq)，其中，其中v1, v2, , vq 是是V2中的中的q个个不同的结点不同的结点，则称，则称G的子图的子图G = 为从为从V1到到V2的一个的一个完全匹配完全匹配(Complete Matching)，简称，简称匹配匹配。由由定定义义：偶偶图图G = 中中，若若存存在在V1到到V2的的单单射射f，使使得对任意得对任意vV1，都有，都有(v, f(v)E，则存在，则存在V1到到V2的匹配。的匹配。 故由单射的性质知，存在故由单射的性质知，存在V1到到V2的匹配的的匹配的必要条件必要条件是是 |V1| |V2|然而，这个条件并不是充分条件。然而，这个条件并不是充分条件。 3737例例11.4.211.4.2下下面面的的3 3个个偶偶图图哪哪些些存存在在V V1 1到到V V2 2匹匹配配？对对存存在在匹匹配配的的偶图给出一个匹配。偶图给出一个匹配。 (b)(b)v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6V V1 1V V2 2v v1 1v v2 2v v3 3v v5 5v v6 6v v7 7v v8 8(c)(c)v v4 4v v9 9V V1 1V V2 2v v1 1v v2 2v v3 3v v6 6v v7 7v v8 8(a)(a)v v4 4V V1 1V V2 2v v1 1v v2 2v v3 3v v5 5v v6 6v v7 7v v8 8v v4 4v v9 9V V1 1V V2 2不存在不存在匹配匹配 不存在不存在匹配匹配 存在存在匹配匹配 3838霍尔定理霍尔定理定定理理11.4.2 (霍霍尔尔定定理理) 偶偶图图G = 中中存存在在从从V1到到V2的的匹匹配配的的充充分分必必要要条条件件是是V1中中任任意意k个个结结点点至至少少与与V2中中的的k个个结结点点相相邻邻，k = 1, 2, , |V1|。 定定理理11.4.2中中的的条条件件通通常常称称为为相相异异性性条条件件(Diversity Condition)。3939例例不不满满足足相相异异性性条条件件，故没有匹配。故没有匹配。(b)(b)v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6V V1 1V V2 2v v1 1v v2 2v v3 3v v5 5v v6 6v v7 7v v8 8(c)(c)v v4 4v v9 9V V1 1V V2 2满足相异性条件，满足相异性条件，故存在匹配故存在匹配4040定理定理11.4.311.4.3设设G = 是一个偶图。如果满足条件是一个偶图。如果满足条件（1）V1中每个结点至少关联中每个结点至少关联t条边；条边；（2）V2中每个结点至多关联中每个结点至多关联t条边；条边；则则G中存在从中存在从V1到到V2的匹配。其中的匹配。其中t为正整数。为正整数。证证明明 由由条条件件(1)知知，V1中中k个个结结点点至至少少关关联联tk条条边边(1k|V1|)，由由条条件件(2)知知，这这tk条条边边至至少少与与V2中中k个个结结点点相相关关联联，于于是是V1中中的的k个个结结点点至至少少与与V2中中的的k个个结结点点相相邻邻接接，因因而而满满足足相相异异性性条条件件，所所以以G中中存存在从在从V1到到V2的匹配。的匹配。定理定理11.4.311.4.3中的条件通常称为中的条件通常称为t t条件条件(t-(t-Condition)Condition)。判断判断t t条件非常简单，只需要条件非常简单，只需要计算计算V V1 1中结点的最小中结点的最小度数度数和和V V2 2中结点的最大度数中结点的最大度数即可。即可。 414111.4.5 11.4.5 偶图的应用偶图的应用 例例11.4.3 有有n台台计计算算机机和和n个个磁磁盘盘驱驱动动器器。每每台台计计算算机机与与m0个个磁磁盘盘驱驱动动器器兼兼容容，每每个个磁磁盘盘驱驱动动器器与与m台台计计算算机机兼兼容容。能能否否为为每每台台计计算算机机配配置置一一台台与与它它兼容的磁盘驱动器？兼容的磁盘驱动器？解解 用用V1表表示示n台台计计算算机机的的集集合合，V2表表示示n台台磁磁盘盘驱驱动动器器的的集集合合。以以V1，V2为为互互补补结结点点子子集集，以以E = (vi, vj) | viV1, vjV2且且vi与与vj兼兼容容为为边边集集，构构造造偶偶图图。它它显显然然满满足足t条条件件(t = m)，所所以以存存在在匹匹配配，故故能能够够为为每每台台计计算算机机配配置置一一台台与与它它兼兼容容的的磁磁盘盘驱驱动动器。器。 4242例例11.4.411.4.4现现有有三三个个课课外外小小组组：物物理理组组，化化学学组组和和生生物物组组，有有五个学生五个学生s1,s2,s3,s4,s5。（1）已已知知s1,s2为为物物理理组组成成员员；s1,s3,s4为为化化学学组组成成员员；s3,s4,s5为生物组成员。为生物组成员。（2）已已知知s1为为物物理理组组成成员员；s2,s3,s4为为化化学学组组成成员员；s2,s3,s4,s5为生物组成员。为生物组成员。（3）已已知知s1即即为为物物理理组组成成员员，又又为为化化学学组组成成员员；s2,s3,s4,s5为生物组成员。为生物组成员。在在以以上上三三种种情情况况的的每每一一种种情情况况下下，在在s1,s2,s3,s4, s5中中选三位组长，不兼职，问能否办到？选三位组长，不兼职，问能否办到？4343解解用用c1,c2,c3分别表示物理组、化学组和生物组。分别表示物理组、化学组和生物组。V1=c1,c2,c3，V2=s1,s2,s3,s4,s5以以V1，V2为互补结点子集，以为互补结点子集，以 E=(ci,sj)|ciV1, sjV2且且ci中有成员中有成员sj为边集，构造偶图。为边集，构造偶图。(1)(1)c c1 1c c2 2c c3 3s s1 1s s2 2s s3 3s s4 4s s5 5V V1 1V V2 2(2)(2)c c1 1c c2 2c c3 3s s1 1s s2 2s s3 3s s4 4s s5 5V V1 1V V2 2(3)(3)c c1 1c c2 2c c3 3s s1 1s s2 2s s3 3s s4 4s s5 5V V1 1V V2 2(1)(1)c c1 1c c2 2c c3 3s s1 1s s2 2s s3 3s s4 4s s5 5V V1 1V V2 2(2)(2)c c1 1c c2 2c c3 3s s1 1s s2 2s s3 3s s4 4s s5 5V V1 1V V2 2不存在不存在匹配匹配 444411.5 11.5 平面图平面图 11.5.1 11.5.1 平面图的定义平面图的定义 4545 问题：问题：假定有三个仓库假定有三个仓库 x1，x2，x3 和三个车站和三个车站 y1，y2，y3。为了便于货物运输，准备在仓库与车站间修筑铁路，如图为了便于货物运输，准备在仓库与车站间修筑铁路，如图(a) 所示所示, 其中边代表铁路。问是否存在一种使铁路不交叉的路其中边代表铁路。问是否存在一种使铁路不交叉的路线设计方案，以避免修建立交桥。线设计方案，以避免修建立交桥。 问题的解答问题的解答但如果在但如果在 x3 与与y1 之间也要修一条铁路，则之间也要修一条铁路，则可验证满足要求的方案不存在。可验证满足要求的方案不存在。 x1 x2 x3y1 y2 y3(a) x1 x2 x3 y1 y2 y3?4646定义定义11.5.111.5.1如如果果能能能能把把一一个个无无向向图图G的的所所有有结结点点和和边边画画在在平平面面上上，使使得得任任何何两两边边除除公公共共结结点点外外没没有有其其他他交交叉叉点点，则则称称G为为平平面面图图(Plane Graph)，否否则则称称G为为非非平平面面图图(Nonplanar Graph)。 当当且且仅仅当当一一个个图图的的每每个个连连通通分分支支都都是是平平面面图图时时，这个图是平面图。这个图是平面图。v v1 1v v2 2v v3 3v v4 4v v5 5v v1 1v v2 2v v3 3v v4 4v v5 5平面图的平面表示平面图的平面表示 4747平面图平面图非平面图非平面图=非平面图非平面图 =4848平面图平面图=平面图平面图494911.5.3 11.5.3 欧拉公式欧拉公式 定义定义11.5.2 在平面图在平面图G的一个平面表示中，的一个平面表示中，u由由边边所所包包围围的的其其内内部部不不包包含含图图的的结结点点和和边边的的区区域域，称为，称为G的一个的一个面面(Surface)，u包包围围该该面面的的诸诸边边所所构构成成的的回回路路称称为为这这个个面面的的边边界界(Bound)，u面面r的的边边界界的的长长度度称称为为该该面面的的次次数数(Degree)，记记为为D(r)。u区区域域面面积积有有限限的的面面称称为为有有限限面面(Finite Surface)，区域区域面积无限面积无限的面称为的面称为无限面无限面(Infinite Surface)。u平面图有且仅有一个无限面平面图有且仅有一个无限面。5050例例 有有5个面：个面：f1，f2，f3，f4，f5 （ f5 为外部面）为外部面）图不连通，其外部面的次数为图不连通，其外部面的次数为5f 1 f 2 f 3f 5f 4D(f1) =1D(f2) =2D(f3) = 3D(f4) = 6D(f5)= 10相加为相加为22，正好是，正好是边数边数11的的2倍倍5151例例11.5.211.5.2考察下图所示平面图的面、边界和次数。考察下图所示平面图的面、边界和次数。 a ab bd de ec ch hi ij jk kr r0 0r r1 1r r2 2r r3 3解解 平面图把平面分成平面图把平面分成4 4个面：个面：r r0 0，边界为，边界为abdehecaabdeheca，D(rD(r0 0)=7)=7r r1 1，边界为，边界为abcaabca，D(rD(r1 1)=3)=3r r2 2，边界为，边界为becbbecb，D(rD(r2 2)=9)=9r r3 3，边界为，边界为bdebbdeb，D(rD(r3 3)=3)=3r r1 1、r r2 2和和r r3 3是是有有限限面面，r r0 0是是无无限限面。面。 注意：注意：对于平面图的不同平面表示，虽然面的数目对于平面图的不同平面表示，虽然面的数目相同，但各面的边界和次数会不同。相同，但各面的边界和次数会不同。 i ij ja ab bd de ec ch hk kr r0 0r r1 1r r2 2r r3 35252定理定理11.5.1 11.5.1 平面图中所有面的次数之和等于边数平面图中所有面的次数之和等于边数 的二倍。的二倍。证证明明 因因任任何何一一条条边边，或或者者是是两两个个面面边边界界的的公公共共边边，或或者者是是在在一一个个面面中中作作为为边边界界被被重重复复计计算算两两次次，故故平平面面图图所所有有面面的的次数之和等于其边数的二倍。次数之和等于其边数的二倍。 1750年年，欧欧拉拉发发现现，任任何何一一个个凸凸多多面面体体，若若有有n个个顶顶点点、m条条棱棱和和r个个面面，则则有有n-m+r = 2。这这个个公公式式可可以以推推广广到到平平面面图上来，称之为图上来，称之为欧拉公式。欧拉公式。定定理理11.5.2（欧欧拉拉公公式式）设设G = 是是连连通通平平面面图，若它有图，若它有n个结点、个结点、m条边和条边和r个面，则有个面，则有 n-m+r = 2 （*）5353证明证明 对对 r 用归纳法。用归纳法。设设 r = k 时，（时，（*）式成立。）式成立。 当当r =1时时 ，G 无无基本回路基本回路又连通，从而是树，有又连通，从而是树，有 n =m+1于是于是 n -m+r =（m+1）- m + 1= 2 当当 r = k+1 时，此时时，此时 G 至少两个面，从而有至少两个面，从而有圈圈 C。删去删去 C 中一条边，记所得之图为中一条边，记所得之图为 G 。并并设设 G 的点数、边数和面数依次为的点数、边数和面数依次为 n , m 和和 r , 易知易知 G 仍连通，但只有仍连通，但只有 k 个面，由归纳假设有个面，由归纳假设有 5454同时同时 n = n ， m = m - 1，r = r - 1代入（代入（*）式得）式得 n -（m-1）+（r -1）= 2即即 n m + r =2 n - m + r = 2 （*）推推论论11.5.2 设设G是是一一个个(n, m)简简单单连连通通平平面面图图，若若每每个面的次数至少为个面的次数至少为k(k3)，则有，则有 5555推论推论11.5.1 设设G是一个是一个(n,m)简单连通平面图，若简单连通平面图，若m 1，则有，则有 m3n-6证证明明 设设G有有k个个面面，因因为为G是是简简单单图图，所所以以G的的每每个个面面至至少少由由3条边围成，在式条边围成，在式（11.5.2) 中取中取 k=3 即得结论即得结论.证明证明 设设G共有共有r个面，各面的次数之和为个面，各面的次数之和为T，由条件可知由条件可知 kr T = 2m（由定理由定理11.5.1）故故 r 2m/k代入欧拉公式代入欧拉公式 n m + r =2 n m + 2m/k 2从而有从而有m k(n-2)/ (k-2) （11.5.2) 5656例例 证明完全图证明完全图K5是非平面图。是非平面图。证证明明 因因为为K5是是简简单单连连通通图图，n=5，m=10，若若 K5 是是平平面面图图，则应满足推论则应满足推论11.5.1: m3n -6。代入不等式。代入不等式 得得 1035 6 = 9矛盾，所以矛盾，所以 K5 是是非非平面图。平面图。例例 证明证明K3,3是非平面图。是非平面图。证明证明 因因 K 3,3 没有长小于没有长小于4的的基本回路基本回路，所以若，所以若 K 3,3 是平面图是平面图，则对其相应的平面图中每个面的次数至少为，则对其相应的平面图中每个面的次数至少为4。由推论。由推论11.5.211.5.2，K 3,3 应满足应满足 k = 4 的不等式的不等式（11.5.2)11.5.2)即即m （ -2）=2 - 4244- -nn而而K 3,3中中m = 9， n = 6，代入上式得代入上式得: 926-4 = 8矛盾，所以矛盾，所以 K 3,3 是是非非平面图。平面图。 5757说明说明 1 1。一一个个简简单单连连通通图图，若若不不满满足足 m3n-6m3n-6，则则一一定定是非平面图是非平面图。 2 2。一个简单连通图，若每个面的次数至少为一个简单连通图，若每个面的次数至少为k(k3)k(k3)，若，若不满足不满足 m k(n-2)/ (k-2），则一定，则一定是非是非平面图。平面图。 3 3。对对1 1。和。和2 2。满足满足不等式的简单连通图不等式的简单连通图未必是未必是平面图。平面图。585811.5.4 11.5.4 库拉托夫斯基定理库拉托夫斯基定理 定定理理11.5.3(11.5.3(库库拉拉托托夫夫斯斯基基定定理理) ) 一一个个图图是是平平面面图图的的充充分分必必要要条条件件是是它它的的任任何何子子图图都都不不可可能能收收缩缩为为K K5 5或或K K3,33,3。我们将我们将K K5 5和和K K3,33,3称为称为库拉托夫斯基图库拉托夫斯基图。例例 (1) 右右图G1是不可平面是不可平面图。因。因为由由G1通通过收收缩边12，34，56，78，09 可得到可得到图K5。 1 2 03 94 8 5 6 7 G15959(2) 彼得森图彼得森图(下图（下图（a）)通过收缩图中通过收缩图中红边红边而得到而得到的图是（的图是（b），故彼得森图是不可平面图。），故彼得森图是不可平面图。(a) (b) v v1 1v v2 2v v3 3v v4 4v v5 5u u1 1u u2 2u u3 3u u4 4u u5 5v v1 1w w2 2w w3 3w w4 4w w5 5u u1 1方法二：方法二：找到子找到子图，收缩边图，收缩边( (v vi i,u,ui i) )，用，用w wi i代代替，替，i=2,3,4,5i=2,3,4,5，得得到图即为到图即为K K3,33,3。 606011.6 11.6 本章总结（本章总结（主要知识点汇集）主要知识点汇集）基基本本概概念念：欧欧拉拉通通路路、欧欧拉拉回回路路、欧欧拉拉图图、桥桥、哈哈密密顿顿通通路路、哈哈密密顿顿回回路路、哈哈密密顿顿图图、偶偶图图、匹匹配配、平平面面图图、对偶图、图的着色等；对偶图、图的着色等；判判定定方方法法：欧欧拉拉图图和和偶偶图图都都有有简简单单的的方方法法，但但哈哈密密顿顿图图和平面图的判定却很困难；和平面图的判定却很困难；在在哈哈密密顿顿图图、平平面面图图、偶偶图图的的匹匹配配中中都都分分别别有有仅仅是是必必要要条条件件的的定定理理，可可用用来来判判断断一一个个图图不不是是哈哈密密尔尔图图、是是非非平平面图、无匹配；面图、无匹配；在在哈哈密密顿顿图图与与匹匹配配中中，也也有有充充分分条条件件，可可用用来来判判断断该该图图是哈密顿图，有匹配；是哈密顿图，有匹配；平面图中欧拉公式；平面图中欧拉公式；特特殊殊的的应应用用：一一笔笔画画问问题题、计计算算机机鼓鼓轮轮设设计计、巡巡回回售售货货员问题、中国邮路问题等。员问题、中国邮路问题等。6161主要知识点汇集主要知识点汇集在在哈哈密密顿顿图图与与匹匹配配中中，也也有有充充分分条条件件，可可用用来来判判断断该该图图是哈密顿图，有匹配；是哈密顿图，有匹配；平面图中欧拉公式；平面图中欧拉公式；特特殊殊的的应应用用：一一笔笔画画问问题题、计计算算机机鼓鼓轮轮设设计计、巡巡回回售售货货员问题、中国邮路问题等。员问题、中国邮路问题等。