第十章图论模型优秀课件.ppt

《第十章图论模型优秀课件.ppt》由会员分享，可在线阅读，更多相关《第十章图论模型优秀课件.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章图论模型第1页，本讲稿共35页1 哥尼斯堡七桥问题哥尼斯堡七桥问题ADCB哥尼斯堡是哥尼斯堡是18世纪东普鲁士的一世纪东普鲁士的一个城市，流经市区有条河名叫普个城市，流经市区有条河名叫普雷格尔河，河中有两岛，把市区雷格尔河，河中有两岛，把市区分成四快陆地分成四快陆地A、B、C、D，陆，陆地间有七座桥相通。地间有七座桥相通。问：一个散步者能否从某地出发，问：一个散步者能否从某地出发，走遍七座桥，且每座桥只走一次，走遍七座桥，且每座桥只走一次，最后回到出发地？一个人能否经最后回到出发地？一个人能否经过每座桥恰一次而走遍七座桥？过每座桥恰一次而走遍七座桥？ABCD抽象：陆地抽象：陆地 点；桥点

2、；桥 线线欧拉判别准则：要能从图的某个顶点出发，经欧拉判别准则：要能从图的某个顶点出发，经图的每条线正好一次，最后回到原来顶点，当图的每条线正好一次，最后回到原来顶点，当且仅当且仅当 这个图连成一片，且每个顶点都有偶数这个图连成一片，且每个顶点都有偶数条线和它连接。七桥问题无解。条线和它连接。七桥问题无解。第2页，本讲稿共35页2 图论的基本概念图论的基本概念一、图的概念一、图的概念一个图一个图G指的是仅由一些点和一些点的指的是仅由一些点和一些点的连线组成的图形。连线组成的图形。顶点（结点）：顶点（结点）：边：边：e7V5V4V3V2V1e6e5e4e3e2e1(a)V5V4V3V2V1a6a

3、5a3a4a2a1(b)图中的小圆点图中的小圆点顶点之间的连线顶点之间的连线无向图：无向图：图中的边没有方向的图图中的边没有方向的图有向图：有向图：图中的边有方向的图图中的边有方向的图1.图的定义：图的定义：图的集合表示：图的集合表示：设设V表示所有顶点组成的集合，表示所有顶点组成的集合，E表示所有表示所有边组成的集合，边组成的集合，G表示图，那么表示图，那么G=。第3页，本讲稿共35页e7V5V4V3V2V1e6e5e4e3e2e1(a)V5V4V3V2V1a6a5a3a4a2a1(b)对于无向图对于无向图G，连接顶点，连接顶点Vi,Vj 的边记为（的边记为（Vi,Vj)如：在图如：在图(a

4、)中，边中，边 e2=(V2,V3)V=v1,v2,v3,v4,v5 ,E=e1,e2,e3,e4,e5,e6,e7对于有向图对于有向图G，一条连接从，一条连接从Vi 指向指向 Vj 的边的边记为记为,如在图如在图(b)中，边中，边a4=V=v1,v2,v3,v4,v5 ,E=a1,a2,a3,a4,a5,a62.关联关联设设G=为无向图，为无向图，e=(u,v)E,则称则称u,v是是e的端点，也称的端点，也称u,v是相邻的，称是相邻的，称e是点是点u（及点（及点v）的关联边。）的关联边。3.环环若图若图G 中某边中某边e 的两个端点相同的两个端点相同,则则称称e为环为环4.多重边多重边在图在

5、图G 中，若两个顶点之间有多中，若两个顶点之间有多于一条边，称这些边为多重边于一条边，称这些边为多重边第4页，本讲稿共35页5.简单图简单图7.度（次）度（次）无环，无多重边的图无环，无多重边的图6.多重图多重图无环，但允许有多重边的图无环，但允许有多重边的图设设G=为一无向图，为一无向图，v V,则称以则称以v 为端点的边的为端点的边的个数为个数为v 的度（次）数，简称度（次），记为的度（次）数，简称度（次），记为d(v)推论推论定理定理1设图设图G=为无向图或有向图，则为无向图或有向图，则G 中所有点的度数之中所有点的度数之和是边数之和的和是边数之和的2 倍。倍。任何图中，度数为奇数的顶点

