离散数学图的基本概论

1、图的基本概念,计算机科学广泛应用于运筹学，信息论，控制论，网络理论，化学生物学，物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用,8.1 无向图及有向图,称a,b | aAbB 为A与B的无序积，记作：A&B,习惯上，无序对a,b改记成(a, b,有序组(a,b)均用,无序积：设A，B为二集合,一、基本图类及相关概念,1. 无向图,无向图：无向图G是一个二元组，其中,1) V是一个非空集 顶点集V(G)，每个元素为顶点或结点,2) E是无序积V & V的可重子集(元素可重复出现)，E 边集E(G)，E中元素称为无向边

2、,v4,实际中，图是画出来的，画法：用小圆圈表示V中的每一个元素，如果(a,b)E，则在顶点a与b之间连线段,如,a,d,c,b,e1,e1,e2,e3,e4,e5,e6,e1,e2,e3,e4,e5,e6,v1,v2,v3,v5,有向图：有向图D是一个二元组，其中,1) V是非空集 顶点集 V(D,2) E是笛卡尔积VV的可重子集，其元素为有向边,实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二元素,2. 有向图,有限图：V，E均为有穷集合,零 图：E,平凡图：E 且 |V| = 1,n, m)图：|V| = n 且 |E| = m,顶与边关联：如果ek = (v

3、i,vj) E，称ek与vi关联，或ek与vj关联,3. 相关概念,顶与顶相邻：如果ek = (vi,vj) E，称vi与vj相邻,环： ek = 中，若 vi = vj，则ek称为环,边与边相邻：如果ek和ei至少有一个公共顶点关联，则称ek与ei相邻,若ek为有向边，则称vi邻接到vj, vj邻接于vi,孤立点：无边关联的顶点,平行边：无向图中，关联一对结点的无向边多于一条，平行边的条数为重数,多重图：包含平行边的图,有向图中，关联一对顶点的无向边多于一条，且始、终点相同,简单图：既不包含平行边又不包含环的图,度：(1) 在无向图G = 中，与顶点v(vV)关联的边的数目(每个环计算两次)

4、，记作：d(v,二、度,2) 在有向图D = 中，以顶点v(vV)作为始点的边的数目，称为该顶点的出度，记作： d+(v,出度与入度之和，称为顶点v的度,度是图的性质的重要判断依据,d(v) = d+(v)+ d(v,以顶点v作为终点的边的数目，称为该顶点的入度，记作：d(v,最大度： (G) = max d(v) | vV,最小度： (G) = min d(v) | vV,度与边数的关系：在任何图中，顶点度数的总和等于边数之和的两倍,握手定理的推论：任何图中，度为奇数的顶点个数一定为偶数,握手定理,出度与入度的关系：在有向图中，各顶点的出度之和等于各顶点的入度之和,度数序列：设V = v1,

5、v2,vn为图G的顶点集,称(d(v1), d(v2), d(vn)为G的度数序列,度数序列之和必为偶数(,例8.1 (3,3,2,3)，(5,2,3,1,4)能成为图的度数序列吗？为什么,解：由于这两个序列中，奇数个数均为奇数，由握手定理知，它们不能成为图的度数序列,例8.2 已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？为什么,解：图中边数 m=10，由握手定理知，G中各顶点度数之和为20,4个3度顶点占去12度，还剩8度,若其余全是2度顶点, 则需要4个顶点来占用8度，所以G至少有8个顶点,正则图：各顶点的度都相同的图为正则图,各顶点的度均为k的

6、图为k次正则图,完全图,1) 设G = 是n阶的无向简单图，如果G中任何一个顶点都与其余n1个顶点相邻，则G为无向完全图，记作：Kn,三、正则图与完全图,2) 设D = 是n阶的有向简单图，如果D中任意顶点u，vV(uv)，即有有向边 ，又有有向边，则称D为n阶有向完全图,如,四、子图与母图,1) G = ， G =,若VV， EE，则G是G的母图， G是G的子图，记作： G G,2) 若GG 且 V=V，则G是G的生成子图,3) 设V1V，且V1，以V1为顶点集，以2端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图,4) 设E1E，且E1，以E1为顶点集，以E1中边关联的顶点的

