第十四章 图的基本概念.

1、第四部分 图论引言图论以图为研究对象，这种图以若干个给定的点和连接两点的线构成。借以描述某些事物之间的描述某些事物之间的某种特定关系某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的特定关系。图论是离散数学的重要组成部分，是近代应用数学的重要分支。图论最早起源于一些数学游戏难题研究：如：迷宫问题，匿门博奕问题，及后来的地图四色问题和哈密顿环游世界问题。1936年 科尼格科尼格 出版图论第一本专著有限图与无限图理论。发展：1736年 欧拉欧拉 （创始人）发表了“哥尼斯堡七桥问题无解”论文；1847年 克希霍夫克希霍夫 用图论分析“电网络问题”；里程碑作为描述事务之间关系的手段或称

2、工具，目前，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。 14.1 图的基本概念图图：用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。无序积无序积：设A , B为任意的两集合，称a , b| aAbB 为A与B的无序积，记作：A&B , 其中无序对a , b记为(a , b) , 且对任意 (a , b)A&B ,有(a , b)=(b , a),即：A&B= B&A区分几何图

3、形图的严格数学定义：1、无向图无向图是一个有序的二元组,记为G； 其中 V,称为顶点集，其元素称为顶点或结点； E称为边集,是V&V的多重子集。 其元素称为无向边。2、有向图有向图是一个有序的二元组,记为D； 其中 V , 为顶点集； E为边集,是VV的多重子集。 其元素称为有向边。e1e3e2e4e7e5e6v1v5v2v4v3给定无向图 G=，其中V=v1,v2,v3,v4,v5E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5) 返回12返回15给定有向图D=，其中V=a , b , c , dE=, ,e2e3e6e

4、5e4e7e1abdc返回133、相关概念及规定|V(G)|= 空图空图，记为 G泛指图泛指图 ，D只能用于有向图 V(G) 、 E(G) 分别表示G的顶点集、边集顶点集、边集；|V(G)|、|E(G)| 分别表示G的顶点数、边数，若均有限，称G为有限图有限图； |V(G)|= n n 阶图阶图， E(G)= 零图零图 即只有顶点； |V(G)|= n 且 E(G)= n 阶阶零图零图，记作Nn称N1为平凡图平凡图，即只有一个顶点；顶点或边用字母标定的图标定图标定图，否则为非标定图常用ek表示一条无向边(vi,vj) 或有向边有向图各有向边均改为无向边后的图称为原有向图的基图基图4、关联与相邻

5、点和边的关联点和边的关联：若 ei =(u , v) 或 ei=则 u , v与ei相关联，称u , v是ei的端点，若uv,则称ei与u 或ei与v的关联次数为1；环环：一条边的两个关联的点是同一点的边称为环。无向图中若两点间有多条边,称这些边为平行边；平行边平行边：在有向图中,始点和终点均相同的边称为平行边；边与边的相邻：边与边的相邻：若 ei与ej至少有一个公共端点，称ei ，ej两边相邻； 若 ei= ，则称u为始点，v 为终点，并称u邻接到v，v邻接于u点与点的相邻：点与点的相邻：若 ei = (u , v) 或 ei= 称u , v 两点相邻；孤立点：孤立点：与任何边均不关联的点称

6、为孤立点。两点间平行边的条数称为边的重数重数；含平行边的图称为多重图多重图，不含平行边和环的图称为简单图简单图。称 e|eEe与v相关联 为v的关联集，记作IG(v);5、邻域设无向图 G= , v V, 称u|uV(u , v)Euv 为v的邻域的邻域，记作NG(v),并称 NG(v)v 为v的闭邻域的闭邻域，记作NG(v) ,示例 设有向图 D=, v V, 称 u|uVEuv 为v的后继元集，记作+D(v), 称 u|uVEuv 为v的先驱元集，记作-D(v), 称 +D(v) -D(v) 为v的邻域的邻域，记作ND(v), 并称 ND(v)v 为v的闭邻域的闭邻域，记作ND(v).示例