6、个数为偶数。任何图中，度数为奇数的顶点个数为偶数。二、子图、完全图、补图二、子图、完全图、补图1.子图子图设设G=,G =是两个图，若是两个图，若V V,E E,则称则称G 是是G 的子图，的子图，G 是是G 的母图的母图,记为记为G G。若若G G,且且G G,（即（即V V或或E E），则称），则称G 是是G 的真子图。的真子图。若若G G,且且V=V,则称则称G 是是G 的生成子图。的生成子图。第5页，本讲稿共35页2.导出图导出图设设G=,若若V V,且且V，E=(u,v)|u,v V,(u,v)E，则称，则称G=是是G 的由的由V导出的导出子图导出的导出子图。设设G=,若若E E,且

7、且E ，V=v V|v是是E中某边的端点中某边的端点，则称则称G=是是G 的由的由E导出的导出子图导出的导出子图。(1)v1v4v3v2e1e2e3e4e5(2)v1v2e4e5(3)v1v4v3v2e1e3e43.完全图完全图设设G=是是n 阶无向简单图（阶无向简单图（|V|=n，顶点数为，顶点数为n），），若若G中任何顶点都与其余的中任何顶点都与其余的n-1个顶点相邻，则称个顶点相邻，则称G为为n阶无向完全阶无向完全图，记为图，记为Kn(2)和和(3)是是(1)的子图的子图(3)是是(1)的生成子图的生成子图(2)是是v1,v2导出子图导出子图(3)是是e1,e3,e4导出子图导出子图第6

8、页，本讲稿共35页设设D=是是n 阶有向简单图，若对任意的顶点阶有向简单图，若对任意的顶点u,v V，既有有向，既有有向边边，又有有向边，又有有向边，则称则称D为为n阶有向完全图。阶有向完全图。4.补图补图设设G=是是n 阶无向简单图阶无向简单图，以，以V为顶点集，以所为顶点集，以所有能使有能使G成为完全图成为完全图Kn 的添加边组成的集合为边集的图，称为的添加边组成的集合为边集的图，称为G相相对于完全图对于完全图Kn的补图，简称的补图，简称G的补图。的补图。(1)(2)(3)(4)(1)与与(2)互补互补(3)与与(4)互补互补第7页，本讲稿共35页三、通路、回路、图的连通性三、通路、回路、

9、图的连通性1.通路、回路：给定一个图通路、回路：给定一个图G=，设，设G 中顶点和边的交错序列中顶点和边的交错序列T=v0,e1,v1,e2,v2,ek,vk，如果满足，如果满足ei=(vi1,vi),(i=1,2,k),则称则称T为为G 的一条联结的一条联结v0和和vk的通路，记为的通路，记为T=v0,v1,v2,vk；v0和和vk称为此称为此通路的起点和终点；通路的起点和终点；T 中边数中边数k称为称为T 的长度；若的长度；若v0=vk,此时称通此时称通路为回路。路为回路。定理定理2：在一个：在一个n 阶图中，若从顶点阶图中，若从顶点vi 到到vj 存在通路，则从存在通路，则从vi 到到v

10、j 存在长度小于等于存在长度小于等于n 1的通路。的通路。定理定理3：在一个：在一个n 阶图中，若存在顶点阶图中，若存在顶点vi 到自身的回路，则从到自身的回路，则从vi 到到自身自身 存在长度小于等于存在长度小于等于n 的回路。的回路。2.连通：在一个无向图连通：在一个无向图G 中，若从顶点中，若从顶点vi 到到vj 存在通路（当然从存在通路（当然从vj 到到vi 也存在通路），则称也存在通路），则称vi 与与vj 是连通的。规定是连通的。规定vi到自身总是连通。到自身总是连通。3.连通图：若无向图连通图：若无向图G 是平凡图，或是平凡图，或G中任意两点都连通，则称中任意两点都连通，则称G