7、全体为顶点集的G的子图，称为E1导出的导出子图,例8.3 列举下图的一些子图、真子图、生成子图、导出子图,e3,e1,e2,e4,e5,v3,v4,v1,v2,解：自己对照定义做一做,1) 子图：子图的定义？举例,2) 真子图：举例,3) 生成子图：定义？举例,4) 导出子图：定义？举例,补图：给定一个图G = ，以V为顶点集,以所有能使G成为完全图的添加边组成边集的图。记作：G,五、补图,如,相对补图：设GG, 如果另一个图G = ，满足 (1) E = E E,2) V中仅包含E中的边所关联的结点,则G是子图G相对于G的补图,图同构：对于G = ，G = ，如果存在 g:VV 满足,1)

8、任意边e = (vi,vj)E，当且仅当e = (g(vi),g(vj)E,2) e与e的重数相同,则说G G,由于同构图顶点之间一一对应，边之间一一对应，关联关系对应相同，所以可以看成同一个图,六、同构图,例8.4 画出4个顶点3条边的所有可能非同构的无向简单图,解：直观上容易看出，下面三个图是4个顶点3条边的所有非同构的无向简单图,例8.5 画出3个顶点2条边的所有可能非同构的有向简单图,解： 3个顶点2条边的无向简单图只有一个,由这个图可派生出下列4个非同构的有向简单图,课堂练习：画出4个顶点4条边的无向简单图,8.2 通路、回路、图的连通性,通路与回路：给定图G =,设G中顶点与边的交

9、替序列 = v0 e1 v1 e2 el vl 满足：vi1vi是ei的端点，(G为有向图时, 要求vi1, vi分别为ei的始点、终点)，i = 1,2, l，则为顶点v0到vl的通路,中边的数目l称为的长度,v0 = vl时，称为回路,一、通路与回路的概念,简单通路： = v0 e1 v1 e2 ek vk为通路且边e1 e2 ek 互不相同，又称之为迹，可简用v0 v1 vk 来表示,简单回路 (v0 = vk)又称为闭迹,初级通路或基本通路： = v0 e1 v1 e2 ek vk为通路且顶点v0 v1 vk 互不相同,初级通路一定是简单通路，但简单通路不一定是一条初级通路,基本回路：

10、 v0 = vk,例8.6 就下面两图列举长度为5的通路，简单通路，回路，简单回路，再列举长度为3的基本通路和回路,v1,e1,e4,v2,v3,v4,v5,e3,e5,e2,e7,e6,1,2,v5,v1,e2,e5,v2,v3,v4,e1,e7,e3,e8,e6,e4,解：试对照定义，自己做一做！如,v1,1)中 v1e1v2e2v5e3v1e1v2e4v3 为v1到v3的通路,v1e1v2e4v3e5v4e7v5e3v1 为v1到v1的一条简单回路,v1e1v2e4v3e5v4e6v2e2v5 为v1到v5的一条简单通路,e1,e4,v2,v3,v4,v5,e3,e5,e2,e7,e6,

11、1,2)中 v1e2v2e5v3e7v4 v1到v4的长度为 了的基本通路,v1e2v2e3v5e1v1 是v1到v1的长度为了的基本回路,2,v5,v1,e2,e5,v2,v3,v4,e1,e7,e3,e8,e6,e4,二、通路与回路的性质,1) 在一个n阶图中，如果从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于n1的通路,如果Ln1，则此通路的顶点数L+1n，从而必有顶点vs，它在序列中不止出现一次，即有序列vi vs vs vj,证明：设vi vk vj为vi到vj的长度为L的一条通路，则序列中必有L+1个顶点,在路中去掉vs到vs的这些边，至少去掉一条边后仍是v

12、i到vj的一条通路,此通路比原来,如此重复下去，必可得到一条从vi到vj的不多于n1条边的通路,通路的长度至少少1,2) 在n阶图中，如果从vi到vj (vivj)存在通路，则必存在从vi到vj 的长度小于等于 n1的基本通路,3) 在n阶图中，如果存在从vi到自身的回路，则从vi 到自身存在长度等于n的回路,4) 在n阶图中，如果从vi到自身存在一条简单回路，则从vi 到自身存在长度等于n的初级回路,两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路,连 通 图：G 中任何两个顶点是连通的；否则是分离图,三、图的连通性,连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系,

