ch10图的基本概念.ppt

《ch10图的基本概念.ppt》由会员分享，可在线阅读，更多相关《ch10图的基本概念.ppt（118页珍藏版）》请在三一文库上搜索。

1、第10章 图的基本概念,如何找到物流运输的最优路径？ 如何找到最优的网络通信线路？ 如果你想周游全国所有城市，如何设计旅游线路？ 化学化合物分析：结构是否相同？ 程序结构度量：程序是否结构相似？ 如何为考试分配教室，使得资源利用率最优？ 如何安排工作流程而达到最高效率？ 如何设计为众多的电视台频道分配最优方案？ 如何设计通信编码以提高信息传输效率？ 操作系统中,如何调度进程而使得系统效率最优？,如何设计集成电路线路布局而达到最优效率？ 如何设计计算机鼓轮？ 七枚同重量硬币与一枚较轻的伪币，使用天平秤多少次就能找出伪币？ 如何设计下棋程序？ n-皇后问题 最少用几种颜色就能将世界地图都着色？ 如

2、何使箱子尽可能装满物体？ 一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。那么他怎样才能把三者都运过河呢？,研究主题 旅行商问题：TSP问题 中国邮路问题 地图着色问题：四色定理 最短路径问题 网络流 匹配 组合计数,主要内容,1) 图的基本术语； 2) 结点的度，子图，完全图； 3) 图的连通性； 4) 图的运算，图的矩阵表示及其性质； 5) 图的同构； 6) 欧拉图与哈密尔顿图的性质及其应用。,10.1 图论概述 图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾名思义是运用数学手段研究图的性质的理论

3、，但这里的图不是平面坐标系中的函数，而是由一些点和连接这些点的线组成的结构。图论是有许多应用的古老学科，也一直以来都是一个热门学科，它已经被广泛应用于计算机科学、化学、运筹学、心理学等很多领域。,10.2 图与图模型 例10.2 时间安排问题。某大学计算机学院的某教研组共有10名教师，他们分别参加7个班级的讨论课，每个班级可能同时需要多位教师参加，有的教师可能需要参加多个班级的讨论，每个班级必须单独开展讨论课，则如何安排才使得所有班级在最短时间段内完成讨论课？参加各个班级讨论课的教师情况如下（ci为班级编号，数字1-10为教师编号）： c1=1，2，3，c2=1，3，4，5，c3=2，5，6，

4、7，c4=2，6，7，c5=4，7，8，9，c6=8，9，10，c7=1，3，9，10。,10.2 图与图模型,这样，一位教师如果给多个班级都授课，则在讨论课时间安排方面则不能冲突，如教师1不能同时参加班级c1与班级c2的讨论课。这种情况可以用下图直观地表示。 在上图中，共用了7个小圆圈来表示班级，圆圈之间的线段表示存在同一个教师参加该二班级的讨论课，这样就不能安排该二班级同时开展讨论课。显然，这就给上述问题构建了一个直观的图的模型。,10.2 图与图模型 定义10.1 图G包括一个非空的对象的集合V与有限的两个对象构成的V的无序对构成的集合E，前者称为的结点集，后者称为边集。 令V=v1,v

5、2,vn是包含n个结点的集合，其m条边的集合E=e1,e2,em，其中，每一条边都是集合V的二元子集，如边ei=u，v，常常简记为uv或vu，其中u、v称为边uv的端点。这样，一个图事实上就是V与E构成的序偶，常常被记作G=(V,E)。于是，也常常用V(G)和E(G)来表示某一个图G的结点集与边集。当然，也可以使用其它符号来表示图，如用F或H，甚至G1等等。,10.2 图与图模型 集合V(G)的基数n表示图G的阶（Order），集合E(G)的基数m表示图G的规模（Size），有时也将图G记作(n,m)。在图G中，若边集E(G)=,则称G为零图（Null Graph），此时，又若G为n阶图，则称

6、G为n阶零图，记作Nn，特别地，称N1为平凡图（Trivial graph）。在图的定义中规定结点集V为非空集，但在图的运算中可能产生结点集为空集的运算结果，为此规定结点集为空集的图为空图（Empty Graph），并将空图记为。阶为有限的图称为有限图(Finite Graph)，否则称为无限图(Infinite Graph)。结点没有标号的图称为非标号图（Unlabeled Graph），否则为标号图（Labeled Graph）。,10.2 图与图模型 如果图中存在某两条边的端点都相同，则称该图为多重图(Multigraph)，该两条边称为平行边。如果一条边关联的两个结点是相同的结点，则称