11、是连通的，否则，称是连通的，否则，称G 是不连通的。是不连通的。第8页，本讲稿共35页四、两个特殊的图四、两个特殊的图1.二部图（二分图）二部图（二分图）若能将无向图若能将无向图G=的顶点集的顶点集V划分成两个子集划分成两个子集V1和和V2（V1 V2=,)，使得，使得G 中任何一条边的两个端点一个属于中任何一条边的两个端点一个属于V1，另一个属于，另一个属于V2,则称则称G为二部图（也称为偶图）。为二部图（也称为偶图）。V1,V2称为互补顶点子集，此称为互补顶点子集，此时可将时可将G记成记成G=。若若V1中任何一顶点与中任何一顶点与V2中每个顶点均有且仅有一条边相关联，则称中每个顶点均有且仅

12、有一条边相关联，则称G为完全二部图（或完全偶图），若为完全二部图（或完全偶图），若|V1|=n,|V2|=m,则可记则可记G为为Kn,m(2)(1)定理：一个无向图定理：一个无向图G=是二部图当是二部图当且仅当且仅当G 中无奇数长中无奇数长度的回路。度的回路。图图(1)是是K2,3图图(2)是是K3,3第9页，本讲稿共35页2.欧拉图欧拉图经过图中每条边一次且仅一次并且行遍图中每个顶点的通路（回路）经过图中每条边一次且仅一次并且行遍图中每个顶点的通路（回路）称为欧拉通路或欧拉迹（欧拉回路或欧拉闭迹）。存在欧拉回路的称为欧拉通路或欧拉迹（欧拉回路或欧拉闭迹）。存在欧拉回路的图称为欧拉图。图称为欧

13、拉图。定理定理5：无向图：无向图G 具有欧拉通路，当且仅当具有欧拉通路，当且仅当G 是连通的且仅有零个是连通的且仅有零个或两个奇数度顶点。若无奇数度顶点，则通路为回路；若有两个奇或两个奇数度顶点。若无奇数度顶点，则通路为回路；若有两个奇数度顶点，则它们是每条欧拉通路的端点。数度顶点，则它们是每条欧拉通路的端点。推论：无向图推论：无向图G 是欧拉图（具有欧拉回路）当且仅当是欧拉图（具有欧拉回路）当且仅当G 是连通的，是连通的，且且G 中无奇数度顶点。中无奇数度顶点。(1)(3)(4)(1)是欧拉图是欧拉图(2)存在欧拉通路存在欧拉通路(3)存在存在欧拉回路欧拉回路(4)既无欧拉回路，既无欧拉回路

14、，也无欧拉通路也无欧拉通路(2)第10页，本讲稿共35页五、图的矩阵表示五、图的矩阵表示1.无向图的关联矩阵无向图的关联矩阵设无向图设无向图G=，V=v1,v2,vn,E=e1,e2,em，令，令mij为顶点为顶点vi与边与边ej的关的关联数，则称（联数，则称（mij）nxm为为G 的关联矩阵，的关联矩阵，记为记为M(G)。v3v2v1v4e4e3e2e1e52.有向图的关联矩阵有向图的关联矩阵设有向图设有向图D=，D无环存在无环存在V=v1,v2,vn,E=e1,e2,em，令，令mij=1,vi为为ej的起点的起点0,vi与与ej不关联不关联1,vi为为ej的终的终点点则称（则称（mij）