13、1) 自反性：由于规定任何顶点到自身总是连通的,证明,2) 对称性：无向图中顶点之间的连通是相互的,3) 传递性：由连通性的定义可知,连通分支：无向图G中每个划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G) = 1为连通图,点割集：无向图G = 为连通图，如果VV，且在G中删除V中所有顶点(包括与该顶点关联的边)后所得子图是不连通的或是平凡图，而删除V中任何真子集中的顶点时，所得子图仍连通，则V是G的点割集,如果点割集中只有一个顶点，该点为割点,四、连通图的连通度,点连通度：G为无向连通图，记k(G) = min|V| V是G的点割集，称k(G)为G的点连通度,由定义知，点连通

14、度即使G不连通的需删除顶点的最少数目,完全图Kn的连通度k(G) = n1,存在割点的连通图连通度为1,分离图的连通度为0,边割集：设无向图G = 连通，边集EE，在G中删除E中所有边后所得子图不连通，而删除E中的任何子集中的边后，所得子图仍连通，则E为G的边割集,如果边割集中只有一边时，该边为割边(或桥,边连通度：设G为无向连通图，记(G) = min| E | E是G的边割集， (G)为G的边连通度,连通度的性质：k(G) (G) (G,五、有向图的连通性,1) 如果有向图 D = 中所有有向边的方向去掉后所得图为无向连通图，则说D为弱连通图,2) u,vV，如果存在u到v的一条通路，则说

15、u可达v,3) 弱连通图中， 任何一对顶点之间，至少有一顶点可达另一个顶点，则 是单向连通的,任何两个顶点之间互相可达，称强连通,有向连通图的性质,1) 强连通一定单向连通，单向连通一定弱连通。反过来都不成立,2) 有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次,充分性) 如果D中存在回路C，它经过D中的每个顶点至少一次，则D中的任意两个顶点都在回路中，所以，D中任意两个顶点都是可达的，因而D是强连通的,证明,因为vi可达vi+1, i=1,2,，n1，让这些通路首尾相连,2) 有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次,必要性) D是强连通的，则D中任

16、何两个顶点都是可达的,则得一回路。显然每个顶点在回路中至少出现一次,证明,所以vi到vi+1存在通路,不妨设D中的顶点,为v1,v2,vn,且vn到v1也存在通路,8.3 图的矩阵表示,邻接矩阵：设G = 是一个简单图，它有n个顶点，V = v1,v2,vn，令,aij,1 E (或 (vi, vj)E,0 E (或 (vi, vj)E,称A(G) = (aij) 为G的邻接矩阵,一、邻接矩阵及其性质,邻接矩阵的特性：在无向图中,1) 邻接阵是对称阵,2) 同一行或者同一列的元素和为对应顶点的度数,3) 矩阵中所有元素的和为边数的2倍,在有向图中,1) 同一行的元素和为对应顶点的出度,2) 同

17、一列的元素和为对应顶点的入度,3) aij = 2 m (边的数目,邻接矩阵可推广到多重图或带权图，这时令aij为vi到vj的边的重数或边上的权值W(vi, vj,邻接阵多用于有向图,关联矩阵,1) 设G = 为(n,m)无向图, V = v1,v2,vn, E = e1, e2, em, 令,mij,1,0,称M(G) = (mij)nxm为G的关联矩阵,vi 关联 ej,vi 不关联 ej,二、关联矩阵及其性质,2) 设D = 是有向图且无环，令,mij,1,0,则称M(D) = (mij)nxm为D的关联矩阵,1,D中 vi 是 ej 的始点,vi 与 ej 不关联,vi 是 ej 的终

18、点,无向图的关联矩阵的性质,握手定理,有向图的关联矩阵的性质,由mij的定义知,通路数与回路数的矩阵算法,1) 设A是有向图D的邻接矩阵，V = v1,v2,vn， Al (l1)中元素aij(l)为vi到vj长度为l的通路数,通路总数,回路数,三、应用,1. 求通路数与回路数,2) 设A是有向图D的邻接矩阵，B1 = A，B2 = A+A2,，Br = A+A2+Ar，则Br中元素bij(r) 为D中vi到vj长度小于等于 r 的通路数,2. 求可达矩阵,可达矩阵,设D = 为一有向图，V = v1,v2,vn，令,pij,1,0,i j,pii = 1 i = 1,2,n,称(pij)nx

