《离散数学图的基本概论》由会员分享，可在线阅读，更多相关《离散数学图的基本概论（78页珍藏版）》请在金锄头文库上搜索。
1、计计算算机机科科学学广广泛泛应应用用于于运运筹筹学学，信信息息论论，控控制制论论，网网络络理理论论，化化学学生生物物学学，物物理理学学。原原因因在在于于这这些些学学科科的的许许多多实实际际问问题题和和理理论论问问题题可可以以概概括括为为图图论论。第第八八、九九章章介介绍绍与与计计算算机机科科学学关关系系密密切切的的图图论论内内容容及及其其在在实实际际中的应用。中的应用。8.1 8.1 无向图及有向图无向图及有向图称称a,b | a A b B 为为A与与B的无序积，记作：的无序积，记作：A&B。习惯上，无序对习惯上，无序对a,b改记成改记成(a, b)有序组有序组(a,b)均用均用无序积无序积
2、：设设A，B为二集合，为二集合，一、基本图类及相关概念1. 无向图无向图：无向图无向图G是一个二元组是一个二元组，其中其中(1) V是一个非空集 顶点集V(G)，每个元素为顶点或结点顶点或结点；(2) E是无序积V & V的可重子集可重子集(元素可重复出现)，E 边集E(G)，E中元素称为无向边无向边。v4 实际中，图是画出来的，画法：用小圆圈表示V中的每一个元素，如果(a,b)E，则在顶点a与b之间连线段。如：adcbe1e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5有向图有向图：有向图有向图D是一个二元组是一个二元组，其中其中(1) V是非空集是非空集 顶点集顶点集 V(
3、D)(2) E是笛卡尔积是笛卡尔积V V的可重子集，的可重子集，其元素为有向边其元素为有向边 实际中，画法同无向图，只是要根据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称为环。称为环。 边与边相邻边与边相邻：如果如
4、果ek和和ei至少有一个公共顶点关联，至少有一个公共顶点关联，则称则称ek与与ei相邻相邻。若若ek为有向边，则称为有向边，则称vi邻接到邻接到vj, vj邻接于邻接于vi 。孤立点孤立点：无边关联的顶点。无边关联的顶点。平行边平行边：无向图中，关联一对结点的无向边无向图中，关联一对结点的无向边多于一条，平行边的条数为多于一条，平行边的条数为重数重数；多重图多重图：包含平行边的图。包含平行边的图。有向图中，关联一对顶点的无向边有向图中，关联一对顶点的无向边多于一条，且始、终点相同。多于一条，且始、终点相同。简单图简单图：既不包含平行边又不包含环的图。既不包含平行边又不包含环的图。度：(1) 在
5、无向图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) | v V最小度最小度： (G) = min d(v) | v V度与边数的关系度与边数的关系：在任何图中，顶点度数的在任何图中，顶点度数的总和等于边数之和的两倍。总和等于边数之和的两倍。握手定理
6、的推论握手定理的推论：任何图中，度为奇数的顶任何图中，度为奇数的顶点个数一定为偶数。点个数一定为偶数。(握手定理握手定理)出度与入度的关系出度与入度的关系：在有向图中，各顶点的出在有向图中，各顶点的出度之和等于各顶点的入度之和。度之和等于各顶点的入度之和。度数序列度数序列：设设V = v1,v2,vn为图为图G的顶点集，的顶点集，称称(d(v1), d(v2), d(vn)为为G的度数的度数序列。序列。度数序列之和必为偶数度数序列之和必为偶数(?)。例例8.1 (3,3,2,3)，(5,2,3,1,4)能成为图的度数序列吗？为什么？解：解：由于这两个序列中，奇数个数均为奇数，由握手定理知，它们
7、不能成为图的度数序列。例例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为
8、无向完全图，记作：为无向完全图，记作：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导出的导出子图导出子图。例
9、例8.3 列举下图的一些子图、真子图、生成子图、导出子图。e3e1e2e4e5v3v4v1v2解解：自己对照定义做一做！(1) 子图：子图的定义？举例(2) 真子图：举例(3) 生成子图：定义？举例(4) 导出子图：定义？举例补图补图：给定一个图给定一个图G = ，以，以V为顶点集，为顶点集，以所有能以所有能使使G成为完全图成为完全图的添加边组成边的添加边组成边集的图。记作：集的图。记作：G五、补图如:(1)(2)相对补图相对补图：设：设G G, 如果另一个图如果另一个图G = ，满足满足 (1) E = E E(2) V中仅包含中仅包含E中的边所关联的结点。中的边所关联的结点。则则G是子图是
10、子图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条边的所
11、有可能非同构的有向简单图。解：解： 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
12、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
13、 为v1到v3的通路；v1e1v2e4v3e5v4e7v5e3v1 为v1到v1的一条简单回路；v1e1v2e4v3e5v4e6v2e2v5 为v1到v5的一条简单通路。e1e4v2v3v4v5e3e5e2e7e6(1)(2)中 v1e2v2e5v3e7v4 v1到v4的长度为 了的基本通路；v1e2v2e3v5e1v1 是v1到v1的长度为了的基本回路。(2)v5v1e2e5v2v3v4e1e7e3e8e6e4二、通路与回路的性质：(1) 在一个n阶图中，如果从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于n1的通路。如 果 Ln1， 则此通路的顶点数L+1n，从而必有
14、顶点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到自身存在一条简单回路
15、，则从vi 到自身存在长度等于长度等于n的初级回路的初级回路。两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。连 通 图：G 中任何两个顶点是连通的；否则是分离图。三、图的连通性连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系等价关系。(1) 自反性：由于规定任何顶点到自身总是连通的；证明证明：(2) 对称性：无向图中顶点之间的连通是相互的；(3) 传递性：由连通性的定义可知。连通分支：无向图G中每个划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G) = 1为连通图。点割集：无向图G = 为连通图，如果VV，且在G中删除V中所有顶点(包括与该顶点关联的边
16、)后所得子图是不连通的或是平凡图，而删除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的边割集。如果边割集中只有一边时，该边为割
17、边(或桥)边连通度：设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中存在一条回路，它至
18、少经过每个顶点一次。(充分性) 如果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个顶点
19、，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) 同一列的元素和为对应顶点的入度(3) aij = 2 m (边的数目) 邻接矩阵可推广到多重图或带权图，这时令aij为vi到vj的边的重数或边上的权值W(vi, vj)。邻接阵多用于有向图。关联矩阵：(
20、1) 设G = 为(n,m)无向图, V = v1,v2,vn, E = e1, e2, em, 令：mij = 10称M(G) = (mij)nxm为G的关联矩阵关联矩阵。vi 关联 ejvi 不关联 ej二、关联矩阵及其性质(2) 设D = 是有向图且无环，令：mij = 10则称M(D) = (mij)nxm为D的关联矩阵关联矩阵。1D中 vi 是 ej 的始点vi 与 ej 不关联vi 是 ej 的终点无向图的关联矩阵的性质无向图的关联矩阵的性质：(握手定理)有向图的关联矩阵的性质有向图的关联矩阵的性质：由mij的定义知通路数与回路数的矩阵算法：(1) 设A是有向图D的邻接矩阵，V =
21、 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 = 10i jpii = 1 i = 1,2,n 称(pij)nxn 为D的可达矩阵。vi 可达 vj否则例. 求下图的可达矩阵，判断它是否为强连通图？V1V4V2V3V5
22、解：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) 00 bij(n1) = 0则 i jpii = 1即得可达矩阵 P(D) = (pij)nxn 8.4 8.4 最短路径问题最短路径问题带权图：对于有向图或无向图的每条边附加一个实数w(e)，则得带权图带权图。如果G1是带权图G的子图，称w(e) 为边e上的权(当e = 时，权记作wij)，记作：G = 一、带权图及其最短
23、路径问题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(r)*，称vi在第r步获得p标号li(r)*(iii) Pr = v | v已获得p标号，称之为第r步通过集
24、 (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标号顶点设lj(r)* = min lj(r1)，r1。vjTr1顶点vi处，表明vi获得p标号。查Tr：若Tr = ，则算法结束，否则转step2将lj(r)*标在相应step2. 修改Tr中各顶点的t标号lj(
25、r) = minlj(r1) , li(r)* +wij， li(r)* 是刚刚获得p标号顶点的p标号。令r r+1，转step1。例例8.7 求下图中顶点v0与v5之间的最短路径v0v2v1v4v3v5121475326解解：利用标号法算法解此题开始，r0，v0获 p标号： l0(0)* = 0l1(0) = w01 = 1通过集P0 = v0，未通过集T0 = v1， v2 ，v3， v4，v5，l2(0) = w02 = 4l4(0) = = l5(0) l3(0) = w03 = 未通过集的 t 标号：v0v2v1v4v3v5121475326第一步第一步：r = 1，计算 = l1(
26、1)* = 1，所以i=1，P1 = v0, v1， T1 = v2,v3 ,v4,v5修改未通过集的t标号：l2(1) = minl2(0), l1(1)* + w12 = min4,3 = 3l3(1) = minl3(0), l1(1)* + w13 = min,8 = 8l4(1) = minl4(0), l1(1)* + w14 = 6l5(1) = minl5(0), l1(1)* + w15 = vi获 p标号l1(1)*，修改通过集与未通过集:修改通过集与未通过集 P2 = v0, v1, v2，T2 = v3 ,v4,v5修改未通过集的t标号：l3(2) = minl3(1)
27、, l2(2)* + w23 = min8,3+ = 8l4(2) = minl4(1), l2(2)* + w24 = min6,3+1 = 4l5(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 = 7l5(3) = minl5(2), l4(3)* + w45 = min,4+6 = 10修改通过集与未通过集 P4 = v0, v1, v2 ,v4 ,v3,T4 = v5
28、修改未通过集的t标号：l5(4) = minl5(3), l3(4)* + w35 = min10,7+2 = 9修改通过集与未通过集 P5 = v0, v1, v2 ,v4 ,v3 ,v5, T5 = 由于T5 = ，过程结束，得v0到v5的最短路径为： = v0, v1, v2 ,v4 ,v3 ,v5 ，且w() = 9标号法的说明：标号法的说明：(1)标号法可求任何顶点Vs到其它任一顶点之间的最短路径，只是算法的“ 开始”步中，先给顶点Vs加p标号0，即ls(0)* = 0，然后算法往下计算。(2)若已经求出从vi到vj的最短路径，则从vi到此路径上其余各顶点的最短路径也都求出了。8.5
29、 8.5 欧拉图与哈密尔顿图欧拉图与哈密尔顿图如果存在一条通路，它经过G的每条边一次且仅一次，则称该通路为欧拉通路欧拉通路；具有欧拉回路的图 欧拉图欧拉图。欧拉图：给定无孤立顶点的图G，存在一条回路，它经过G的每条边一次且仅一次，则此回路为欧拉回路欧拉回路。如果欧拉图的判定定理：(1) 无向图G具有一条欧欧拉拉回回路路，当且仅当G是连连通通的，并且所有顶点的度度数数全全为偶数为偶数；(2) 有向图D具有单向欧欧拉拉回回路路，当且仅当D是连连通通的，并且每个顶点的入入度度等等于出度于出度。(3) 无向图G有欧拉通路欧拉通路，当且仅当它连通且有零个或两个零个或两个奇数度顶点；(4) 有向图D有欧拉
30、通路欧拉通路，当且仅当它连通且除两个顶点外除两个顶点外，各顶点的入度均入度均等于出度等于出度。证明较复杂 (略)。哈密尔顿图：给定图G，如果存在一条经过G的每个顶点一次且恰好一次的通路(回路)，则称该通路(回路)为哈密为哈密尔顿通路尔顿通路(回路回路)。具有哈密尔顿回路的图称为哈密尔顿图。哈密尔顿图的充分必要条件至今仍未解决至今仍未解决。例例8.8 下列图哪些为欧拉图：(1)(2)(3)(4)1. 本本章章围围绕绕图图中中元元素素间间的的邻邻接接与与关关联联关关系系讨讨论论了了图图论论中中几几个个基基本本问问题题：图图的的连连通通性性问问题题，道路问题，可达性问题，最短路径问题。道路问题，可达性问题，最短路径问题。2. 要要仔仔细细领领会会和和掌掌握握下下列列基基本本概概念念和和相相关关结结论论：子子图图、度度、通通路路、回回路路、支支、割割点点，割割边，独立点，权，补图，同构图等。边，独立点，权，补图，同构图等。3. 熟练掌握标号法。熟练掌握标号法。