15、nxm为为D 的关联矩阵，记为的关联矩阵，记为M(D)。e5v4v3v2v1e4e2e1e3第11页，本讲稿共35页3.有向图的邻接矩阵有向图的邻接矩阵设有向图设有向图D=，V=v1,v2,vn,|E|=m，令，令aij为为vi邻接到邻接到vj的边的条数，称（的边的条数，称（aij）nxn为为D的邻接矩阵，记为的邻接矩阵，记为A(D)。4.有向图的可达矩阵有向图的可达矩阵若从若从vi 到到vj 存在通路，则称存在通路，则称vi 可达可达vj设有向图设有向图D=，V=v1,v2,vn,令令Pij=1,vi可达可达vj0,否则否则称（称（pij）nxn为为D的可达矩阵，记为的可达矩阵，记为P(D)

16、。v4v3v2v1第12页，本讲稿共35页第13页，本讲稿共35页第14页，本讲稿共35页ABCDgdcbafe七桥问题中第一个问题是图七桥问题中第一个问题是图G中是否存在欧拉中是否存在欧拉通路；第二个问题是图通路；第二个问题是图G中是否是欧拉图中是否是欧拉图d(A)=3,d(B)=5,d(C)=3,d(D)=3,问题问题1和问题和问题2均无解均无解Euler将问题一般化将问题一般化：给定任意一河道图，任：给定任意一河道图，任意多座桥，可否判断每座桥恰好走一次？这意多座桥，可否判断每座桥恰好走一次？这便是一笔画问题。除起点和终点外，交点的便是一笔画问题。除起点和终点外，交点的度数是偶数。度数是

17、偶数。1.连接奇数座桥的陆地仅有一个或超过两个，不能实现一笔画。连接奇数座桥的陆地仅有一个或超过两个，不能实现一笔画。2.连接奇数座桥的陆地仅有两个时，则从两者任意一陆地出发，可连接奇数座桥的陆地仅有两个时，则从两者任意一陆地出发，可以实现一笔画而停在另一陆地。以实现一笔画而停在另一陆地。3.每个陆地都连接偶数个桥时，则从任意地出发都能实现一笔画，每个陆地都连接偶数个桥时，则从任意地出发都能实现一笔画，而回到出发地。而回到出发地。第15页，本讲稿共35页第16页，本讲稿共35页问问题：题：在在6人的集会上，总能找到或者人的集会上，总能找到或者3人互相认识，或者人互相认识，或者3人谁也人谁也不认

18、识谁。假定认识是相互的。不认识谁。假定认识是相互的。u6u5u4u3u2u1图图Gu6u5u4u3u2u1补图补图G命命题题对于一个任意的具有对于一个任意的具有6个顶点个顶点的简单图的简单图G，要么这个图本身，要么这个图本身，要么它的补图要么它的补图G中含有一个三中含有一个三角形（即角形（即3个顶点的完全图个顶点的完全图K3)考虑考虑u1与其余与其余5个顶点相邻情况：个顶点相邻情况：u1与其余与其余5个顶点的每个顶点或者在个顶点的每个顶点或者在G中相邻，或者在补图中相邻，或者在补图G中相邻。因中相邻。因此与此与G中或中或G中至少三个顶点相邻。中至少三个顶点相邻。不妨设不妨设u1在在G中与中与u

19、2,u3,u4相邻相邻(1)若若u2,u3,u4中有中有2点在点在G 中相邻，得证中相邻，得证(2)若若u2,u3,u4在在G 中均不相邻，则它们中均不相邻，则它们在在G中彼此相邻，得证中彼此相邻，得证第17页，本讲稿共35页第18页，本讲稿共35页问问题题一个摆渡人一个摆渡人F希望用一条小船把一只狼希望用一条小船把一只狼W，一头羊，一头羊G 和一蓝白和一蓝白菜菜C 从河的左岸渡到右岸，而小船只能容纳从河的左岸渡到右岸，而小船只能容纳F、W、G、C 中的中的两个，决不能两个，决不能 在无人看守的情况下，留下狼和羊在一起，羊和在无人看守的情况下，留下狼和羊在一起，羊和菜在一起，问怎样渡河才能将狼

