《第十章 图论模型.ppt》由会员分享，可在线阅读，更多相关《第十章 图论模型.ppt（35页珍藏版）》请在金锄头文库上搜索。
1、第十章,图论模型,1 哥尼斯堡七桥问题,哥尼斯堡是18世纪东普鲁士的一个城市，流经市区有条河名叫普雷格尔河，河中有两岛，把市区分成四快陆地A、B、C、D，陆地间有七座桥相通。,2 图论的基本概念,一、图的概念,一个图G指的是仅由一些点和一些点的连线组成的图形。,顶点（结点）：,边：,图中的小圆点,顶点之间的连线,无向图：,图中的边没有方向的图,有向图：,图中的边有方向的图,1.图的定义：,图的集合表示：,设V表示所有顶点组成的集合，E表示所有边组成的集合，G表示图，那么G= 。,对于无向图G ，连接顶点Vi , Vj 的边记为（Vi ,Vj),如：在图(a)中，边 e2=(V2,V3),V=v
2、1, 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, a6,2.关联,设G=为无向图，e=(u,v)E,则称u,v是e的端点，也称u,v是相邻的，称e是点u（及点v）的关联边。,3.环,若图G 中某边e 的两个端点相同,则称e为环,4.多重边,在图G 中，若两个顶点之间有多于一条边，称这些边为多重边,5.简单图,7.度（次）,无环，无多重边的图,6.多重图,无环，但允许有多重边的图,设G
3、=为一无向图，vV,则称以v 为端点的边的个数为v 的度（次）数，简称度（次），记为d(v),推论,定理1,设图G=为无向图或有向图，则G 中所有点的度数之和是边数之和的2 倍。,任何图中，度数为奇数的顶点个数为偶数。,二、子图、完全图、补图,1.子图,设G =,G =是两个图，若VV,E E,则称G 是G 的子图，G 是G 的母图,记为G G 。,若G G,且G G,（即VV或EE），则称G 是G 的真子图。,若G G,且V=V,则称G 是G 的生成子图。,2.导出图,设G =,若V V,且V，E=(u,v)|u,vV,(u,v)E，则称G =是G 的由V导出的导出子图。,设G =,若E E
4、,且E ，V=v V|v是E中某边的端点，则称G =是G 的由E导出的导出子图。,3.完全图,(2)和(3)是(1)的子图,(3)是(1)的生成子图,(2)是v1,v2导出子图,(3)是e1,e3,e4导出子图,设D =是n 阶有向简单图，若对任意的顶点u,v V，既有有向边，又有有向边，则称D为n阶有向完全图。,4.补图,(1)与(2)互补,(3)与(4)互补,三、通路、回路、图的连通性,四、两个特殊的图,1.二部图（二分图）,若能将无向图G =的顶点集V划分成两个子集V1和V2（V1V2 =,)，使得G 中任何一条边的两个端点一个属于V1，另一个属于V2,则称G为二部图（也称为偶图）。V1
5、,V2称为互补顶点子集，此时可将G记成G =。,若V1中任何一顶点与V2中每个顶点均有且仅有一条边相关联，则称G为完全二部图（或完全偶图），若|V1|=n, |V2|=m ,则可记G为Kn,m,定理：一个无向图G =是二部图当且仅当G 中无奇数长度的回路。,图(1)是K2,3,图(2)是K3,3,2.欧拉图,经过图中每条边一次且仅一次并且行遍图中每个顶点的通路（回路）称为欧拉通路或欧拉迹（欧拉回路或欧拉闭迹）。存在欧拉回路的图称为欧拉图。,推论：无向图G 是欧拉图（具有欧拉回路）当且仅当G 是连通的，且G 中无奇数度顶点。,(1)是欧拉图,(2)存在欧拉通路,(3)存在欧拉回路,(4)既无欧拉
6、回路，也无欧拉通路,五、图的矩阵表示,1. 无向图的关联矩阵,设无向图G = ，V=v1,v2, ,vn, E=e1,e2, ,em ，令mij为顶点vi与边ej的关联数，则称（mij）nxm为G 的关联矩阵，记为M(G) 。,2. 有向图的关联矩阵,设有向图D = ，D无环存在V=v1,v2, ,vn,E=e1,e2, ,em ，令,则称（mij）nxm为D 的关联矩阵，记为M(D) 。,3. 有向图的邻接矩阵,设有向图D = ，V=v1,v2, ,vn,|E|=m ，令aij为vi邻接到vj的边的条数，称（aij）nxn为D的邻接矩阵，记为A(D) 。,4. 有向图的可达矩阵,若从vi 到
7、vj 存在通路，则称vi 可达vj,图论法建模举例,七桥问题的 图论解法,七桥问题中第一个问题是图G中是否存在欧拉通路；第二个问题是图G中是否是欧拉图,d(A)=3, d(B)=5 , d(C)=3 ,d(D)=3 ,问题1和问题2均无解,Euler将问题一般化 ：给定任意一河道图，任意多座桥，可否判断每座桥恰好走一次？这便是一笔画问题。除起点和终点外，交点的度数是偶数。,1.连接奇数座桥的陆地仅有一个或超过两个，不能实现一笔画。,2.连接奇数座桥的陆地仅有两个时，则从两者任意一陆地出发，可以实现一笔画而停在另一陆地。,3.每个陆地都连接偶数个桥时，则从任意地出发都能实现一笔画，而回到出发地。
8、,相识问题,问题：,在6人的集会上，总能找到或者3人互相认识，或者3人谁也不认识谁。假定认识是相互的。,命题,对于一个任意的具有6个顶点的简单图G ，要么这个图本身，要么它的补图G中含有一个三角形（即3个顶点的完全图K3),考虑u1与其余5个顶点相邻情况： u1与其余5个顶点的每个顶点或者在G中相邻，或者在补图G中相邻。因此与G中或G中至少三个顶点相邻。,不妨设u1在G中与u2,u3,u4相邻,(1)若u2,u3,u4中有2点在G 中相邻，得证,(2)若u2,u3,u4在G 中均不相邻，则它们在G中彼此相邻，得证,人、狼、羊、菜,渡河问题,问题,一个摆渡人F希望用一条小船把一只狼W ，一头羊G
9、 和一蓝白菜C 从河的左岸渡到右岸，而小船只能容纳F、W、G、C 中的两个，决不能 在无人看守的情况下，留下狼和羊在一起，羊和菜在一起，问怎样渡河才能将狼、羊、白菜都运过去？,首先对两岸上允许的组合加以分类 ，如(FWG/C)等，用点表示允许状态，也可用四维向量(1,1,1,0)来表示允许状态。两个状态可以互相转化时，用这两点间连线表示。,消防设施与 监狱看守问题,最小覆盖与 最小控制集问题,消防设施的安置问题：,若干条街道构成小区，一个非常简化的小区如图所示。e1,e2, ,e7表示街道，v1,v2,v5,表示交叉路口。计划在某些路口安置消防设施，只有与路口直接相连的街道才能使用它们。为使所
10、有街道必要时都有消防设施可用，在哪些路口安置设施才最节省？,每个路口安置设施显然可以达到目的，但这是不必要的。,去掉v5 ,在v1,v2,v3,v4各安置一个也可达到目的。,再去掉v1 ,在v2,v3,v4各安置一个仍然可达到目的。但不能再去掉了。,另外，在v1,v3,v5 或在v2,v4,v5各安置一个也可以达到目的，但只在2个路口安置消防设施是不行的。,最小覆盖问题,如： (v2,v3,v4,v5) , (v2,v3,v4,) , (v1,v3,v5) , (v2,v4,v5) ,均为G 的覆盖,覆盖与图的关联矩阵的关系,顶点集V 的子集K 是图G 的一个覆盖，当且仅当G 的关联矩阵中K的
11、各顶点所对应的行内，每列至少存在一个元素1 。,（1）从上到下，观察R的每一行，取出现1最多的一行，如v3 行，令v3K ，划去v3 行及v3 行元素1所在的列e2 , e3 , e6 得,（2）从R1 中取v5 K ，划去v5行及v5 行元素1所在的列e5 , e7 得,（3）继续上述方法，取v1 K ，得R3=0,最小覆盖K=(v1 , v3 , v5),监狱看守问题：,在每间牢室设一个看守是多余的，在v1,v3,v5 各设一看守即可同时监视v2,v4 。还可以把v3 去掉，只留下v1,v5 。当然在v2,v3或v4 ,v5 处设看守亦可，但只在一处设看守不行，所有至少需要2名看守。,用图
12、解决问题就是用若干顶点通过邻边控制所有顶点。（控制集）,如： (v1,v3,v5) , (v1,v5) , (v2,v3,) 均为G 的控制集， (v1,v5) , (v2,v3,) 为G 的最小控制集。,邻接矩阵表示的是顶点之间的关系，可用邻接矩阵确定最小控制集,取v2 C, 得,取v3 C, 得A2=0,最小控制集为（ v2 , v3 ）,染色问题,设有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)。,例如 : (a),(a
13、,e),(a,e,g)是独立集；(a,e,g)是极大独立集，(a,f),(b,d,f)也是极大独立集。顶点染色问题的关键是找极大独立集。,(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,c,e,g) 的全部独立集,其最小覆盖为(c) 和(e) ,从而
14、最大独立集为(a,c,g), (a,e,g) ,取S2=(a,c,g)，给S2染上第2 种颜色。GS1S2只剩下e ，于是给e 染第3 种颜色。,可以用3 种颜色分别给(b,d,f),(a,c,g)和(e) 涂染，是颜色数目最少的顶点染色方案。,至少把仓库划分3 个小区，将b,d,f 制品，a,c,g 制品与e分开存放。,中国邮递员问题,1.第一可行方案的确定：,每对奇数度顶点间必有一通路，把通路上所有边作为重复边加到图中，便给出第一个可行方案。,记wij为边(vi,vj)的权（即距离），则重复边的总权为,2w12+w23+w34+2w45 +2w56+w67+w78+2w18=51,2.调整
15、可行方案，使重复边总长度下降,若边(vi,vj)上有两条或两条以上重复边，从中去掉偶数条，就能得到一个总长度下降的可行方案。右图总长度降为21,把图中某回路上重复边去掉，而给原来没有重复边加上重复边，图中仍没有奇数度顶点，是可行方案。,如果某回路上重复边的总权大于这个回路的总权的一半，则按上述方法做一次调整，会得到一个总长度下降的可行方案。,最优方案的判别：可行方案是最优方案的充分必要条件是：(a)图中的每条边上最多有一条重复边；(b)每一回路上重复边总权不大于该回路总权的一半。,回路(v1,v2,v9,v6,v7,v8,v1)中，重复边总权为13，而回路总权为24，进行调整。,经检查，得最优方案，其重复边总权为15。,思考题:商人们怎样安全过河,问题(智力游戏),随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.,但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?,