19、n 为D的可达矩阵,vi 可达 vj,否则,例. 求下图的可达矩阵，判断它是否为强连通图,V1,V4,V2,V3,V5,解：1. 写出邻接矩阵,2. 计算 A2, A3, A4, A5,3. 计算 B = A +A2 + A3 + A4 + A5 , 并求出,可达矩阵的求法：由邻接矩阵A计算A2,A+A2, A+A2+A(n1) = B = (bij(n1)nn,pij,1 bij(n1) 0,0 bij(n1) = 0,则 i j,pii = 1,即得可达矩阵 P(D) = (pij)nxn,8.4 最短路径问题,带权图：对于有向图或无向图的每条边附加一个实数w(e)，则得带权图,如果G1是

20、带权图G的子图，称,w(e) 为边e上的权(当e = 时，权记作wij)，记作：G =,一、带权图及其最短路径问题,G = 为带权图，且G中各边带的权均大于等于0，从顶点u到顶点v的所有通路中求带权最小的通路问题，称为最短路径问题,最短路径问题,如果v1v2 vn1vn是v1到vn的最短路径，则v1v2 vn1也必然是v1从到vn1的最短路径,求最短路径的标号法的基本思想,标号法：(1) 符号说明,i) li(r)*为顶点v1到顶点vi最短路径的权,ii) lj(r)为v1到vj最短路径权的上界，如果vj获得lj(r) ，称vj在第r步获得t标号lj(r) (r0,如果顶点vi获得了标号li(

21、r)*，称vi在第r步获得p标号li(r,iii) Pr = v | v已获得p标号，称之为第r步通过集 (r0,iv) Tr = V Pr 称之为第r步未通过集 (r0,二、求最短路径问题的标号法,2) 算法,开始，r0，v1获p标号： l1(0)* = 0，P0 = v1，T0 = Vv1， vj (j1)的t标号,lj(0) = w1j,w1j 0 v1与vj相邻,v1与vj 不相邻,修改通过集和未通过集：Pr = Pr1vi， Tr = Tr1vi,step1. 求下一个p标号顶点,顶点vi处，表明vi获得p标号,查Tr：若Tr = ，则算法结束，否则转step2,将lj(r)*标在相

22、应,step2. 修改Tr中各顶点的t标号,lj(r) = minlj(r1) , li(r)* +wij， li(r)* 是刚刚获得p标号顶点的p标号,令r r+1，转step1,例8.7 求下图中顶点v0与v5之间的最短路径,v0,v2,v1,v4,v3,v5,1,2,1,4,7,5,3,2,6,解：利用标号法算法解此题,开始，r0，v0获 p标号： l0(0)* = 0,l1(0) = w01 = 1,通过集P0 = v0，未通过集T0 = v1， v2 ，v3， v4，v5,l2(0) = w02 = 4,l4(0) = = l5(0,l3(0) = w03 =,未通过集的 t 标号,

23、第一步：r = 1，计算 = l1(1)* = 1，所以i=1,P1 = v0, v1， T1 = v2,v3 ,v4,v5,修改未通过集的t标号,l2(1) = minl2(0), l1(1)* + w12 = min4,3 = 3,l3(1) = minl3(0), l1(1)* + w13 = min,8 = 8,l4(1) = minl4(0), l1(1)* + w14 = 6,l5(1) = minl5(0), l1(1)* + w15 =,vi获 p标号l1(1,修改通过集与未通过集,修改通过集与未通过集 P2 = v0, v1, v2，T2 = v3 ,v4,v5,修改未通过集

24、的t标号,l3(2) = minl3(1), l2(2)* + w23 = min8,3+ = 8,l4(2) = minl4(1), l2(2)* + w24 = min6,3+1 = 4,l5(2) = minl5(0), l2(2)* + w25 = min,3+ =,修改通过集与未通过集 P3 = v0, v1, v2 ,v4,T3 = v5 ,v3,修改未通过集的t标号,l3(3) = minl3(2), l4(3)* + w43 = min8,4+3 = 7,l5(3) = minl5(2), l4(3)* + w45 = min,4+6 = 10,修改通过集与未通过集 P4 = v0, v1, v2 ,v4 ,v3,T4 = v5,修改未通过集的t标号,l5(4) = min