图论图的基本概念学习教案

1、会计学1图论图论(t ln)图的基本概念图的基本概念第一页，共115页。第1页/共115页第二页，共115页。第2页/共115页第三页，共115页。n例如 在多重集合a,a,b,b,b,c,d中，n a,b,c,d的重复度分别为2,3,1,1。第3页/共115页第四页，共115页。第4页/共115页第五页，共115页。其元素称为(chn wi)顶点或结点。（2）E为边集，它是笛卡儿积VV的多重子集，其元素称为(chn wi)有向边，简称边。q可以用图形表示图，即用小圆圈（或实心点）表示顶点(dngdin)，用顶点(dngdin)之间的连线表示无向边，用有方向的连线表示有向边。 第5页/共115

2、页第六页，共115页。 (1) 给定(i dn)无向图G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 给定(i dn)有向图D=，其中 Va,b,c,d，E,。 画出G与D的图形。第6页/共115页第七页，共115页。此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图。n在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记为。第7页/共115页第八页，共115页。G基图(j t)的有向

3、图。第8页/共115页第九页，共115页。n设D为有向图，ekE，n称vi,vj为ek的端点。n若vivj，则称ek为D中的环。n无论在无向图中还是在有向图中，无边(wbin)关联的顶点均称为孤立点。第9页/共115页第十页，共115页。邻接到vj，vj邻接于vi。n若ek的终点(zhngdin)为el的始点，则称ek与el相邻。第10页/共115页第十一页，共115页。n称u|uVEuv为v的先驱元集，记做-D(v)。n称+D(v) 为v的出邻域, -D(v)为v 的入邻域. +D(v)-D(v)为v的邻域，记做ND(v)。n称ND(v)v为v的闭邻域，记做ND(v)。第11页/共115页第

4、十二页，共115页。+D(d ) v2，v5NG(v1) v1，v2，v5IG(v1) e1，e2，e3 c-D(d ) a，cND(d ) a，cND(d ) a，c，d第12页/共115页第十三页，共115页。既不含平行(pngxng)边也不含环的图称为简单图。例如：在图1.1中，(a)中e5与e6是平行(pngxng)边，(b)中e2与e3是平行(pngxng)边，但e6与e7不是平行(pngxng)边。(a)和(b)两个图都不是简单图。第13页/共115页第十四页，共115页。称d+(v)+d-(v)为v的度数，记做d(v)。注:某个点上的有向环要对这个点计算一次入度计算一次出度.第1

