图论及其应用图论及其应用1第一章第一章 图的基本概念图的基本概念本次课主要内容本次课主要内容子图、图运算、路与连通性子图、图运算、路与连通性(一一)、子图的相关概念、子图的相关概念(三三)、路与连通性、路与连通性(二二)、图运算、图运算21 1、子图、子图简单地说，图简单地说，图G的任意一部分的任意一部分(包括本身包括本身)都称为是图都称为是图G的的的一个子图。的一个子图。定义定义1 1 如果如果(一一)、子图的相关概念、子图的相关概念且且H H中边的重数不超过中边的重数不超过G G中对应边的条数，则称中对应边的条数，则称H H为为G G的子图，记为的子图，记为当当 时，称时，称H H是是G G的真子图，记为的真子图，记为 32 2、点与边的导出子图、点与边的导出子图(1) 图图G的顶点导出子图的顶点导出子图定义定义2 2 如果如果 ，则以，则以 为顶点集，为顶点集，以两个端点均在以两个端点均在 中的边集组成的图，称为中的边集组成的图，称为图图G G的点导出子图。记为：的点导出子图。记为：例例1 如图所示，求如图所示，求 。其中。其中12345图图G4解：由点导出子图的定义得：解：由点导出子图的定义得：135(2) 图图G的边导出子图的边导出子图定义定义3 3 如果如果 ，则以，则以 为边集，为边集，以以 中边的所有端点为顶点集组成的图，称为中边的所有端点为顶点集组成的图，称为图图G G的边导出子图。记为：的边导出子图。记为：例例2 如图所示，求如图所示，求 。其中。其中5解：由边导出子图的定义得：解：由边导出子图的定义得：12345图图G1234563 3、图的生成子图、图的生成子图定义定义3 3 如果图如果图G G的一个子图包含的一个子图包含G G的所有顶点，称的所有顶点，称该子图为该子图为G G的一个生成子图的一个生成子图例例2 如图所示，求如图所示，求G的所有生成子图的所有生成子图123图图G解：按边数分别求出解：按边数分别求出7定理：简单图定理：简单图G=(n,m)的所有生成子图个数为的所有生成子图个数为2m(二二)、图运算、图运算 在图论中，将两个或更多的图按照某种方式合并，或者对在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。合并或对一个图进行操作，称为图运算。图运算形式很多。1、图的删点、删边运算、图的删点、删边运算(1)、图的删点运算、图的删点运算设设 ，在，在G中删去中删去 中的顶点和中的顶点和G中与之关中与之关联的所有边的操作，称为删点运算。记为联的所有边的操作，称为删点运算。记为特别地，如果只删去一个点特别地，如果只删去一个点v，则记为，则记为G-v.8(2)、图的删边运算、图的删边运算设设 ，在，在G中删去中删去 中的所有边的操作，中的所有边的操作，称为删边运算。记为称为删边运算。记为特别地，如果只删去一条边特别地，如果只删去一条边e，则记为，则记为G-e.注：删点、删边后得到的图是原图的子图。注：删点、删边后得到的图是原图的子图。2、图的并运算、图的并运算 设设G1,G2是是G的两个子图，的两个子图，G1与与G2并是指由并是指由 为为顶点集，以顶点集，以 为边集组成的子图。记为：为边集组成的子图。记为： 特别是，如果特别是，如果G1,G2不相交不相交(没有公共顶点没有公共顶点)，称它们的并为直接并，称它们的并为直接并，可以记为：可以记为：92、图的交运算、图的交运算 设设G1,G2是是G的两个子图，的两个子图，G1与与G2交是指由交是指由 为为顶点集，以顶点集，以 为边集组成的子图。记为：为边集组成的子图。记为： 设设G1,G2是两个图，是两个图，G1与与G2的差是指从的差是指从G1中删去中删去G2中的边得到的新中的边得到的新图。记为图。记为G1-G2.3、图的差运算、图的差运算4、图的对称差运算、图的对称差运算(或环和运算或环和运算) 设设G1,G2是两个图，是两个图，G1与与G2的对称差定义为：的对称差定义为：10例例3 已知已知G1与与G2，求，求1234abcdefG1h2354cdegijG2解：由相应运算定义得下面结果：解：由相应运算定义得下面结果：1234abcdef5hgij234cde11123abfh2354gij1234abf5hgij125、图的联运算、图的联运算 设设G1,G2是两个不相交的图，作是两个不相交的图，作G1+G2，并且将，并且将G1中每个顶点和中每个顶点和G2中的每个顶点连接，这样得到的新图称为中的每个顶点连接，这样得到的新图称为G1与与G2的联图。记为的联图。记为 ：例例4 已知已知G1与与G2，求，求21G1345G2解：由联图的定义得：解：由联图的定义得：21345136、图的积图、图的积图 设设 是两个图。对点集是两个图。对点集 的任意两个点的任意两个点u=(u1,u2)与与v=(v1,v2),当当(u1=v1和和u2adjv2)或或(u2=v2和和u1adjv1)时，时，把把u与与v相连。如此得到的新图称为相连。如此得到的新图称为G1与与G2的积图。记为的积图。记为例例5 已知已知G1与与G2，求，求G112G2345(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)146、图的合成图、图的合成图 设设 是两个图。对点集是两个图。对点集 的任意两个点的任意两个点u=(u1,u2)与与v=(v1,v2),当当(u1adjv1)或或(u1=v1和和u2adjv2)时，时，把把u与与v相连。如此得到的新图称为相连。如此得到的新图称为G1与与G2的合成图。记为的合成图。记为 例例6 已知已知G1与与G2，求，求G112G2345(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)15 图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常图的积运算是网络构造的常用方法。并行计算机中的网络拓扑常采用所谓的采用所谓的“超立方体超立方体”结构。采用该结构可使网络具有较好的可结构。采用该结构可使网络具有较好的可靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点。 “超立方体超立方体”可以采用积图来递归构造。定义如下：可以采用积图来递归构造。定义如下： (1) 1方体方体 (2) n方体定义为：方体定义为：Q1Q3Q2 “超立方体超立方体”常采用下面简单的递归构造方法：常采用下面简单的递归构造方法：16 n方体方体Q n的顶点可用一个长度为的顶点可用一个长度为n的二进制码来表示。的二进制码来表示。Q n的顶点的顶点数目正好等于数目正好等于2n个。个。 由由n-1方体方体Q n-1构造构造Q n的方法是：将的方法是：将Q n-1拷贝一个。将原拷贝一个。将原Q n-1每个每个顶点的码后再添加一个零，将拷贝得来的顶点的码后再添加一个零，将拷贝得来的n-1方体每个顶点的码前面方体每个顶点的码前面再添加一个再添加一个1。然后在两个。然后在两个n-1方体之间连线：当且仅当两个顶点码只方体之间连线：当且仅当两个顶点码只有一位对应位数字不同时，该两点连线。如此得到的图即为有一位对应位数字不同时，该两点连线。如此得到的图即为n方体。方体。 关于关于n方体方体Q n的性质研究，可以查阅到很多文献。经典文章是：的性质研究，可以查阅到很多文献。经典文章是：Saad Y, Schultz M H. Topological properties of hypercubes J. IEEETrans. Comput . 1988, 37(7) : 867-8727、图的联合、图的联合 把把G1的一个顶点和的一个顶点和G2的一个顶点粘合在一起后得到的新图称为的一个顶点粘合在一起后得到的新图称为G1与与G2的联合。记为：的联合。记为：17(三三)、路与连通性、路与连通性 对图的路与连通性进行研究，在计算机网络研究中有十分重要的对图的路与连通性进行研究，在计算机网络研究中有十分重要的意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠性也是主要问题之一，它与图的连通性问题相对应。性也是主要问题之一，它与图的连通性问题相对应。1、路与连通性的相关概念、路与连通性的相关概念(1)、图中的途径、图中的途径 G的一条途径（或通道或通路）是指一个有限非空序列的一条途径（或通道或通路）是指一个有限非空序列w= v0 e1 v1 e2 v2ek vk，它的项交替地为顶点和边，使得它的项交替地为顶点和边，使得 ，ei的端点是的端点是vi-1和和vi. 途径中边数称为途径的长度；途径中边数称为途径的长度；v0,vk分别称为途径的起点与终点，分别称为途径的起点与终点，其余顶点称为途径的内部点。其余顶点称为途径的内部点。(2)、图中的迹、图中的迹 边不重复的途径称为图的一条迹。边不重复的途径称为图的一条迹。18 图中顶点图中顶点u与与v的距离：的距离：u与与v间最短路的长度称为间最短路的长度称为u与与v间距离。记为间距离。记为d (u, v). 如果如果u与与v间不存在路，定义间不存在路，定义d (u, v)=.(3)、图中的路、图中的路(4)、图中两顶点的距离、图中两顶点的距离注：起点与终点重合的途径、迹、路分别称为图的闭途径、闭迹注：起点与终点重合的途径、迹、路分别称为图的闭途径、闭迹 与圈。闭迹也称为回路。长度为与圈。闭迹也称为回路。长度为k的圈称为的圈称为k圈，圈，k为奇数时称为奇为奇数时称为奇 圈，圈，k为偶数时称为偶圈。为偶数时称为偶圈。 顶点不重复的途径称为图的一条路。顶点不重复的途径称为图的一条路。(5)、图中两顶点的连通性、图中两顶点的连通性 图图G中点中点u与与v说是连通的，如果说是连通的，如果u与与v间存在通路。否则称间存在通路。否则称u与与v不连不连通。点的连通关系是等价关系。通。点的连通关系是等价关系。 如果图如果图G中任意两点是连通的，称中任意两点是连通的，称G是连通图，否则，称是连通图，否则，称G是非连通是非连通图。非连通图中每一个极大连通部分，称为图。非连通图中每一个极大连通部分，称为G的连通分支。的连通分支。G的连通的连通分支的个数，称为分支的个数，称为G的分支数，记为的分支数，记为19(6)、图的直径、图的直径 连通图连通图G的直径定义为：的直径定义为： 如果如果G不连通，图不连通，图G的直径定义为的直径定义为 例例6 证明：在证明：在n阶连通图中阶连通图中 (1) 至少有至少有n-1条边；条边； (2) 如果边数大于如果边数大于n-1，则至少有一条闭迹；，则至少有一条闭迹； (3) 如果恰有如果恰有n-1条边，则至少有一个奇度点。条边，则至少有一个奇度点。 证明证明: (1) 若若G中没有中没有1度顶点，由握手定理：度顶点，由握手定理：20若若G中有中有1度顶点度顶点u，对，对G的顶点数作数学归纳。的顶点数作数学归纳。当当n=2时，结论显然；设结论对时，结论显然；设结论对n=k时成立。时成立。当当n=k+1时，考虑时，考虑G-u,它仍然为连通图，所以，边数它仍然为连通图，所以，边数k-1.k-1.于是于是G G的的边数边数k.k. 另证：由于另证：由于G连通，所以，存在如下形式的途径：连通，所以，存在如下形式的途径： 显然该途径至少含有显然该途径至少含有n-1条边。条边。(v1,v2, , v n是是G的的n个不同顶点个不同顶点) (2) 考虑考虑G中途径：中途径： 若若W是路，则长为是路，则长为n-1;但由于但由于G的边数大于的边数大于n-1,因此，存在因此，存在vi与与vj,它它们相异，但邻接。于是：们相异，但邻接。于是： 为为G中一闭途径，于是也就存在闭迹。中一闭途径，于是也就存在闭迹。21 (3) 若不然，若不然，G中顶点度数至少为中顶点度数至少为2，于是由握手定理：，于是由握手定理： 这与这与G中恰有中恰有n-1条边矛盾！条边矛盾！ 例例7 证明：若证明：若2，则G中必然含有圈。中必然含有圈。 证明：只就连通图证明即可！证明：只就连通图证明即可！设设W=v1v2.vk-1vk是是G中的一条最长路。由于中的一条最长路。由于2，所以，所以vk必然有相必然有相异于异于vk-1的邻接顶点。又的邻接顶点。又W是是G中最长路所以，这样的邻接点必然是中最长路所以，这样的邻接点必然是v1,v2,.,vk-2中之一。设该点为中之一。设该点为vm，则，则vmvm+1.v kvm为为G中圈。中圈。 例例8 设设G是具有是具有m条边的条边的n阶单图，证明：若阶单图，证明：若G的直径为的直径为2且且=n-2,=n-2,则则m2n-4.m2n-4. 证明：设证明：设d (v)=n-2,=n-2,且设且设v v的邻接点为的邻接点为v v1 1,v,v2 2,v,vn-2n-2. u. u是剩下的一是剩下的一个顶点。由于个顶点。由于d (G)=2d (G)=2且且u u不能和不能和v v邻接，所以邻接，所以u u必须和必须和v v1 1,v,v2 2,v vn-2n-2中每个顶点邻接。否则有中每个顶点邻接。否则有d (G)2.d (G)2.于是得：于是得：m2n-4.m2n-4.22 例例8的说明图为：的说明图为： 2、连通性性质、连通性性质 定理定理1：若图：若图G不连通，则其补图连通不连通，则其补图连通 证明：对证明：对 ,如果如果u, v属于属于G的同一分支，设的同一分支，设w是与是与u, v处于不同分支中的点，则在处于不同分支中的点，则在G的补图中，的补图中，u与与w, v与与w分别邻接，于是，分别邻接，于是，u与与v在在G的补图中是连通的。的补图中是连通的。23 如果如果u与与v在在G的两个不同分支中，则在的两个不同分支中，则在G的补图中必然邻接，因此，的补图中必然邻接，因此，也连通。也连通。 所以，若所以，若G不连通，不连通，G的补图是连通的。的补图是连通的。 定理定理2：设图：设图G为为n阶图，若对阶图，若对G中任意两个不相邻顶点中任意两个不相邻顶点u与与v，有：，有： 则则G是连通的是连通的,且且d (G)2.2. 证明：我们证明，对证明：我们证明，对G中任意两点中任意两点x与与y,一定存在一条长度至多为一定存在一条长度至多为2的的连接连接x与与y的路。的路。若若 ,则上面论断成立！若则上面论断成立！若 可以证明，存在点可以证明，存在点w，它与，它与x, y同时邻接。同时邻接。 若不然，在若不然，在G的剩下的的剩下的n-2个顶点中，假设有个顶点中，假设有k个与个与x邻接，但与邻接，但与y不不邻接，有邻接，有l个顶点和个顶点和y邻接，但不和邻接，但不和x邻接，同时假定有邻接，同时假定有m个顶点个顶点24 和和x, y 均不邻接。则：均不邻接。则：d (x)=k-1 ,d (y)= l-1。由于。由于k+ l+ m=n-2,所以，所以，d (x)+ d (y) =k + l- 2n-4,n-4,矛盾！矛盾！ 推论：设图推论：设图G为为n阶图，若阶图，若(n-1)/2,(n-1)/2,则则 G G 连通。连通。 证明：对证明：对G中任意两个不相邻顶点中任意两个不相邻顶点u与与v，有：，有： 所以，所以，G是连通的。是连通的。 注意：定理注意：定理2的界是紧的的界是紧的(Sharpness)。即不能再修改！。即不能再修改！ 例如：设例如：设G由两个分支作成的图，两个分支均为由两个分支作成的图，两个分支均为Km, 则则G中不相邻顶中不相邻顶点度数之和恰为点度数之和恰为n-2.(n=2m)3、偶图的判定定理、偶图的判定定理25定理定理3 一个图是偶图当且当它不包含奇圈一个图是偶图当且当它不包含奇圈。证明：证明： 必要性必要性：设：设G是具有二分类（是具有二分类（X, Y）的偶图，并且）的偶图，并且C = v0 v1 vk v0是是G的一个圈的一个圈 不失一般性，可假定不失一般性，可假定 。一般说来，一般说来， 。又因为 ，所以，所以 由此即得由此即得C是偶圈是偶圈。 充分性充分性：在：在G中任意选取点中任意选取点u, 定义定义V的分类如下：的分类如下：X = x | d (u, x) 是偶数，是偶数，x V (G)Y = y | d (u, y) 是奇数，是奇数，y V (G)下面证明：对下面证明：对X中任意两点中任意两点v与与w , v与与w不邻接！不邻接！26 设设v与与w是是X中任意两个顶点。中任意两个顶点。P是一条最短是一条最短(u , v)路路 ，而，而Q是一条最是一条最短的短的(u, w)路。路。QPvuwu1 又设又设u1是是P和和Q的最后一个交点。由于的最后一个交点。由于P, Q是最短路，所以，是最短路，所以，P,Q中中u到到u1段长度相同，因此奇偶性相同。又段长度相同，因此奇偶性相同。又P,Q的长均是偶数，所以，的长均是偶数，所以，P,Q中中u1v段和段和u1w段奇偶性相同。段奇偶性相同。 如果如果v与与w邻接，则可得到奇圈，矛盾！邻接，则可得到奇圈，矛盾！27作业作业P29P30 13, 14, 20, 2228Thank You !29