7、6、点的度数设无向图 G= , v V, 称v作为边的端点的次数之和为v的度数，简称度度，记作dG(v), 简记为d(v);设有向图G=, vV, 称以v为始点的边的条数为该点的出度出度,记作dD+(v), 简记为d+(v); 以v为终点的边的条数为该点的入度入度,记作dD- (v), 简记为d- (v);称 d+(v)+d-(v)为v的度数，记作d (v)。在有向图D中，称+(D) = maxd+(v)| vV(D) 为D的最大出度，记为+(D) = mind+(v)| vV(D) 为D的最小出度，记为+-(D) = maxd-(v)| vV(D) 为D的最大入度，记为-(D) = mind

8、-(v)| vV(D) 为D的最小入度，记为-在无向图G中，称(G) = maxd (v)| vV(G) 为G的最大度，简记为； (G) = mind (v)| vV(G) 为G的最小度，简记为；悬挂顶点（相关联的边为悬挂边）：度数为一的顶点。偶度（奇度）顶点 示例二、图的基本定理：定理1：在任意无向图中,结点度数和等于边数的二倍结点度数和等于边数的二倍。 即 d(v1)+ d(v2)+ d(vn)=2m 其中 |V|=n , |E|=m （又称握手定理）定理2：在任意有向图中所有结点的入度之和结点的入度之和等于所有 结点的出度之和结点的出度之和。 即 d(v1)+ d(v2)+ d(vn)=

9、2m 且d+(v1)+ d+(v2)+ d+(vn)= d-(v1)+ d-(v2)+ d-(vn)=m推论：在任何图中, 奇度顶点的个数必为偶数奇度顶点的个数必为偶数。定理4： 设G为任意n阶无向简单图，则 (G) n-1设G=,为一个n阶无向图，V= v1,v2,vn,称 d(v1), d(v2), d(vn) 为G的度数列度数列，反之，给定非负整数列 d=(d1,d2, ,dn),若存在以V= v1,v2,vn为顶点集的n阶无向图,使得d(vi)=di , 则称d是可图化的可图化的。若所得图为简单图，则称d是可简单图化的。定理3：设非负整数列d=(d1,d2, ,dn), 则d是可图化的