5、4页/共115页第十五页，共115页。n在有向图D中，n最大出度 +(D)maxd+(v)|vV(D)n最小出度 +(D)mind+(v)|vV(D)n最大入度 -(D)maxd-(v)|vV(D)n最小入度 -(D)mind-(v)|vV(D)第15页/共115页第十六页，共115页。d+(a)4，d-(a)1(环e1提供(tgng)出度1，提供(tgng)入度1)，d(a)4+15。5，3，+4 (在a点达到)+0(在b点达到)-3(在b点达到)-1(在a和c点达到) 第16页/共115页第十七页，共115页。n n12)(iimvd说明任何无向图中，各顶点度数之和等于边数的两倍。证明G中

6、每条边(包括环)均有两个(lin )端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。 第17页/共115页第十八页，共115页。否则当 , 0),(),( , 1),(GEvvvvjiji第18页/共115页第十九页，共115页。n两边消去(xio q)2t,得到结论。第19页/共115页第二十页，共115页。定理(dngl)1.2 设D为任意有向图，Vv1,v2,vn，|E|m，则 n nn nn n111)()(,2)(iiiiiimvdvdmvd且第20页/共115页第二十一页，共115页。Vvvdm)(221)()(VvVvvdvd由于(yuy)2m

7、和2)(Vvvd，所以1)(Vvvd为偶数，但因V1中顶点度数为奇数，所以|V1|必为偶数。第21页/共115页第二十二页，共115页。解。(2)为了建立一个图模型，需要决定顶点和边分别代表什么。(3)在一个图模型中，边经常代表两个顶点之间的关系。第22页/共115页第二十三页，共115页。仅当两个面有公共边界线时在相应的两顶间连一条边， 于是|V(G)|是奇数，而且对每个顶点v,d(v)是奇数,则所有的顶点的度数之和为奇数， 与握手定理矛盾。第23页/共115页第二十四页，共115页。特别地，若所得图是简单图，则称d是可简单图化的。类似地，设D为一个n阶有向图，Vv1,v2,vn，称d(v1

8、)，d(v2)，d(vn)为D的度数列，另外称d+(v1)，d+(v2)，d+(vn)与d-(v1)，d-(v2)，d-(vn)分别为D的出度列和入度列。第24页/共115页第二十五页，共115页。按字母顺序(shnx)，度数列，出度列，入度列分别为5,3,3,34,0,2,11,3,1,2第25页/共115页第二十六页，共115页。n n1)2(mod0iid证明必要性。由握手定理显然得证。充分性。由已知条件可知，d中有偶数个奇数(j sh)度点。奇数(j sh)度点两两之间连一边，剩余度用环来实现。5331第26页/共115页第二十七页，共115页。第27页/共115页第二十八页，共115

9、页。第28页/共115页第二十九页，共115页。只能最多接收k次）。第29页/共115页第三十页，共115页。不可图化。(2) (5,4,3,2,2)可图化，不可简单图化。若它可简单图化，设所得图为G，则(G)max5,4,3,2,25，这与定理1.4矛盾。第30页/共115页第三十一页，共115页。因而(yn r)(3)中序列也不可简单图化。(4) (d1,d2,dn)，d1d2dn1 且 为偶数。 n n1iid可图化，不可(bk)简单图化。原因?第31页/共115页第三十二页，共115页。第32页/共115页第三十三页，共115页。 设G1，G2为两个无向图，若存在双射函数f：V1V2，

10、对于vi,vjV1，(vi,vj)E1当且仅当(f(vi),f(vj)E2，并且 (vi,vj)与(f(vi),f(vj)的重数相同，则称G1与G2是同构的，记做G1G2。说明(1) 类似地，可以定义两个有向图的同构。(2) 图的同构关系(gun x)看成全体图集合上的二元关系(gun x)。(3) 图的同构关系(gun x)是等价关系(gun x)。(4) 在图同构的意义下，图的数学定义与图形表示 是一一对应的。 第33页/共115页第三十四页，共115页。彼得森(Petersen)图第34页/共115页第三十五页，共115页。第35页/共115页第三十六页，共115页。第36页/共115页

11、第三十七页，共115页。n阶竞赛图。第37页/共115页第三十八页，共115页。1)/2K53阶有向完全(wnqun)图4阶竞赛图第38页/共115页第三十九页，共115页。第39页/共115页第四十页，共115页。注: 定义中一定是先要保证G是图这个前提.第40页/共115页第四十一页，共115页。第41页/共115页第四十二页，共115页。GE1为(3)中图所示。第42页/共115页第四十三页，共115页。(1)为自补图(2)和(3)互为补图第43页/共115页第四十四页，共115页。除(shnch)V 中所有顶点，称为删除(shnch)V 。(3)设边e(u,v)E，用Ge表示从G中删除

12、(shnch)e后，将e的两个端点u,v用一个新的顶点w(或用u或v充当w)代替，使w关联除e外u,v关联的所有边，称为边e的收缩。(4)设u,vV(u,v可能相邻，也可能不相邻)，用G(u,v)(或G+(u,v)表示在u,v之间加一条边(u,v)，称为加新边。说明 在收缩边和加新边过程中可能产生环和平行边。第44页/共115页第四十五页，共115页。GGe5Ge1, e4Gv5Gv4, v5Ge5第45页/共115页第四十六页，共115页。若的所有顶点(除vi0与vij可能相同外)各异，所有边也各异，则称为初级通路或路径，又若vi0vil，则称为初级回路或圈。将长度为奇数的圈称为奇圈，长度为

13、偶数的圈称为偶圈。第46页/共115页第四十七页，共115页。n情况，即回路也是通路，又初级通路(回路)是简单通路(回路)，但反之不真。第47页/共115页第四十八页，共115页。(xli)()，可称这种表示法为混合表示法。第48页/共115页第四十九页，共115页。即在上存在vs到自身(zshn)的回路Csk,在上删除Csk上的一切边及除vs外的一切顶点，得v0e1v1e2vkes+1 elvl ,仍为vi到vj的通路，且长度至少比减少1。若还不满足要求，则重复上述过程，由于G是有限图，经过有限步后，必得到vi到vj长度小于或等于n-1的通路。第49页/共115页第五十页，共115页。第50

14、页/共115页第五十一页，共115页。第51页/共115页第五十二页，共115页。如果只考虑起点(终点)的差异，而不考虑顺时针逆时针的差异，应有3种不同的圈，当然它们都是同构的，画出图来只有一个。第52页/共115页第五十三页，共115页。第53页/共115页第五十四页，共115页。第54页/共115页第五十五页，共115页。kp(G)。说明 若G为连通图，则p(G)1。若G为非连通图，则p(G)2。在所有的n阶无向图中，n阶零图是连通分支最多的，p(Nn)n。第55页/共115页第五十六页，共115页。nG连通分支， 则存在一个连通分支， 其顶点数小于等于k, 则在这个连通分支上最大度数不超

15、过k-1, 矛盾第56页/共115页第五十七页，共115页。第57页/共115页第五十八页，共115页。则d(u,v)+d(v,w)d(u,w)说明：在完全图Kn(n2)中，任何两个顶点之间的距离都是1。在n阶零图Nn(n2)中，任何两个顶点之间的距离都为。第58页/共115页第五十九页，共115页。第59页/共115页第六十页，共115页。v2,v4,v3,v5都是点割集v3,v5都是割点v1与v6不在任何(rnh)割集中。 实际上，点割集是若删去它们就会使图不连通的顶点的集合，而割点是若删去此一顶点就会使图不连通的顶点。第60页/共115页第六十一页，共115页。e6,e5,e2,e3,e

16、1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，e6,e5是桥。 实际上，边割集是若删去它们就会使图不连通的边的集合(jh)，而割边是若删去此一边就会使图不连通的边。第61页/共115页第六十二页，共115页。若 (G)k，则称G是k-连通图，k为非负整数(zhngsh)。说明 (G)有时简记为。上例中图的点连通度为1，此图为1-连通图。K5的点连通度K4，所以K5是1-连通图，2-连通图，3-连通图，4-连通图。若G是k-连通图（k1）则在G中删除任何k-1个顶点后，所得图一定还是连通的。第62页/共115页第六十三页，共115页。完全图Kn的边连通度为n-1，因而Kn是r

17、边-连通图，0rn-1。平凡(pngfn)图G 由于E 则01，它只能是1边-连通图。第63页/共115页第六十四页，共115页。K4K3K2K1K=1 =2K2K0K0第64页/共115页第六十五页，共115页。(lintng)图，k1,2。(4)是1-连通(lintng)图，1边-连通(lintng)图。(5)是1-连通(lintng)图，k边-连通(lintng)图，k1,2。(6)是k-连通(lintng)图，k边-连通(lintng)图，k1,2。(7)是0-连通(lintng)图，0边-连通(lintng)图。(8)是0-连通(lintng)图，0边-连通(lintng)图。点连通

18、(lintng)程度为(1)(2)(3)(6)(4)(5)(7)(8)。边连通(lintng)程度为(1)(2)(3)(5)(6)(4)(7)(8)。第65页/共115页第六十六页，共115页。，若vivj，称vi到vj长度(chngd)最短的通路为vi到vj的短程线，短程线的长度(chngd)为vi到vj的距离，记作d 。说明 与无向图中顶点vi与vj之间的距离d(vi,vj)相比，d除无对称性外，具有d(vi,vj)所具有的一切性质。第66页/共115页第六十七页，共115页。强连通(lintng)图单向连通图弱连通图第67页/共115页第六十八页，共115页。路，则1,2,n-1,n所围

19、成的回路经过D中每个顶点至少一次。设D是n阶有向图，D是单向连通图当且仅当D中存在(cnzi)经过每个顶点至少一次的通路。第68页/共115页第六十九页，共115页。w, u,w), (w,v)Gcu, v在Gc中连通。第69页/共115页第七十页，共115页。第70页/共115页第七十一页，共115页。径)，称l+k为“极大路径”，n称使用此种方法证明问题的方法为“扩大路径法”。n有向图中可以类似地讨论，只须注意，在每步扩大中保持(boch)有向边方向的一致性。第71页/共115页第七十二页，共115页。第72页/共115页第七十三页，共115页。第73页/共115页第七十四页，共115页。

20、14.5u,v间存在路径，用“扩大路径法”扩大这条路径，设最后得到的“极大路径”为lv0v1vl，易知l3。若v0与vl相邻，则l(v0,vl)为长度大于或等于4的圈。否则，由于d(v0)(G)3，因而(yn r)v0除与l上的v1相邻外，还存在l上的顶点vk(k1)和vt(kt l )与v0相邻，则v0v1vkvtv0为一个圈且长度大于或等于4第74页/共115页第七十五页，共115页。第75页/共115页第七十六页，共115页。第76页/共115页第七十七页，共115页。第77页/共115页第七十八页，共115页。GKr,sr|V1|，s|V2|。说明 n阶零图为二部图。第78页/共115

21、页第七十九页，共115页。K6的子图K6的子图K3,3K2,3K3,3K2,3第79页/共115页第八十页，共115页。又因为v0V1，所以vkV2，因而k为奇数，故C的长度为偶数。第80页/共115页第八十一页，共115页。e，设v0到vi,vj的短程线分别为i,j，则它们的长度d(v0,vi),d(v0,vj)都是偶数，于是(ysh)ije中一定含奇圈，这与已知条件矛盾。类似可证，V2中也不存在相邻的顶点，于是(ysh)G为二部图。第81页/共115页第八十二页，共115页。10000110000011001112M(G)第82页/共115页第八十三页，共115页。第83页/共115页第八

22、十四页，共115页。第84页/共115页第八十五页，共115页。的终点为不关联为的始点为jijijiijevevevm101则称(mij)nm为D的关联矩阵，记作M(D)。1-1-1-00110000011-100011-M(D)第85页/共115页第八十六页，共115页。1101000100120000A第86页/共115页第八十七页，共115页。第87页/共115页第八十八页，共115页。第88页/共115页第八十九页，共115页。第89页/共115页第九十页，共115页。第90页/共115页第九十一页，共115页。第91页/共115页第九十二页，共115页。第92页/共115页第九十三页

23、，共115页。第93页/共115页第九十四页，共115页。第94页/共115页第九十五页，共115页。pij1 vi 可达 vj0 否则(fuz)称(pij)nn为D的可达矩阵(j zhn)，记作P(D)，简记为P。 1101101111110001P第95页/共115页第九十六页，共115页。第96页/共115页第九十七页，共115页。G1-G2。(3)称以E1E2为边集，以E1E2中边关联的顶点(dngdin)组成的集合为顶点(dngdin)集的图为G1与G2的交图，记作G1G2。(4)称以E1 E2为边集（为集合之间的对称差运算），以E1 E2中边关联的顶点(dngdin)组成的集合为顶

24、点(dngdin)集的图为G1与G2的环和，记作G1 G2。第97页/共115页第九十八页，共115页。G1 G2(G1G2)-(G1G2)第98页/共115页第九十九页，共115页。第99页/共115页第一百页，共115页。 Dijkstra算法能求一个顶点到另一顶点最短路径。它是由Dijkstra于1959年提出的。实际它能出始点到其它所有顶点的最短路径。 Dijkstra算法是一种标号法：给赋权图的每一个顶点记一个数，称为顶点的标号（临时标号，称T标号，或者固定标号，称为P标号）。T标号表示从始顶点到该标点的最短路长的上界；P标号则是从始顶点到该顶点的最短路长。 Dijkstra算法步骤

25、(bzhu)如下：第100页/共115页第一百零一页，共115页。111(1)P()0(2,3, )T()jjjvd vvjnd vl 给给顶顶点点 标标 标标号号，给给顶顶点点标标 标标号号；000001(2)()()()jjjjjjj jjTd vlvTPTTvTd vd vlvT 在在所所有有 标标号号中中取取最最小小值值，譬譬如如，则则把把的的 标标号号改改为为 标标号号，并并重重新新计计算算具具有有 标标号号的的其其它它各各顶顶点点的的 标标号号：选选顶顶点点 的的 标标号号与与中中较较小小者者作作为为 的的新新的的 标标号号。(3)P重重复复上上述述步步骤骤，直直到到目目标标顶顶点点的的标标号号改改为为 标标号号。第101页/共115页第一百零二页，共115页。v1v2v3v4v5v6v7v8v9v10v112817615129341369272149第102页/共115页第一百零三页，共115页。v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490281第103页/共115页第一百零四页，共115页。v1v2v3v4v5v6v7v8v9v10v112817615129341369272149028101第104页/共115页第一百零五页，共115页。v1v2v