20、、羊、白菜都运过去？菜在一起，问怎样渡河才能将狼、羊、白菜都运过去？首先对两岸上允许的组合加以分类首先对两岸上允许的组合加以分类，如，如(FWG/C)等，用点表示允许等，用点表示允许状态，也可用四维向量状态，也可用四维向量(1,1,1,0)来表示允许状态。两个状态可以互来表示允许状态。两个状态可以互相转化时，用这两点间连线表示。相转化时，用这两点间连线表示。(FWGC/0)(FWG/C)(FWC/G)(FGC/W)(FG/WC)(WC/FG)(W/FGC)(G/FWC)(C/FWG)(0/FWGC)第19页，本讲稿共35页(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)

21、(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(1,1,1,0)(1,1,1,1)(1,0,1,1)(1,1,0,1)(0,0,0,1)(0,0,0,0)(1,0,1,0)(0,1,0,0)(0,0,1,0)思考题：用图论的方法解决商人过河问题思考题：用图论的方法解决商人过河问题第20页，本讲稿共35页第21页，本讲稿共35页v5v4v3v2v1e7e6e5e4e3e2e1消防设施的安置问题：消防设施的安置问题：若干条街道构成小区，一个非常简化若干条街道构成小区，一个非常简化的小区如图所示。的小区如图所示。e1,e

22、2,e7表示街道，表示街道，v1,v2,v5,表示交叉路口。计划在某些表示交叉路口。计划在某些路口安置消防设施，只有与路口直接路口安置消防设施，只有与路口直接相连的街道才能使用它们。为使所有相连的街道才能使用它们。为使所有街道必要时都有消防设施可用，在哪街道必要时都有消防设施可用，在哪些路口安置设施才最节省？些路口安置设施才最节省？每个路口安置设施显然可以达到目的，但这是不必要的。每个路口安置设施显然可以达到目的，但这是不必要的。去掉去掉v5,在在v1,v2,v3,v4各安置一个也可达到目的。各安置一个也可达到目的。再去掉再去掉v1,在在v2,v3,v4各安置一个仍然可达到目的。但不能再去掉了

23、。各安置一个仍然可达到目的。但不能再去掉了。另外，在另外，在v1,v3,v5 或在或在v2,v4,v5各安置一个也可以达到目的，但只在各安置一个也可以达到目的，但只在2个路口安置消防设施是不行的。个路口安置消防设施是不行的。最小覆盖问题最小覆盖问题第22页，本讲稿共35页覆盖：若图覆盖：若图G 的每条边都至少有一个端点在顶点集的每条边都至少有一个端点在顶点集V的一个子集的一个子集K中，则中，则K称为称为G 的覆盖。的覆盖。如：如：(v2,v3,v4,v5),(v2,v3,v4,),(v1,v3,v5),(v2,v4,v5),均为均为G 的覆盖的覆盖最小覆盖：含顶点个数最少的覆盖称为最小覆盖（不

24、一定唯一）。最小覆盖：含顶点个数最少的覆盖称为最小覆盖（不一定唯一）。最小覆盖中顶点的个数称为覆盖数，记为最小覆盖中顶点的个数称为覆盖数，记为 。覆盖与图的关联矩阵的关系覆盖与图的关联矩阵的关系顶点集顶点集V 的子集的子集K 是图是图G 的一个覆盖，当且仅当的一个覆盖，当且仅当G 的关联矩阵中的关联矩阵中K的各顶点所对应的行内，每列至少存在一个元素的各顶点所对应的行内，每列至少存在一个元素1。v5v4v3v2v1e7e6e5e4e3e2e1第23页，本讲稿共35页（1）从上到下，观察）从上到下，观察R的每一行，的每一行，取出现取出现1最多的一行，如最多的一行，如v3 行，令行，令v3 K，划去

25、，划去v3 行及行及v3 行元素行元素1所所在的列在的列e2,e3,e6 得得（2）从）从R1 中取中取v5 K，划去，划去v5行行及及v5 行元素行元素1所在的列所在的列e5,e7 得得（3）继续上述方法，取）继续上述方法，取v1 K，得，得R3=0最小覆盖最小覆盖K=(v1,v3,v5)第24页，本讲稿共35页监狱看守问题：监狱看守问题：v5v4v3v2v1e7e6e5e4e3e2e1一座监狱的几间牢室有道路相连，不一座监狱的几间牢室有道路相连，不妨设其示意图为右图。妨设其示意图为右图。v1,v2,v5,表表示牢室，示牢室，e1,e2,e7 表示道路，监狱表示道路，监狱看守要设在通过道路能

26、直接监视所有看守要设在通过道路能直接监视所有牢室的地方，如果看守不得走动，那牢室的地方，如果看守不得走动，那么他们应呆在某些牢室（即路口）所在地方，问至少需要几名看守么他们应呆在某些牢室（即路口）所在地方，问至少需要几名看守才能完成监视任务？才能完成监视任务？在每间牢室设一个看守是多余的，在在每间牢室设一个看守是多余的，在v1,v3,v5 各设一看守即可同时监各设一看守即可同时监视视v2,v4。还可以把。还可以把v3 去掉，只留下去掉，只留下v1,v5。当然在。当然在v2,v3或或v4,v5 处设处设看守亦可，但只在一处设看守不行，所有至少需要看守亦可，但只在一处设看守不行，所有至少需要2名看

27、守。名看守。用图解决问题就是用若干顶点通过邻边控制所有顶点。（控制集）用图解决问题就是用若干顶点通过邻边控制所有顶点。（控制集）控制集：若图控制集：若图G 的每个顶点或直接属于顶点集的每个顶点或直接属于顶点集V的某个子集的某个子集C，或，或者它的邻边的另一端点属于者它的邻边的另一端点属于C，则称，则称C 为为G 的控制集。的控制集。第25页，本讲稿共35页最小控制集：含顶点个数最少的控制集称为最小控制集。最小控制最小控制集：含顶点个数最少的控制集称为最小控制集。最小控制集中顶点个数称为控制数，记为集中顶点个数称为控制数，记为。如：如：(v1,v3,v5),(v1,v5),(v2,v3,)均为均

28、为G 的控制集，的控制集，(v1,v5),(v2,v3,)为为G 的最小控制集。的最小控制集。邻接矩阵表示的是顶点之间的关系，可用邻接矩阵确定最小控制集邻接矩阵表示的是顶点之间的关系，可用邻接矩阵确定最小控制集取取v2 C,得得取取v3 C,得得A2=0 最小控制集为（最小控制集为（v2,v3）第26页，本讲稿共35页第27页，本讲稿共35页问题：一家公司生产若干种化学制品，其中某些制品是互不相容的，问题：一家公司生产若干种化学制品，其中某些制品是互不相容的，如果存放在一起，则可能发生化学反映，引起危险，因此公司必须如果存放在一起，则可能发生化学反映，引起危险，因此公司必须把仓库分成相互隔离的

29、若干区域，以便把不相容的制品分开存放。把仓库分成相互隔离的若干区域，以便把不相容的制品分开存放。问至少要划分多少小区？怎样存放才能安全？问至少要划分多少小区？怎样存放才能安全？gdebafc设有设有7中化学制品，并用中化学制品，并用a,b,c,d,f,g表表示，其中不能存放在一起的是：示，其中不能存放在一起的是：(a,b),(a,d),(b,c),(b,e),(b,g),(c,d),(c,e),(c,f),(d,e),(d,g),(e,f),(f,g)。图表示：顶点代表这图表示：顶点代表这7种制品，把不能存放在一起的制品连线（边）种制品，把不能存放在一起的制品连线（边）顶点染色：给各顶点染色，

30、使相邻顶点的颜色互不相同，并且为了顶点染色：给各顶点染色，使相邻顶点的颜色互不相同，并且为了使所使用颜色的数目最少，每种颜色应给尽可能多的顶点涂色。为使所使用颜色的数目最少，每种颜色应给尽可能多的顶点涂色。为此，在顶点集此，在顶点集V 中，要找出那些不包含相邻顶点的子集，并要求这中，要找出那些不包含相邻顶点的子集，并要求这种子集内顶点数目尽量多，这就可以用同种颜色涂染尽可能多顶点种子集内顶点数目尽量多，这就可以用同种颜色涂染尽可能多顶点第28页，本讲稿共35页独立集：不包含相邻顶点的独立集：不包含相邻顶点的 V 的子集的子集S 称为独立集称为独立集极大独立集：若在独立集极大独立集：若在独立集S

31、 中添加任何顶点都会使中添加任何顶点都会使S 不再是独立集不再是独立集例如例如:(a),(a,e),(a,e,g)是独立集；是独立集；(a,e,g)是极大独立集，是极大独立集，(a,f),(b,d,f)也也是极大独立集。顶点染色问题的关键是找极大独立集。是极大独立集。顶点染色问题的关键是找极大独立集。独立集与覆盖的关系：若独立集与覆盖的关系：若S是独立集，则是独立集，则S的补集是覆盖，反之亦然的补集是覆盖，反之亦然极小覆盖极小覆盖K：如果从覆盖：如果从覆盖K中去掉任何顶点都会使中去掉任何顶点都会使K不再是覆盖。不再是覆盖。极大独立集与极小覆盖的关系：若极大独立集与极小覆盖的关系：若S是极大独立

32、集，则是极大独立集，则S的补集是极的补集是极小覆盖，反之亦然。小覆盖，反之亦然。极小覆盖的性质：当且仅当对于每个顶点极小覆盖的性质：当且仅当对于每个顶点v，或者，或者v 属于属于K，或者，或者v 的所有相邻顶点属于的所有相邻顶点属于K，并且二者不能同时成立时，并且二者不能同时成立时，K是极小覆盖。是极小覆盖。极小覆盖的逻辑算法：对于每个顶点极小覆盖的逻辑算法：对于每个顶点v，选择，选择v，或选择，或选择v 的所有相的所有相邻顶点（两者不能同时选择），利用逻辑代数中的邻顶点（两者不能同时选择），利用逻辑代数中的“和和”（+）运）运算和算和“积积”（）运算（相当于集合运算中的）运算（相当于集合运算

33、中的“或或”（）、）、“交交”()）第29页，本讲稿共35页gdebafc(a+bd)(b+aceg)(c+bdef)(d+aceg)(e+bcdf)(f+ceg)(g+bdf)化简为化简为aceg+bcdeg+bdef+bcdf取全部极小覆盖的补集，得极大独立集：取全部极小覆盖的补集，得极大独立集：(b,d,f),(a,f),(a,c,g),(a,e,g)包含数目最多的极大独立集称为最大独立集包含数目最多的极大独立集称为最大独立集，其数目称为独立数，其数目称为独立数任取一最大独立集，如：任取一最大独立集，如：S1(b,d,f),给它染上第给它染上第1 种颜色。种颜色。再找出再找出GS1=（a

34、,c,e,g)的全部独立集的全部独立集,其最小覆盖为其最小覆盖为(c)和和(e),从而最大独立从而最大独立集为集为(a,c,g),(a,e,g),取取S2=(a,c,g)，给，给S2染上第染上第2 种颜色。种颜色。GS1S2只剩下只剩下e，于，于是给是给e 染第染第3 种颜色。种颜色。geca可以用可以用3 种颜色分别给种颜色分别给(b,d,f),(a,c,g)和和(e)涂染，是颜色数目最少的顶点染色涂染，是颜色数目最少的顶点染色方案。方案。至少把仓库划分至少把仓库划分3 个小区，将个小区，将b,d,f 制品，制品，a,c,g 制品与制品与e分开存放。分开存放。第30页，本讲稿共35页第31页