7、该边为圈或自环(Loop)。不存在平行边与圈的图即称为简单图(Simple Graph)。,10.2 图与图模型 定义10.2 如果uv是图G的边，记为e，即uvE(G),则称结点u和v邻接(Adjacent),否则称结点u与v非邻接。这里，也称结点u或v与边e是关联（Incident）关系。与同一个结点关联的两条边称为邻接边。与结点v关联的边数称为结点v的度，记作deg(v)。与结点v关联的环对v的度数的贡献要计算两次。如果结点v的度为0，则称之为孤立点(Isolated Vertex)。一度的结点称为悬挂点（Pendant Vertex）。图G的所有结点度数的最小度数称为G的最小度，记作(

8、G)，而所有结点度数的最大者称为G的最大度，记作(G)。各结点的度均相同的图称为正则图（Regular Graph）。各结点度均为k的正则图称为k-正则图。,10.2 图与图模型 定义10.3 如果图的每条边是二结点构成的有序对，则该图称为有向图(Directed Graph)，上文所定义的图都是无向图(Undirected Graph)。有向图中边uv与vu是两条不同的边，对于边uv，称u为始点，v为终点。 有向图中，结点v的度分为入度，即与该结点相关联并以该结点为终点的边的数目，以及出度,即与该结点相关联并以该结点为始点的边的数目,分别记作deg+(v)，deg-(v)。,10.2 图与图

9、模型,无向图,有向图,10.2 图与图模型,环loop (伪图: 非简单图simple graph),边e2(有向边directed edge有向图)关联incident结点v1、v2,结点vertex/vertices(顶点),平行边/重边multiedge 多重图multigraph,多重图 且伪图 拟图 (pseudograph),孤立点 (isolated vertex),悬挂边(pendant edge),悬挂点(pendant vertex),分离边,v3结点度degree为3,与3结点邻接adjacent,2出度1入度,v3,10.2 图与图模型 练习1 设G=(V,E)是一无向

10、图，V=v1,v2, v8，E=(v1,v2),(v2,v3),(v3,v1),(v1,v5),(v5,v4), (v4,v3),(v7,v8) （1）画出G的图解； （2）指出与V3邻接的结点，以及和V3关联的边； （3）指出与(v2,v3)邻接的边和与(v2,v3)关联的结点； （4）该图是否有孤立结点和孤立边？ （5）求出各结点的度数，并判断是否是完全图和正则图？ （6）该(n,m)图中，n=？，m=？,10.2 图与图模型 图的边数与结点数的关系是图最为重要的属性，结点的度数满足一个非常简单的关系，即图的每条边都关联于两个结点，则每条边对图结点度数之和的贡献为2，从而有下面的定理： 定

11、理10.1（欧拉定理）在任何图中，结点度的总和等于边数的两倍。 该定理也被称为握手定理，被认为图论第一定理，可以用于证明图的相关性质。 推论10.1 在任意图中，奇数度的结点个数为偶数。,10.2 图与图模型 例10.3 设G=，|V|=n, |E|=m，证明：(G)2m/n(G)。 证明 由欧拉定理，deg(v)=2m。 对任意的vV，有(G)deg(v)(G)，于是 n(G)deg(v)n(G) n(G)2mn(G) 即 (G)2m/n(G)。,10.2 图与图模型 例10.4 请证明：有向图中，所有结点出度之和等于所有结点入度之和。 证明 在有向图中，任意一条边都有一个始点和一个终点，因

12、而结论成立。,10.2 图与图模型 练习2 设G=(V,E)有12条边，有6个度为3的结点，其余结点的度数均小于3，问G中至少有多少个结点？,10.2 图与图模型 例10.5 十字路口交通管理问题。下图(a)是某繁忙的城市十字路口交通管理示意图，其中c1c9表示可能的行车路线，为安全考虑，显然c1、c5可以同时进入十字路口，但c1与c8却不能同时进入十字路口，等等。本问题可以用图来建模，如下图（b）所示。其中，结点集为所有行车路线的构成的集合，结点之间的边表示相应的二行车道不能同时开通。显然此图可以用于十字路口交通信号灯的设计。,(a),(b),10.2 图与图模型,例10.6 旅行售货员问题

