计算机科学广泛应用于运筹学，信息论，控制论，网络理论，化学生物学，物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用。8.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中元素称为无向边。v4实际中，图是画出来的，画法：用小圆圈表示V中的每一个元素，如果(a,b)E，则在顶点a与b之间连线段。如：adcbe1e1 e2e3e4e5e6e1e2e3e4 e5e6v1v2v3v5有向图：有向图D是一个二元组，其中(1) V是非空集 顶点集 V(D)(2) E是笛卡尔积VV的可重子集，其元素为有向边实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第 二元素。2. 有向图有限图：V，E均为有穷集合零 图：E 平凡图：E 且 |V| = 1(n, m)图：|V| = n 且 |E| = m顶与边关联：如果ek = (vi,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)关联的边的数目(每个环计算两次)，记作：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,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的图为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中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。例8.3 列举下图的一些子图、真子图、生成子图、导出子图。e3e1e2e4e5v3v4v1v2解：自己对照定义做一做！(1) 子图：子图的定义？举例(2) 真子图：举例(3) 生成子图：定义？举例(4) 导出子图：定义？举例补图：给定一个图G = ，以V为顶点集，以所有能使G成为完全图的添加边组成边集的图。记作：G五、补图如:(1)(2)相对补图：设GG, 如果另一个图G = ，满足 (1) E = E E(2) V中仅包含E中的边所关联的结点。则G是子图G相对于G的补图。如：图为的子图，则图(1)(2)(3)为(1)相对于(2)的补图 。图同构：对于G = ，G = ，如果存在 g:VV 满足： (1) 任意边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 8.2 通路、回路、图的连通性通路、回路、图的连通性通路与回路：给定图G = ，设G中顶点与边的交替序列 = 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 互不相同。初级通路一定是简单通路，但简单通路不一定是一条初级通路。基本回路： v0 = vk。例8.6 就下面两图列举长度为5的通路，简单通路，回路，简单回路，再列举长 度为3的基本通路和回路。v1e1e4v2v3v4v5e3e5e2e7e6(1)(2)v5v1e2e5v2v3v4e1e7e3e8e6e4解：试对照定义，自己做一做！如：v1(1)中 v1e1v2e2v5e3v1e1v2e4v3 为v1到v3的通路；v1e1v2e4v3e5v4e7v5e3v1 为v1到v1的一条简单回路；v1e1v2e4v3e5v4e6v2e2v5 为v1到v5的一条简单通路。e1e4v2v3v4v5e3e5e2e7e6(1)(2)中 v1e2v2e5v3e7v4 v1到v4的长度为 了的基本通路；v1e2v2e3v5e1v1 是v1到v1的长度为了的基本回路。(2)v5v1 e2e5v2v3v4e1e7e3e8e6e4二、通路与回路的性质：(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的这些边，至少去掉 一条边后仍是vi到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上的等价关系。(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的点连通度。 由定义知，点连通度即使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的一条通路，则说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中任何两个顶点都是可达的。则得一回路。显然每个顶点在回路中至少出现一次。证明：所以vi到vi+1存在通路，不妨设D中的顶点 为v1,v2,vn，且vn到v1也存在通路，8.3 8.3 图的矩阵表示图的矩阵表示邻接矩阵：设G = 是一个简单图，它有n个顶点，V = v1,v2,vn，令aij = 1 E (或 (vi, vj)E)0 E (或 (vi, vj)E)称A(G) = (aij) 为G的邻接矩阵。一、邻接矩阵及其性质邻接矩