35、，本讲稿共35页v9v8v7v6v5v4v3v2v1944445526433问题：假定右图是某邮递员负责的街问题：假定右图是某邮递员负责的街道图，道图，v1为邮局，各边上的数为距离为邮局，各边上的数为距离（单位：公里），邮递员送信时，要（单位：公里），邮递员送信时，要走完他负责投递的全部街道，完成任走完他负责投递的全部街道，完成任务后回到邮局，问邮递员按照怎样的务后回到邮局，问邮递员按照怎样的路线走，所走的路程最短？路线走，所走的路程最短？解：如果图没有奇数度顶点（是欧拉图），可以从邮局出发，走过解：如果图没有奇数度顶点（是欧拉图），可以从邮局出发，走过每条街道一次，且仅一次，最后回到邮局，这

36、样所走的路程最短。每条街道一次，且仅一次，最后回到邮局，这样所走的路程最短。如果有奇数度顶点，就必须在某些街道重复走一次或多次。如果有奇数度顶点，就必须在某些街道重复走一次或多次。等价问题：在一个有奇数度顶点的图中，要求增加一些重复边，并等价问题：在一个有奇数度顶点的图中，要求增加一些重复边，并且重复边的总权数最小。且重复边的总权数最小。需要解决的问题：需要解决的问题：1.如何增加新边（重复边），使新图不含奇数度如何增加新边（重复边），使新图不含奇数度顶点，简称可行方案；顶点，简称可行方案；2.怎样判别可行方案是否为最优方案？若不怎样判别可行方案是否为最优方案？若不是最优方案，如何调整这个方案