10、当且仅当 为偶数。niid1例例142 判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？ (1) (5,5,4,4,2,1)(2) (5,4,3,2,2)(3) (3,3,3,1)(4) (d1,d2,dn)，d1d2dn1 且 为偶数(5) (4,4,3,3,2,2) 解解 易知，除(1)中序列不可图化外，其余各序列都可图化。但除了(5)中序列外，其余的都是不可简单图化的。(2)中序列有5个数，若它可简单图化，设所得图为G，则(G)=max5,4,3,2,2=5，这与定理4矛盾。所以(2)中序列不可简单图化。类似可证(4)中序列不可简单图化。 假设(3)中序列可以简单图化，设G=以(

11、3)中序列为度数列。不妨设V=v1，v2，v3，v4 且d(v1)= d(v2)=d(v3)=3,d(v4)=1，由于d(v4)1，因而v4只能与v1，v2，v3之一相邻，于是v1，v2，v3不可能都是3度顶点，这是矛盾的，因而(3)中序列也不可简单图化。 (5)中序列是可简单图化的，如下图所示：三、图的同构设G1=, G2=为两个无向图（有向图），若存在双射函数双射函数 f : V1 V2,对于 vi , vjV1 , ( vi, vj)E1 (E1)当且仅当 (f(vi) , f(vj) E2 (E2 ) 并且 ( vi, vj) ()与 (f(vi) , f(vj) ()的重数相同，则称

12、G1与与G2是同构，是同构，记作G1G2 不同构（1）为彼得松）为彼得松(Petersen)图图 ，（2）（3）均与（1）同构edcbaijfgh（1）bgfeacdhij（2）eiahbjifcdg（3）图之间的同构关系是等价关系 图之间的同构关系 可看成全体图集合上的二元关系，这个二元关系 具有自反性，对称性和传递性，因而它是等价关系。在这个等价关系的每一等价类中均取一个非标定图作为一个代表，凡与它同构的图，在同构的意义之下都可以看成一个图，在图14.3中，(1)，(2)，(3)可以看成一个图，它们都是彼得松图，其中的(1)可看成这类图的代表。提到彼得松图，一般是指(1)中图。 至此，可以

13、这样说，在图同构的意义下，图的数学定义与图形表示是一一对应的。 关于图之间的同构问题还应该指出以下两点： a到目前为止，人们还没有找到判断两个图是否同构的好的算法，还只能根据定义看是否能找到满足条件的双射函数，显然这是困难的。 b需要注意的是，不要将两个图同构的必要条件当成充分条件。若G1 G2，则它们的阶数相同，边数相同，度数列相同，等等。破坏这些必要条件的任何一个，两个图就不会同构，但以上列出的条件都满足，两个图也不一定同构，见图有相同的度数列，但它们不同构。 四、 完全图和补图G=为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图阶无向完全图,记作Kn(n

14、1）D=为n阶有向简单图，若D中每一对顶点间均有方向相反的两边关联,则称D是n阶有向完全图有向完全图； D=为n阶有向简单图，若D的基图为n阶无向完全图， 则称D是n阶竞赛图竞赛图。n阶无向完全图， n阶有向完全图， n阶竞赛图的边数分别为 n(n-1)/2 ，n(n-1) , n(n-1)/2设G为n阶无向简单图， v V(G)，均有d(V)=k,则称G为k-k-正则图正则图；由定义可知，n阶零图是0-正则图，n阶无向完全图是(n-1)正则图，彼得松图是3-正则图。 由握手定理可知，n阶k-正则图中，边数m=kn/2，因而当k为奇数时，n必为偶数。 e1e3e4e5e2e1e5e1e3abd

15、cabcabdc设G=，G=为两个图（同为无向图或有向 图），若VV且E E , 则称G是G的子图子图, G为G的母图，母图，记作GG；若VV且EE , 则称G是G的真子图，若V=V，则称G是G的生成子图生成子图。设G=为一图， V1V且V1，E1E且E1GV1：以V1为顶点集，以G中两个端点都在V1中的边 组成边集的图，称为V1导出的子图。GE1：以E1为边集，以E1中边关联的顶点组成顶点集 的图，称为E1 导出的子图。V1=a,b,cE1=e1,e3例例143 (1) 画出4阶3条边的所有非同构的无向简单图。 (2) 画出3阶2条边的所有非同构的有向简单图。 解解 (1)由握手定理可知，所

16、画的无向简单图各顶点度数之和为23=6，最大度小于或等于3。于是所求无向简单图的度数列应满足的条件是，将6分成4个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数的个数为偶数。将这样的整数列排出来只有下面三种情况： (a) 3，1，1，1(b) 2，2，1，1(c) 2，2，2，0 将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图 (2) 由握手定理可知，所画有向简单图各顶点度数之和为4，最大出度和最大入度均小于或等于2.度数列及入度出度列为 (b) 2，2，0 (a) 1，2，1其中3个无向图都是K4的子图，而且是生成子图，4个有向图都是3阶有向完全图的生成子图。 试问K

17、4的所有非同构的i(i=0，1，2，4，5，6)条边的生成子图各有几个？ 自补图 互为补图设G =为无向图，GE 从G中去掉边E ，称为删除删除E ；Ge 从G中去掉边e，称为删除边删除边e；设G =为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn添加边组成的集合为边集的图,称为G的补图补图，记作G；若图GG，则G是自补图自补图G(u , v)在u , v(u,vV) 之间加一条边(u , v),称为加新边加新边。Gv 从G中去掉v及所关联的一切边，称为删除顶点删除顶点v；GV 从G中去掉V及所关联的一切边，称为删除删除V ；G e 从G中删除e后，将e的两个端点u,v用一个新的顶点w

18、代替,使w关联e以外u,v关联的所有边，称为边边E的的收缩收缩；下面两组数，是否是可以简单图化的？若是，请给出尽量多的非同构的无向简单图以它为度数列。 （1）2，2，2，3，3，6（2）2，2，2，2，3，3不可简单图化。 (2) 可简单图化。共有下面4种非同构情况，它们都是K6的子图. 画出K4的所有非同构的生成子图。 在一次象棋比赛中，n名选手中的任意两名选手之间至多只下一盘，又每人至少下一盘，证明：总能找到两名选手，他们下棋的盘数相同。 证明： 做无向图G=，其中V=v|v为选手 E=(u，v)|u，vVu与v下过棋uv 则G为无向简单图。d(v)：v下棋次数。由已知条件可知，1d(v)

19、n-1。于是 d(v1)，d(v2)，d(vn)只能取从1到n-1中取值。由鸽巢原理，这n个顶点度数至少有 =2个相同，即至少有2个人下棋次数相同。 1nn14.3 图的连通性 一、无向图的连通性 定义定义1 设无向图G=,u,vV，若u,v之间存在通路，则称u,v是连通的是连通的，记作uv. vV，规定vv. 由定义不难看出，无向图中顶点之间的连通关系 =（u,v）|u,vV且u与v之间有通路是自反的，对称的，传递的，因而是V上的等价关系定义定义2 若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图连通图，否则称G是非连通图非连通图或分离图分离图。 完全图Kn(n1)都是连通图，

20、而零图Nn(n2)都是分离图。 定义定义3 设无向图G=，V关于顶点之间的连通关系的商集 V/=V1,V2,Vk，Vi为等价类，称导出子图GVi(i=1,2,k)为G的连通分支连通分支，连通分支数k常记为p(G) 由定义可知，若G为连通图，则p(G)=1，若G为非连通图，则p(G)2，在所有的n阶无向图中，n阶零图是连通分支最多的，p(Nn)=n. 定义定义4 设u,v为无向图G中任意两个顶点，若u v，称u,v之间长度最短的通路为u,v之间的短程线短程线，短程线的长度称为u,v之间的距离距离，记作d(u,v).当u,v不连通时，规定d(u,v)=. 距离有以下性质： 1d(u,v)0，u=v

21、时，等号成立。2具有对称性，d(u,v)=d(v,u)。3满足三角不等式： u,v,wV(G)，则d(u,v)+d(v,w)d(u,w) 在完全图Kn(n2)中，任何两个顶点之间的距离都是1，而在n阶零图Nn(n2)中，任何两个顶点之间的距离都为. 定义定义5 设无向图G=，若存在VV，且V，使得p(G-V)p(G)，而对于任意的V V，均有p(G-V)=p(G)，则称V是G的点割集点割集，若V是单元集，即V=v，则称v为割点割点。如图所示，v2,v4，v3，v5都是点割集，而v3,v5都是割点。注意，v1与悬挂顶点v6不在任何割集中。 定义定义6 设无向图G=，若存在EE，且E，使得p(G-

22、E)p(G)，而对于任意的EE，均有p(G-E)=p(G)，则称E是G的边割集边割集，或简称为割集。若E是单元集，即E=e，则称e为割边割边或桥桥。 在右图中，e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，其中e6,e5是桥。 定义定义7 设G为无向连通图且为非完全图，则称 (G)=min|V|V为G的点割集为G的点连通度点连通度，简称连通度连通度。规定完全图Kn(n1)的点连通度为n-1，又规定非连通图的点连通度为0.又若(G)k，则称G是k-连通图连通图，k为非负整数。若G是k-连通图（k1）则在G中删除任何k-1个顶点后，所得图一定还是连通的

23、。 定义定义8 设G是无向连通图，称 (G)=min|E| E是G的点割集为G的边连通度边连通度。规定非连通图的边连通度为0.又若(G)r，则称G是r边边-连通图连通图。 若G是r边-连通图，则在G中任意删除r-1条边后，所得图依然是连通的 完全图Kn的边连通度为n-1，因而Kn是r边-连通图，0rn-1. 设G1,G2都是n阶无向简单图，若(G1)(G2)，则称G1比G2的点连通程度高。若(G1)(G2)，则称G1比G2的边连通程度高。 例例1 求图中所示各图的点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。 解解 设第i个图的点连通度为i，边

24、连通度为i，i=1,2,8.容易看出，1=1=4，2=2=3，3=3=2，4=4=1，5=1，5=2，6=6=2，7=7=0，8=8=0. 定理定理1 对于任何无向图G，有 (G)(G)(G)例例2 （1）给出一些无向简单图，使得=. （2）给出一些无向简单图，使得. 解解 （1）n阶无向完全图Kn和n阶零图Nn都满足要求。 二、有向图的连通性及其分类 定义定义9 设D=为一个有向图。vi,vjV，若从vi到vj存在通路，则称vi可达可达vj，记作vivj，规定vi总是可达自身的，即vivi.若vivj且vjvi，则称vi与vj是相互可达相互可达的，记作vivj.规定 vi vi. 与都是V上

25、的二元关系，并且不难看出是V上的等价关系。 定义定义10设D=为有向图，vi,vjV，若vivj，称vi到vj长度最短的通路为vi到vj的短程线短程线，短程线的长度为vi到vj的距离，记作d. 与无向图中顶点vi与vj之间的距离d(vi,vj)相比，d除无对称性外，具有d(vi,vj)所具有的一切性质。 定义定义11 设D=为一个有向图。若D的基图是连通图，则称D是弱连通图弱连通图，简称为连通图连通图。若vi,vjV ，vivj与vjvi至少成立其一，则称D是单向连通图单向连通图。若均有vivj，则称D是强连通图强连通图。 强连通图一定是单向连通图，单向连通图一定是弱连通图。 强连通图单向连通

26、图弱连通图 定理定理2 设有向图D=，D=v1,v2,vn.D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。 证证 充分性显然。下面证明必要性。由D的强连通性可知，vivi+1，i=1,2,n-1，设i为vi到vi+1的通路。又因为vnv1，设n为vn到v1的通路，则1,2,n-1,n所围成的回路经过D中每个顶点至少一次。 定理定理3 设D是n阶有向图，D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。 三、扩大路径法及极大路径 设设G=G=为为n n阶无向图，阶无向图，EE，设，设l l为为G G中一条中一条路径，若此路径的始点或终点与通路外的顶点相邻，路径，若此路径的始点或

27、终点与通路外的顶点相邻，就将它们扩到通路中来，继续这一过程，直到最后得就将它们扩到通路中来，继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止，设到的通路的两个端点不与通路外的顶点相邻为止，设最后得到的通路的两个端点不与通路外的顶点相邻为最后得到的通路的两个端点不与通路外的顶点相邻为止，设最后得到的路径为止，设最后得到的路径为l l+k+k（长度为（长度为l l的路径扩大的路径扩大成了长度为成了长度为l l+k+k的路径），称的路径），称l l+k+k为为“极大路径极大路径”，称使用此种方法证明问题的方法为称使用此种方法证明问题的方法为“扩大路径法扩大路径法”。（演示）（演示）

28、 例例3 设G为n（n4）阶无向简单图，(G)3.证明G中存在长度大于或等于4的圈。 证证 不妨设G是连通图，否则，因为G的各连通分支的最小度也都大于或等于3，因而可对它的某个连通分支进行讨论。设u,v为G中任意两个顶点，由G是连通图，因而u,v之间存在通路，由定理14.5的推论可知，u,v之间存在路径，用“扩大路径法”扩大这条路径，设最后得到的“极大路径”为l=v0v1vl，易知l3.若v0与v1相邻，则l(v0,vl)为长度大于或等于4的圈。否则，由于d(v0)(G)3，因而v0除与l上的v1相邻外，还存在l上的顶点vk(k1)和vt(ktl)与v0相邻，则v0v1vkvtv0为一个圈且长

29、度大于或等于4，见下图. 四、二部图及判别定理 定义定义12 设G=为一个无向图，若能将V分成V1和V2（V1V2=V,V1V2=），使得G中的每条边的两个端点都是一个属于V1，另一个属于V2，则称G为二部图二部图（或称二分图，偶图等），称V1和V2为互补顶点子集，常将二部图G记为.又若G是简单二部图，V1中每个顶点均与V2中所有顶点相邻，则称G为完全二部图完全二部图，记为Kr,s，其中r=|V1|,s=|V2|. 注意，注意，n阶零图为二部图。阶零图为二部图。 在图上中所示各图都是二部图，其中，(1)，(2)，(3)为K6的子图，(3)为完全二部图K3,3，常将K3,3画成与其同构的(5)的形式，K3,3是下文中经常遇到的图。(4)是K5的子图，它是完全二部图K2,3，K2,3常画成(6)的形式。 定理定理4 n(n2)阶无向图G是二部图当且仅当G中无奇圈。 证证 必要性。若G中无圈，结论显然成立。若G中有圈，设C为G中任意一圈，令C= vi1vi2vilvi1，易知l2.不妨设vi1V1 ，则vi1,vi2,vil依次交替属于V1，V2，且有vilV-V1=V2，而l必为偶数，于是C为偶圈，由C的任意性可知结论