13、。现有一个笔记本计算机代理商要从其所在的城市北京出发，乘飞机去5个城市，然后回到出发点。如右图所示。图中结点代表城市，边代表城市间的直达航线。他怎样才能出差到每个城市恰巧一次，最后回到北京呢？,这个问题的解答本身比较简单，如可以选择线路为北京-成都-武汉-海口-广州-上海-北京。但对于更为复杂的情况就很难直接找到好的解答。本问题与后文将研究的Hamilton图有关，将在那里做详细讨论。,10.2 图与图模型,例10.7 优先图。通过并发地执行某些语句，计算机程序可以执行得更快。如何确定哪些语句可以并发执行是非常重要的，这需要分析清楚程序中语句之间的优先关系。这种优先关系可以用有向图来表示。如用

14、结点表示语句，若在执行完第一个结点表示的语句之前不能执行第二个结点表示的语句所表示的语句，则在第一个结点到第二个结点之间添加一条边。最后得到的图称为优先图。下图就是一个优先图的例子。该图表明在执行语句S1、S2与S4之前不能执行语句S5。,10.2 图与图模型 练习3 在晚会上有n个人，他们各自与自己相识的人握一次手。已知每人与别人握手的次数都是奇数，问n是奇数还是偶数。为什么？ 解 n是偶数。用n个顶点表示n个人，顶点间的一条边表示一次握手，可构成 一个无向图。若n是奇数，那么该图的顶点度数之和为奇数个奇数的和,即为奇数，与图性质矛盾，因此，n是偶数。,10.2 图与图模型 与集合论中研究子

15、集，抽象代数中研究子代数类似，图论中也研究一个图的子图。一个图G的子图G可以通过选取G中的部分结点与边构成，但要求如果选择了G中的边，则必须选择与该边向关联的结点。这样就保证了G能够构成一个图。,10.2 图与图模型 定义10.4 令图G=（V，E），称(V,E)为G的子图（Subgraph），当 (1)VV且EE； (2)对任意eE，则与e相关联的结点u,vV。 若G是 G的子图,则称G是G的超图，记作GG。若GG且GG(即VV或EE)，则称G是G的真子图。若GG且VV，则称G是G的生成子图（Spanning Subgraph）。设V1V,且V1，以V1为结点集，以两端点均在V1中的全体边为

16、边集的G的子图，称为结点集V1导出的导出子图（Derived Subgraph）。设E1E,且E1，以E1为边集，以E1中边关联的结点的全体为结点集G的子图，称为边集E1导出的导出子图。,10.2 图与图模型 显然，子图或导出子图可以通过删除一些结点或一些边得到。 例10.9 下图所示的图中，G1是G的由结点导出的导出子图，G2为G的由边集导出的导出子图。,10.2 图与图模型 定义10.5 设G =是n阶图,若G中任何结点都与其余的n1个结点相邻，则称G为n阶完全图(Complete Graph)。记作Kn。设D=为n阶有向图,若对于任意的结点,u,vV (uv) ,既有有向边,又有，则称D

17、为有向完全图。 容易得到如下重要结论： Kn的边数|E(Kn)|=n(n-1)/2，且对于一般的n个结点的图G其边数|E(G)|n(n-1)/2。,10.2 图与图模型 下图中图(a)为四个结点的完全图，(b)不是完全图，(c)是有向完全图。,(a),(b),(c),10.2 图与图模型 定义10.6 若图G的结点可以分为两个非空集合V1，V2，G中的边的端点分别属于V1，V2，则称G为二分图（Bipartite Graph），可简记为G(V1，V2)。若V1中结点与V2中结点均邻接且V2中结点与V1中结点也均邻接，则称G为完全二分图（Complete Bipartite Graph），记为K

18、m,n，m,n分别是V1，V2的基数。 二分图常常被应用于工作分配问题中，通过对二分图的分析，找出满足最多条件的工作分配方案。完全二分图K1，n常常被用来对计算机网络建模，度为n的结点代表网络服务器，其余结点代表网络中的n个计算机。,10.2 图与图模型 例10.10 下图所示的图(a)是二分图,图（b）是其的另一种表示。,10.3 路径与图连通性 图论中的许多概念和应用都与对图的遍历有关，即是从一个结点u出发，到达与之相邻接的结点，在从该邻接结点出发到达其邻接的结点，依次类推，最后可以到达图中的某结点v，从而就得到一条从u到v的通路。从u到v的通路W可用如下的结点的序列来表示： W: u=v

19、0,v1,v2,vk=v，k0。 通路W常表示为u-v通路。这些结点序列中任意相邻的结点在图中是邻接的关系，称结点vi（i=0，1,k）以及边(vi,vi+1) (i=0,1,k-1)为通路W上的结点与边。,10.3 路径与图连通性 如果通路上首尾结点相同，则称该通路是闭的(Closed)，否则称该通路是开的(Opened)。如果通路上没有相同的边，则称该通路为迹(Trail)，如果迹上的开始结点与结束结点相同，则称之为回路(Circuit)，如果回路上除了开始结点与结束结点没有相同的结点，则称之为环(Cycle)。如果通路上没有相同的结点，则称该通路为路或路径(Path)，有n个结点的路常记