37、？是最优方案，如何调整这个方案？第32页，本讲稿共35页v9v8v7v6v5v4v3v2v19444455264331.第一可行方案的确定：第一可行方案的确定：每对奇数度顶点间必有一通路，把通每对奇数度顶点间必有一通路，把通路上所有边作为重复边加到图中，便路上所有边作为重复边加到图中，便给出第一个可行方案。给出第一个可行方案。记记wij为边为边(vi,vj)的权（即距离），则重的权（即距离），则重复边的总权为复边的总权为2w12+w23+w34+2w45+2w56+w67+w78+2w18=512.调整可行方案，使重复边总长度下降调整可行方案，使重复边总长度下降v9v8v7v6v5v4v3v2

38、v1944445526433若边若边(vi,vj)上有两条或两条以上重复边，上有两条或两条以上重复边，从中去掉偶数条，就能得到一个总长度从中去掉偶数条，就能得到一个总长度下降的可行方案。右图总长度降为下降的可行方案。右图总长度降为21把图中某回路上重复边去掉，而给原把图中某回路上重复边去掉，而给原来没有重复边加上重复边，图中仍没来没有重复边加上重复边，图中仍没有奇数度顶点，是可行方案。有奇数度顶点，是可行方案。第33页，本讲稿共35页如果某回路上重复边的总权大于这个回路的总权的一半，则按上如果某回路上重复边的总权大于这个回路的总权的一半，则按上述方法做一次调整，会得到一个总长度下降的可行方案。

39、述方法做一次调整，会得到一个总长度下降的可行方案。最优方案的判别：可行方案是最优最优方案的判别：可行方案是最优方案的充分必要条件是：方案的充分必要条件是：(a)图中的图中的每条边上最多有一条重复边；每条边上最多有一条重复边；(b)每每一回路上重复边总权不大于该回路一回路上重复边总权不大于该回路总权的一半。总权的一半。v9v8v7v6v5v4v3v2v1944445526433回路回路(v1,v2,v9,v6,v7,v8,v1)中，重复中，重复边总权为边总权为13，而回路总权为，而回路总权为24，进行调整。进行调整。v9v8v7v6v5v4v3v2v1944445526433经检查，得最优方案，其重复经检查，得最优方案，其重复边总权为边总权为15。第34页，本讲稿共35页 思考题思考题:商人们怎样安全过河商人们怎样安全过河问题(智力游戏)3名商人 3名随从河小船(至多2人)随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?第35页，本讲稿共35页