20、作Pn。,10.3 路径与图连通性 通路遍历过的边的数目为通路的长度，如果通路长度为0，则称之为平凡通路（Trivial Walk）。两结点u，v间的路可能不只一条，将其中的最短的路称为u，v间的距离。 如果一条通路W上有k+1个结点，即W: u=v0,v1,v2,vk=v，k0。则由于W上的边是由W上相邻结点(vi,vi+1) (i=0,1,k-1)构成，因此W上有k条边，即W的长度为k。如果一条环C上有k+1个结点，即C: v0,v1,v2,vkv0，k0.则由于C上的边是由C上相邻结点(vi,vi+1)(i=0,1,k-1)以及（vk,v0）构成，因此C上有k+1条边，即C的长度为k+1

21、。,10.3 路径与图连通性 定理10.2 如果图G上存在一条u-v通路，则必然存在一条u-v路；如果G上存在一条闭通路，则必然存在一条回路(环)。 这是因为，如果通路上存在相同的结点vi,vj，则可将vi,vj之间的一段通路删除，并合并vi，vj为一个结点，从而得到一条更短的u-v通路。如果所得到的u-v通路上还存在相同的结点，则可以依此继续执行删除操作，最终一定可以得到一条没有相同结点的u-v通路，也就是一条u-v路。类似地，如果G上存在一条闭通路，则必然存在一条回路（环）。,10.3 路径与图连通性 例10.11 在右图中， 1) 找出一条包含图所有结点的通道； 2) 找出一条包含图所有

22、结点的迹； 3) 找出所有a-d路，并求出其长度； 4) 找出图中所有的环。 解 1) 包含图所有结点的不是迹的通道：aebcaebd。 2) 包含所有结点的迹：beacbd。 3) a-d路：aebd,acbd,长度均为3。 4) 环：acbea，长度为4。,10.3 路径与图连通性 例10.12 每个结点的度数至少为2的图必包含一个回路。 证明 设P是图G中最长路经中的一条，并设其长度为m, P的一个端点为u。考察G中与u关联的边，由于G中每个结点的度至少为2，故u必关联一条不在P上的边e，从而e的另一个端点v必然在P上，否则，将这个结点加入P上，则可以得到更长的路。于是，P上u到v的的路

23、与边e构成回路。,10.3 路径与图连通性 Dijkstra最短路径算法 输入：一个带权图G，G的任意两个结点间有路径存在，G中任意边(v,x)的权值w(v,x)0；结点a与z 输出：L(z)，从结点a到z的最短路径长度 1 Procedure Dijkstra(G) 2 For 所有结点xa 3 L(x)=; L(x)表示a到x的最短路径长度 4 End for; 5 L(a)=0; 6 T=V(G); 7 S=;,10.3 路径与图连通性 8 While(zT) 9 从T中找出具有最小L(v)的结点v; 10 For 所有与v相邻的结点xT 11 L(x)=minL(x),L(v)+w(v

24、,x) 12 End For 13 T=T-v; 14 S=Sv; 15 End While 16 End Procedure,10.3 路径与图连通性 例10.13 下图所示的带权图中，根据上述算法可以得到结点a到z的最短路径为图中加粗的边所示，长度为13。,10.3 路径与图连通性 定义10.5 如果图G中结点u到v有一条路径，则称结点u到v是可达的（Accesible）或连通的（Connected）。结点u到其自身也定义为连通的。 定义10.6 如果图G的任何两个结点都是相互可达的，称G是连通的（Connected）,并称G为连通图(Connected Graph)。对于有向图G，如果G

25、的任何两个结点都是相互可达的，则称有向图G是强连通的；如果G的任何两个结点中，至少从一个结点到另一个结点是可达的，称有向图G是单向连通的；如果G的有向边被看作无向边时是连通的，称有向图G是弱连通的。,10.3 路径与图连通性 容易判断，强连通图必定是单向连通图，单向连通图必定是弱连通图。 例10.14 下图中，(a)为连通图，(b)为由两个连通分支的非连通图，c为强连通图，d为单向连通图，e为弱连通图。 a b c d e,10.3 路径与图连通性 练习4 已知关于a,b,c,d,e,f,g的下述事实： a说英语； b说英语和西班牙语； c说英语、意大利语和俄语； d说日语和西班牙语； e说德

26、语和意大利语； f说法语、日语和俄语； g说法语和德语； 试问：上述7人中是否任意两人都能交谈（如果必要，可由其余5人中所组成的译员链帮忙？）,10.3 路径与图连通性 若将图中两个结点间的连通性看作图的结点间的一种关系，容易判定图中两个结点间的连通性是一个等价关系，因为结点u到u是连通的满足自反性；若u到v是连通的，则v到u也是连通的，满足对称性；若u到v连通，v到w连通，则u到w存在一条通路，从而存在一条u到w的路径，故u到w是连通的，满足传递性。但对于有向图，结点间的连通性不满足对称性，是偏序关系。,10.3 路径与图连通性 现在可以利用结点的连通性对图G的结点集进行划分，于是利用这个划

27、分可以得到G的多个连通子图，如 Gv=(Vv,Ev), 是结点v所在的一个连通子图，其中，Vv=x|x到v可达，Ev为Vv中结点在G中相应的边之集合。 Gv具有一个特点，即不存在一个G的真子图G, Gv为G的真子图,且G也是G的连通子图。称Gv为G的连通分支或连通分图（Connected Component）,也称为极大连通子图。,10.3 路径与图连通性 例10.15 如果图G恰有两个不同的奇数度的结点u，v，那么u到v必定是可达的。 证明 如果u到v不可达，那么G不是连通的，u与v必分属于两个连通分支G1，G2，而G1，G2是G的子图，且都恰有一个奇数度结点。与推论10.1矛盾。因而u到v

28、是可达的。,10.3 路径与图连通性 定理10.3 设G是一(n，m)图，G有个分图，则 n-m(n-)(n-+1)/2,10.3 路径与图连通性 练习5 在任何n (n2)个顶点的简单图G中，至少有两个顶点具有相同的度。 证明 如果G有两个或更多孤立顶点，那么它们便是具有相同的度的两个顶点。 如果G恰有一个孤立顶点，那么我们可对有n1 个顶点但没有孤立顶点的G（它由G删除孤立顶点后得到）作讨论；如果G有分图，则也可以直接对分图进行讨论。因此，不妨设G没有孤立顶点，那么G 的n个顶点的度数应是：1，2，3，n1 这n1种可能之一，显然，必定有两个顶点具有相同的度。,10.3 路径与图连通性 练

29、习6 给定简单图G=，且|V|=n，|E|(n-1)(n-2)/2，试证G是连通图。试给出|V|=n，|E|=(n-1)(n-2)/2的简单无向图G=是不连通的例子。,10.3 路径与图连通性 定义10.9 设S为图G的结点集V的子集，称S为G的点割集（Cut Set of Vertex）,如果从G中删除S中的所有结点后G的连通分支数增加，但S的任何真子集均无这一特性。当点割集为单元素集合v时，v称为割点（Cut Vertex）。 设S为连通图G边集E的子集，称S为G的边割集（Cut set of Edge），如果从G中删除S的所有边后G的连通分支数增加，但S的任何真子集均无这一特性。当割集为

30、单元素集e时，称e为桥(Bridge)或割边（Cut Edge）。,10.3 路径与图连通性 例10.17 下图中的图有点割集1，5，2，3是割点，而4，7不是点割集。e1,e3,e4,e5,e6,e8等均是边割集，e9是割边。,10.3 路径与图连通性 例10.18 试证明：图G的任一边，若其不是割边，则必出现于G的某一环里。 证明 设图G的边e=(vi，vj)不是分割边，去掉e后，与vi相连接的接点集为V1，与vj相连接的结点集为V2，由割边定义知，V1V2。因而存在一结点vV1V2，使得在去掉e后，vi与v有路相连，v与vj有路相连。于是vi与vj有路相连接，因而必存在一条连接vi与vj

31、的路P=vi，v1，v2，v，vj，从而P与边(vi，vj)组成一个环。,10.3 路径与图连通性 定义10.10 图G的点连通度（Vertex Connectivity）是指把G变成非连通图或平凡图至少要删除的结点数，记作(G) (读作卡帕)。定义中的平凡图主要针对G为完全图时而言的，因为完全图无论删除多少结点都不会变得不连通。根据定义，(G)可以具体定义如下： (G)=,10.3 路径与图连通性 类似地，有边连通度的定义。G的边连通度（Edge Connectivity）是指把G变成非连通图或平凡图至少要删除的边数，记作(G)。根据定义，当G为非连通图或为K1时(G)=0。 例10.17中

32、图的点连通度为1，边连通度为1。 显然，点（边）连通度越小，图的连通性越脆弱。,10.3 路径与图连通性 令(G)表示图G中结点度数的最小值（常称图G的最小度），那么我们有以下定理。 定理10.4 对于图G，有下面不等式成立： (G)(G)(G) 从直观上看，图的连通度应当与图中任两点之间的路的条数有关。连通度越高，连接两点的路应当越多。,10.3 路径与图连通性 定义10.11 设G=(V，E)是连通图，SV，u，vV。若在G-S中u，v不可达，则称S分离u，v。设FE，若在G-F中u，v不可达，则称F分离u，v。 定理10.5 在一个连通(p，q)图中，分离两个不相邻接的点u，v的点集中，

33、点的最少数目等于连接u，v的不相交的路的最多数。,10.3 路径与图连通性 证明 设G=(p，q)，u，v是G中任二不相邻的结点，且分离u，v的点集至少有k个点，连接u，v的不相交的路(点不相重)共有m条。 1) 因为连接u，v的不相交的路共有m条，这m条路除端点外无公共点，所以要分离u，v，至少要从每一条路上去掉一个点，即mk。 2) 若分离u，v的点集中至少要k个点，而连接u，v的路共有m条，则只要在这m条互不相交的路上各取一点，即可组成一个由m个点组成的点集S，S分离u，v。所以km。 由(1)、(2)结论可得k=m。证毕。,10.3 路径与图连通性 定理10.6 若u，v是图G中两个不

34、同的点，G中连接u，v的边不相交的路的最多数目，等于分离u，v的边集中边的最少数目。 以上两个定理属于Menger定理的图论形式。Menger定理具有普遍意义，它的图论形式还有多种。并且，在其它领域中，类似的定理也被一再发现。例如，网络最优化理论中有名的最大流最小割定理、集族理论中的霍尔定理、格论中关于有限格中不可比元素的数目等于包含所有元素的链集中链的最少数的定理，等等。这些定理从不同领域中发现，相互之间有着内在联系，它们都是Menger定理的变形。,10.4 图的运算 1 基本运算 删除运算 从图G中删除一边e所得到的子图，记为G-e。从图G中删除一个结点v及其关联的边所得到的子图，记为G

35、-v。类似地，G-E表示从G中删除边集E的子集E所得到的子图，记为G-E=(V，E-E)。G-V表示从G中删除结点集V的子集V以及与它们关联的边所得的子图。,10.4 图的运算 边收缩运算 设图G中边e=(vi，vj)，删去边e，并把vi与vj合并成一个新点vi-j，使原来与vi或vj关联的边变为与点vi-j关联的边，称边e被收缩，得到的新图称为G关于边e的收缩图，记为G/e或G/vivj。如下图，图（b）是对图(a)的边（d，e）收缩后得到的图。,(a),(b),10.4 图的运算 并与和运算 设G1=(V1，E1)，G2=(V2，E2)是两个给定的图，则定义： G1与G2的并为G1G2=(

36、V1V2，E1E2)； G1与G2的和G1+G2是在G1与G2的并的基础上需增加G1的每个结点与G2的每个结点连接得到的共计mn条边，m，n分别为G1，G2的阶。如下图所示，图(a)为K2K3，图(b)为K2+K3。,(a),(b),10.4 图的运算 2 补运算 在集合论与数理逻辑中都有补运算，图论中的补运算也类似。图G=(V,E)的绝对补图(简称图G的补图，记为G)是相对于以V为结点集所构成的完全图而言，V(G)=V(G),且若边eKn,但eG，则eG 。如下图所示，(b)为(a)的补图。显然，图(a)也是(b)的补图。即有：G=G。,(a),(b),10.4 图的运算 上面所定义的补图其

37、实是相对完全作图而言，但事实上，也常常需要求某图G的子图G1相对G的补，称为相对补，即V(G1)=V(G),且若边eG,但eG1，则eG1 。如下图所示，(c)为(b)相对于(a)的相对补图。,(a),(b),(c),10.4 图的运算 例10.19 对于任何一个具有6个结点的简单图G，存在一个子图K3或在G中存在子图K3. 证明 考察G中任一结点u，u与G的其余5个结点要么在G中邻接，要么在G中邻接。由于是5个结点，因此，必然是至少有3个结点在G中与u邻接，或者至少有3个结点在G中与u邻接。不妨假设有3个结点x,y,z与u在G中邻接。若这3个结点中有两个如x,y在G中邻接，则u,x,y构成G

38、的子图K3，若x,y,z在G中两两不邻接，则x,y,z在G中两两邻接，即x,y,z构成G中的子图K3。,10.4 图的运算 3 笛卡尔积 设图G和H的结点集分别为u1,u2,um和v1,v2,vn，G，H的笛卡尔积记作GH,，其结点集由标记为(i，j)的mn个结点组成，其中1im,1jn；当且仅当满足下列两个条件之一时，两个结点（i,j），(h,k)邻接： 1) i=h，且vj和vk在图H中邻接； 2) j=k, 且ui和uh在图G中邻接。 对于每个i，结点集(i,j)的导出子图是图H的副本，称为H的第i个副本，其中j=1,2,n；对于每个j，结点集(i,j)的导出子图是图G的副本，称为G的第

39、j个副本，其中i=1,2,m。,10.4 图的运算 例10.20 如下图所示，GH为G，H的笛卡尔积。可以看到GH中有G的三个副本，H的四个副本。由于v1，v2邻接，因此G的副本1与副本2的对应结点邻接，由于v2，v3邻接，因此G的副本2与副本3的对应结点邻接，但v1，v3不邻接，因此G的副本1与副本3的对应结点不邻接。,10.4 图的运算 4 超立方体 超立方体在并行计算中的计算机体系结构中具有重要的应用。超立方体Qn可以由笛卡尔积来定义： Q0=K1,Qn=K2Qn-1. 之所以称Qn为超立方体，是因为n=3时，Qn可以画成三维的立方体，且可以扩展到更高维。下图给出了前5个超立方体。超立方

40、体Qn的n是指Qn结点标号所用的二进制位之长度，且要求相邻结点标号只相差一位。所以Qn有2n个结点。Qn这种编号方式可用在计算机编码如格雷码的设计方面，至于如何实现Qn这样的编号，其中一种方法是按照后文10.7节将讨论的找Qn中Hamilton环的方法。,10.4 图的运算,10.4 图的运算 5 网格 网格也是计算机处理器互联一种方式，利用笛卡尔积也可以构造网格。网格也可以称为网或格。 2维网格M(m,n)是由路径Pm与Pn的笛卡尔积来定义，即M(m,n)=PmPn。3维网格M(m,n,k)是Pm与Pn、Pk的笛卡尔积来定义，即M(m,n)=Pm PnPk 。网格可以扩展到n维。图9.21所

41、示的两个图分别为网格M(3,2)与M(3,2,3)。,10.4 图的运算,10.5 图的表示与图的同构 1 图的表示 在集合论中，曾经用关系矩阵来表示关系，事实上，图也是一种关系的表示，但用计算机来分析一个图时，矩阵是其更为形式化的表示方法，这里主要讨论邻接矩阵。 构造一个图的邻接矩阵是很容易的，可以通过下面的例子来分析。,10.5 图的表示与图的同构 例10.21 构造下图中图G的邻接矩阵。顾名思义，邻接矩阵就是表示图结点的邻接关系的矩阵，邻接矩阵与图是一种一一对应关系。首先，需要确定图结点的顺序，本题中为a，b，c，d，e。接着，矩阵的元素(ij)表示第i个结点与第j个结点的邻接关系，这里

42、用1或0来表示，如果邻接，则(ij)为1，否则为0。于是得到图G的邻接矩阵 A(G)=,10.5 图的表示与图的同构 可以看到，图G的邻接矩阵是关于主对角线对称的，这是因为这里讨论的图是无向图，但有向图的邻接矩阵一般不是对称的，因此，邻接矩阵对于表示有向图可能更有效。后文继续对无向图展开讨论，相关结论也可以应用到有向图中。 邻接矩阵可以用来求解图中从一个结点到另一个结点的某长度的路径的数目，如对于例10.21中图的邻接矩阵A(G),有,10.5 图的表示与图的同构 A(G)2= = 以A(G)2中d行c列的元素为例，其值是A(G)中第d行与A(G)中第c列运算得到，即 =11+01+10+01

43、+11=2,10.5 图的表示与图的同构 显然，可以看到，只有G中存在形如(d,v)与(v,c)的边，才能形成了从d到c长度为2的路径(a,v,c)。相应地，这两条边在矩阵A(G)中的值为1，于是其对A(G)2的第d行c列元素值得贡献分别为1。如A中存在边(d,a)以及边(a,c)，从而有长度为2的路径(d,a,c)。此外，还存在d到c的路径(d,e,c)。于是共存在d到c的长度为2的路径2条，因此，A(G)2的第d行c列元素值为2。,10.5 图的表示与图的同构 定理9.7 如果A是一个图G的邻接矩阵，那么An（n=1，2，3，）中元素(ij)等于从结点i到结点j的长度为n的路径的数目。,1

44、0.5 图的表示与图的同构 2 图的同构 定义10.12 设图G1=，G2=，若存在双射 f:V1V2，满足uV1，vV1，(u,v)E1当且仅当(f(u),f(v)E2，则称G1与G2同构，记作G1G2，f称为同构映射。如果讨论有向图的同构，则对应边的方向也必须一致。 从图的同构的定义可知，二图同构则必有结点数相同，边数相同，两图中度数相同的结点的个数相同。还可以知道，图的同构关系是一种等价关系。,10.5 图的表示与图的同构 例10.23 下图中，G1与G2不同构，原因在于G1中存在三结点两两相邻，而G2中不存在，因此不可能建立满足定义的双射关系。类似地，图G4与G2不同构，原因在于G4中

45、存在三结点两两不相邻，而G2中却不存在这样的情况。G1与G3同构。,10.5 图的表示与图的同构 图的同构的判断主要是建立同构映射，如果能够建立，则同构的两个图除了结点符号相异外，结构上是完全一样的。因此，容易想到考虑用邻接矩阵来进行判断，即：图G1和G2是同构的当且仅当对某一结点的顺序，其邻接矩阵是一样的，最基本的方法是通过变换矩阵行、列元素的顺序来比较二邻接矩阵是否相等。尽管通过判断邻接矩阵来判断图是否同构是可行的，但在最坏情况下，其搜索空间将达到n!(n为结点数)，具有指数级算法复杂性。如果n很大，算法的效率是非常低的，甚至不可解。,10.5 图的表示与图的同构 从例10.23还可以看到

46、，图G1和G2同构时，G1具有的特性P，G2也应该具备这个特性P。于是判断两个图G1和G2不同构的办法可以是：找到一个G1的特性P，G2并不具备。这样的一个特性称为不变量。如“有10个结点”、“有一个度数为k的结点”，以及例10.23中用到的“有k个结点两两相邻（或不相邻）”等等。如果能够找到一些可以简单测试的同构图具有且只有同构图具有的不变量，那么就可以非常容易的判断两个图是否同构。不幸的是，没有人能够成功找到这样一些不变量。,10.5 图的表示与图的同构 例10.24 若图G与其补图同构，则称G为自补图。请找出所有的阶数小于6的自补图。 解 所找到的阶数小于6的自补图有4个，如下图所示。,

47、10.5 图的表示与图的同构 练习7 画出完全图K5的4条边的所有非同构的生成子图。,10.5 图的表示与图的同构 练习8 画出所有具有5个结点3条边的互不同构的简单无向图。,10.5 图的表示与图的同构 练习9 设G是具有3个结点的完全图，试问： （1）G有多少个子图？ （2）G有多少个生成子图？ （3）如果没有任何两个子图同构，则G的子图个数是多少？,10.6 欧拉图,七桥问题 问题 寻找走遍哥尼斯堡（Knigsberg）城的7座桥，且只许走过每座桥一次，最后又回到原出发点(图论源于游戏) 求解 1736年瑞士大数学家欧拉（Leonhard Euler） 发表了关于“哥尼斯堡七桥问题”的论

48、文（图论的第一篇论文）。他指出 从一点出发不重复的走遍七桥，最后又回到原来出发点是不可能的。,10.6 欧拉图,研究方法 抽象 用4个字母A、B、C、D代表4个城区,并用7条线表示7座桥。 从而将哥尼斯堡七桥问题抽象为一个数学问题:即经过图中每边一次且仅一次的问题。 后来人们把有这样的回路的图称为欧拉图。 欧拉因此被称为“图论之父”，1736年通常被称为“图论元年”。,10.6 欧拉图,定义10.11 给定无孤立点图G，若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路(Euler Circuit)。具有欧拉回路的图称为欧拉图(Euler Grpah)。若存在一条迹，经过图中每边一次且仅一次，该条路称为欧拉迹(Euler Trail)。,10.6 欧拉图,定理10.8 图G是欧拉图当且仅当G是连通的且每个结点的度数为偶数。 证明 先证必要条件：设G是欧拉图。是G的一个欧拉回路。 当通过G的任一结点v时，通过关联于v的两条边。若通过v点k次，则通过关联于v的2k条边。是欧拉回路。因此通过关联于v的2k条边即是关联于v的所有边且互不相同，即v的度数为2k。由v的任意性，必要性得证。,10.6 欧拉图,再证充分条件：设G是连通图且所有结点度数为偶数，按如下步骤构造G的欧拉回路。 1) 从任一结点