图的基本概念llyppt课件

1、第第8讲讲 图的基本概念图的基本概念重点重点重要概念：简单图，重要概念：简单图， 度与握手定理、完全度与握手定理、完全图、同构图图、同构图通路、回路、图的连通性通路、回路、图的连通性图的矩阵表示与应用图的矩阵表示与应用欧拉图与哈密尔顿图欧拉图与哈密尔顿图难点难点同构图，割集，初级通路与简单通路区别同构图，割集，初级通路与简单通路区别18世纪： 哥尼斯堡(Konigsiberg)七桥问题 图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于数学游戏的难题研究。acdbadcb1859年：哈密尔顿提出环游世界1920世纪：迷宫、棋盘上马的行走线路1852年：格色里(Guthrie)提出四色

2、猜想在工程科学中的应用：现实世界中，许多状态都可用图来描述， 例如交通运输、城市规划、电 路网络、工作调配等都可以 用点和边连结的图来模拟。在计算机学科中，计算机网络、操作系统 数据库，数据结构等等都与图论 有重要的联系。一、基本图类及相关概念 如右图，这是不同于几何图形的另一数学结构。adcb 我们不关心边的长短与形状。但边可以是有方向的，有方向的边称为有向边，没有方向的边称为无向边。称a,b | aAbB 为A与B的无序积，记作：A&B。习惯上，无序对a,b改记成(a, b)有序对(a,b)均用无序积：设无序积：设A，B为二集合，为二集合，=(b,a)1. 无向图无向图无向图：无向

3、图G是一个二元组，其中(1) V是一个非空集 顶点集V(G)，每个元素为顶点或结点；(2) E是无序积V & V的可重子集(?元素可重复出现)，E 边集E(G)，E中元素称为无向边。通常记：V=v1 , v2 , , vn E=e1 , e2 , , em 其中：ek=(vi,vj) 实际中，图的画法：用小圆圈表示V中的每一个元素，假如(vi,vj)E，则在顶点vi与vj之间连线段。如(1)：G=，V=v1,v2,v3,v4， E=(v1,v2),(v1,v2),(v2,v3),(v2,v3),(v3,v4),(v2,v4),(v1,v4)v1v4v3v2e1e7e2e3e4e5e6(

4、1)v4e1e2e3e4e5e6v1v2v3v5(2)如(2)：G=，V=v1,v2,v3 ,v4 ,v5， E=(v2,v2),(v1,v2),(v2,v3),(v1,v3),(v1,v3), (v1,v4)有向图：有向图有向图：有向图D是一个二元组是一个二元组，其中，其中(1) V是非空集是非空集 顶点集顶点集 V(D)(2) E是笛卡尔积是笛卡尔积VV 的可重子集，的可重子集，其元素为有向边其元素为有向边 实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二元素。2. 有向图有向图v1v4v3v2e1e2e3e4e5e6(a)v1v4v3v2e1e2e3e4e5e

5、6(b)如(a)：D=，V=v1,v2,v3,v4， E=,如(b)：D=，V=v1,v2,v3 ,v4， E=,考虑：与以前讲到的什么相似？考虑：与以前讲到的什么相似？有限图：V，E均为有穷集合零 图：E 平凡图：E 且 |V| = 1(n, m)图：|V| = n 且 |E| = m顶点与边关联：如果ek = (vi,vj) E，称ek与vi关联，或ek与vj关联。 3. 相关概念v1v2v3v4v5v1e1e2e3e4e5e6v1v2v3v5(5, 6)图v4顶与顶相邻：如果顶与顶相邻：如果ek = (vi,vj ) E，称，称vi与与vj相邻；相邻；边与边相邻：如果边与边相邻：如果ek

6、和和ei至少有一个公共顶点关至少有一个公共顶点关联，则称联，则称ek与与ei相邻。相邻。若若ek为有向边，则称为有向边，则称vi邻接到邻接到vj, vj邻接于邻接于vi 。ek=e1e2e3e4e5e6v1v2v3v5v4v1v4v3v2e1e2e3e4e5e6孤立点：无边关联的顶点。孤立点：无边关联的顶点。平行边：无向图中，关联一对结点的无向边平行边：无向图中，关联一对结点的无向边多于一条，平行边的条数为重数；多于一条，平行边的条数为重数；多重图：多重图：?包含平行边的图。包含平行边的图。有向图中，关联一对顶点的有向边有向图中，关联一对顶点的有向边多于一条，且始、终点相同。多于一条，且始、终

7、点相同。简单图：简单图： ?既不包含平行边又不包含环的图。既不包含平行边又不包含环的图。环：环： ek = 中，假设中，假设 vi = vj，则，则ek称为环。称为环。 例：判断多重图与简单图？例：判断多重图与简单图？v1v4v3v2e1e2e3e4e5e8e6e7v5e1e2e3e4e5v1v2v3v5v4e1e3e2e4v1v2v3v5v4度：(1) 在无向图G = 中，与顶点v(vV)关联的边的数目 (每个环计算两次)， 记作：d(v)。二、度二、度e1e2e3e4e5e6v1v2v3v5v4考虑：无向图中度与边的关系考虑：无向图中度与边的关系?(2) 在有向图D = 中，以顶点v(vV

8、)作为始点的边的数目，称为该顶点的出度，记作： d+(v)；出度与入度之和，称为顶点v的度：度是图的性质的重要判断依据。d(v) = d+(v)+ d(v)以顶点v作为终点的边的数目，称为该顶点的入度，记作：d(v)。例：例：v1v4v3v2e1e2e3e4e5e8e6e7v5d+(v1)=0 , d-(v1)=1 d+(v2)=2 , d-(v2)=2 d+(v3)=4 , d-(v3)=1 d+(v4)=2 , d-(v4)=4 d+(v5)=0 , d-(v5)=0 考虑：有向图入度考虑：有向图入度 ,出度及边的关系出度及边的关系?最大度：最大度： (G) = max d(v) | vV

9、最小度：最小度： (G) = min d(v) | vV度与边数的关系：在任何图中，顶点度数的总度与边数的关系：在任何图中，顶点度数的总和等于边数之和的两倍。和等于边数之和的两倍。Vv|2)( Evd即握手定理的推论：任何图中，度为奇数的顶握手定理的推论：任何图中，度为奇数的顶点个数一定为偶数。？点个数一定为偶数。？(握手定理？握手定理？)出度与入度的关系：在有向图中，各顶点的出出度与入度的关系：在有向图中，各顶点的出度之和等于各顶点的入度之和？。度之和等于各顶点的入度之和？。度数序列：设度数序列：设V = v1,v2,vn为图为图G的顶点集，的顶点集，称称(d(v1), d(v2), d(v

10、n)为为G的度的度数序列。数序列。度数序列之和必为偶数度数序列之和必为偶数(?)。mvdvdniinii11)()(例例8.1 (3,3,2,3)，(1,3,3,3)能成为无向图的度数能成为无向图的度数序列吗？能成为无向简单图的度数序列序列吗？能成为无向简单图的度数序列吗？吗？ (5,4,3,2,2) (4,4,3,3,2,2)?例例8.2 有向简单图的度数序列有向简单图的度数序列(3,3,3,3)，它，它的入度能为的入度能为(1,1,1,1)吗？吗？例例8.3 已知图已知图G中有中有10条边，条边，4个个3度顶点，度顶点， 其余顶点的度数均小于等于其余顶点的度数均小于等于2，问，问G 中至少

11、有多少个顶点？中至少有多少个顶点？正则图：各顶点的度都相同的图为正则图；正则图：各顶点的度都相同的图为正则图；各顶点的度均为各顶点的度均为k的图为的图为k次正则图。次正则图。完全图：完全图：(1) 设设G = 是是n阶的无向简单图，如果阶的无向简单图，如果G中任何一个顶点都与其余中任何一个顶点都与其余n1个顶点相个顶点相邻，则邻，则G为无向完全图，记作：为无向完全图，记作：Kn。三、正则图与完全图考虑：考虑： 1) 正则图与完全图关系举例）正则图与完全图关系举例） 2) n阶无向完全图中，总的边数？阶无向完全图中，总的边数？ 3) n阶无向简单图中，假设阶无向简单图中，假设 (G)=n-1,那

12、么那么 (G)=？(2) 设D = 是n阶的有向简单图，如果D中任意顶点u，vV(uv)，即有有向边 ，又有有向边，则称D为n阶有向完全图。如：考虑考虑 : 1) n阶有向完全图中每个顶点的度数？总的边数？阶有向完全图中每个顶点的度数？总的边数？ 2) n阶有向完全图是多少次正则图。？阶有向完全图是多少次正则图。？ 3完全图是简单图完全图是简单图 ？1阶有向完全图？阶有向完全图？四、子图与母图(1) G = ， G = 若VV， EE，则G是G的母图， G是G的子图，记作： G G。(2) 若GG 且 V=V，则G是G的生成子图？。注：注：空图是有意义的，但一般求子图时，不将空图考虑其中空图是

13、有意义的，但一般求子图时，不将空图考虑其中(3) 设V1V，且V1，以V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图。(4) 设E1E，且E1，以E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。v1v4v3v2e1e2e3e4e5e8e6e7v5考虑考虑:V= v1,v2顶点集的导出子图顶点集的导出子图?E=e1,e3为边集的导出子图为边集的导出子图?例例8.3 列举下图的一些子图、列举下图的一些子图、真子图、生成子图、真子图、生成子图、导出子图。导出子图。v3e3e1e2e4e5v4v1v2解：自己对照定义做一做！解：自己对

14、照定义做一做！(1) 子图：子图的定义？举例(2) 真子图：举例(3) 生成子图：定义？举例(4) 导出子图：定义？举例e3e1e4v4v1v2图1图2考虑：图考虑：图1有多少个生成子图？有多少个生成子图？补图：给定一个图补图：给定一个图G = ，以，以V为顶点集，为顶点集，以所有能使以所有能使G成为完全图的添加边组成边成为完全图的添加边组成边集的图。记作：集的图。记作：G五、补图如:(1)(2)考虑考虑:构造补图的关键是什么？构造补图的关键是什么？相对补图：设相对补图：设GG, 如果另一个图如果另一个图G = ，满足满足 (1) E = E E(2) V中仅包含中仅包含E中的边所关联的结点。

15、中的边所关联的结点。则则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 1图是表达事物之间关系的工具，在画图时，由于顶点位置不同，边的曲直不同，同一事物之间的关系可能有不同形状来表示，从而引入同构图，应此同构图可以看成同一个图。2由于同构图顶点之间一一对应，边之间一一对应，关联关系对应相同，判断

16、同构图的必要条件:？ 举例说明六、同构图例例8.4 画出画出4个顶点个顶点3条边的所有可能非条边的所有可能非同构的无向简单图。（同构的无向简单图。（3）例例8.5 画出画出3个顶点个顶点2条边的所有可能非同构的有条边的所有可能非同构的有向简单图。向简单图。 （4）考虑：考虑：3顶点顶点3边的所有可能非同构的有向简单图？边的所有可能非同构的有向简单图？例例8.5 3个顶点个顶点2条边的所有可能非同构的有向简单图。条边的所有可能非同构的有向简单图。解：解： 3个顶点个顶点2条边的无向简单图只有一个：条边的无向简单图只有一个：由这个图可派生出下列4个非同构的有向简单图： G为为n阶简单图，阶简单图，

17、G为为G补图，若补图，若G G称自补图；称自补图；问：问：4个顶点个顶点3条边的所有非同构的无向简单图中有几个自补图？条边的所有非同构的无向简单图中有几个自补图？ 3阶有向完全图所有非同构生成子图中有几个自补图？阶有向完全图所有非同构生成子图中有几个自补图？通路与回路：给定图G = ，设G中顶点与边的交替序列 = v0 e1 v1 e2 el vl 满足：vi1vi是ei的端点，(G为有向图时, 要求vi1, vi分别为ei的始点、终点)，i = 1,2, l，那么为顶点v0到vl的通路。中边的数目l称为的长度。v0 = vl时，称为回路。(回路中必须有边？）一、通路与回路的概念简单通路：简单

18、通路： = v0 e1 v1 e2 ek vk为通路且边为通路且边e1 e2 ek 互不相同，又称之为迹，可简互不相同，又称之为迹，可简用用v0 v1 vk 来表示。来表示。简单回路 (v0 = vk)又称为闭迹。初级通路：初级通路： = v0 e1 v1 e2 ek vk为通路且顶点为通路且顶点v0 v1 vk 互不相同。互不相同。考虑：考虑：顶点顶点v0 v1 vk 互不相同，边会相同吗？（反之？）互不相同，边会相同吗？（反之？）初级通路、简单通路及通路关系？初级通路、简单通路及通路关系？初级回路(圈)： v0 = vk。例例8.6 就下图中就下图中V1到到 V3初级通路多少条初级通路多少

19、条?简简单通路单通路?通路通路?， V1到到 V1长度为长度为6的的初级回路初级回路?简单回路简单回路?回路回路?。v1v5e2e5v2v3v4e1e7e3e6e4解：解： 7, 9,?,0, 4,？(不考虑同构性不考虑同构性)二、通路与回路的性质：(1) 在一个n阶图中，如果从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于n1的通路。证明：设证明：设vi vk vj为为vi到到vj的长度为的长度为L的一条通路，的一条通路，则序列中必有则序列中必有L+1个顶点。个顶点。 如果如果Ln1，则此通路的顶点数，则此通路的顶点数L+1n，从而必，从而必有顶点有顶点vs，它在序列中

20、不止出现一次，即有序列，它在序列中不止出现一次，即有序列vi vs vs vj 。 在上述通路中，去掉在上述通路中，去掉vs到到vs的这些边，至少去掉的这些边，至少去掉一条边后仍是一条边后仍是vi到到vj的一条通路。此通路比原来的一条通路。此通路比原来通路长度至少少通路长度至少少1。 如此重复下去，必可得到一条从如此重复下去，必可得到一条从vi到到vj的不多于的不多于n1条边的通路。条边的通路。(2) 在n阶图中，如果从vi到vj (vivj)存在通路，则必存在从vi到vj 的长度小于等于 n1的初级通路。（简单通路？）(3) 在n阶图中，如果存在从vi到自身的回路，则从vi 到自身存在长度小

21、于等于n的回路。(4) 在n阶图中，如果从vi到自身存在一条简单回路，则从vi 到自身存在长度小于等于n的初级回路。 考虑：在n阶图中，若两点之间存在初级通路，则其长度一定小于等于 n1？ 若为简单通路？考虑：在考虑：在n阶图中，如果从阶图中，如果从vi到自身存在一条初级回路，到自身存在一条初级回路，则从则从vi 到自身的长度一定小于等于到自身的长度一定小于等于n？（简单回路？）？（简单回路？）两顶点连通：u,v为无向图G的两个顶点，u到v存在一条通路。连连 通通 图：图：G 中任何两个顶点是连通的；否中任何两个顶点是连通的；否则是分离图。则是分离图。三、无向图的连通性连通分支：无向图G中每个

22、划分块称为G的一个连通分支，p(G)表示连通分支的个数。p(G) = ？为连通图。连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系。(1) 自反性：由于规定任何顶点到自身总是连通的；证明：证明：(2) 对称性：无向图中顶点之间的连通是相互的；(3) 传递性：由连通性的定义可知。四、有向图的连通性：(1) 如果有向图 D = 中所有有向边的方向去掉后所得图为无向连通图，则说D为弱连通图。(2) 弱连通图中， 任何一对顶点之间，至少有一顶点可达另一个顶点，那么 是单向连通的；(3)任何两个顶点之间互相可达，称强连通。考虑：弱连通、单向连通、强连通关系？考虑：弱连通、单向连通、强连通关

23、系？图图1图图2图图3v1v1v1v2v2v2v3v3v3v4v4v4有向连通图的判定：有向连通图的判定：仅仅弱连通仅仅弱连通:有向连通图中至少有两个以上顶点有向连通图中至少有两个以上顶点为全入度或全出度为全入度或全出度单向连通单向连通:依次从各顶点出发依次从各顶点出发,寻找到其他所有寻找到其他所有顶点的可达性顶点的可达性.-(存在经过每点至少一次的通存在经过每点至少一次的通路路)强连通的充要条件强连通的充要条件:当且仅当当且仅当D中存在一条回路，中存在一条回路，它至少经过每个顶点一次它至少经过每个顶点一次.-(存在经过每点至存在经过每点至少一次的回路少一次的回路)有向图D强连通，当且仅当D中

24、存在一条回路，它至少经过每个顶点一次。 (充分性) 如果D中存在回路，它经过D中的每个顶点至少一次，则D中的任意两个顶点都在回路中，以，D中任意两个顶点都是可达，因而D是强连通。(必要性) D是强连通的，则D中任何两个顶点都是可达的。不妨设D中的顶点为v1,v2,vn，因为vi可达vi+1, i=1,2,，n1，让这些通路首尾相连，所以vi到vi+1存在通路，且vn到v1也存在通路，则得一回路。显然每个顶点在回路中至少出现一次。证明：证明：点割集：无向图G = ，如果存在顶点集VV 1) 在G中删除V中所有顶点(包括与该顶点关联的边)后所得子图G-V的连通分支数与G的连通分支数满足P(G-V)

25、P(G)， 2 ) 而 删 除 V 中 任 何 真 子 集 V 后 P ( G -V”)=P(G) ，则V是G的点割集。 如果点割集中只有一个顶点，该点为割点。五、割集考虑：如果点割集中顶点考虑：如果点割集中顶点1，点割集中会含割点吗？，点割集中会含割点吗？边割集：设无向图G = ，存在边集EE 1) 在G中删除E中所有边(不包括边关联的顶点)后所得子图G-E的连通分支数与G的连通分支数满足P(G-E)P(G)， 2而删除E中任何真子集E后P(G-E”)=P(G) ，则E是G的边割集。如果边割集中只有一边时，该边为割边(或桥)考虑：如果边割集中边数考虑：如果边割集中边数1，边割集中会含割边吗？

26、，边割集中会含割边吗？V2, V4 是点割集？V6, V1, V5是点割集？ V6是割点？ V1？ V5？e9, e7, e8是边割集？ e9是割边？e8, e7是边割集？ e8, e7，e1是边割集? e3e1e2e4e5v4v1v2v3v5v6v7e6e8e7e9点割集中不会含其有它点割集？点割集中不会含其有它点割集？边割集中不会含有其他边割集？边割集中不会含有其他边割集？看看P 292 21 (1) .43无向图关联矩阵：(1) 设G = 为(n,m)无向图, V = v1,v2,vn, E = e1, e2, em, 令：mij = 10称M(G) = (mij)nm为G的关联矩阵。v

27、i 关联 ej环?2）vi 不关联 ej一、关联矩阵及其性质v4e1e2e3e4e5v1v2v3强调：顶点与边的关系，强调：顶点与边的关系， (mij)nm行行n为？为？m为？为？无向图的关联矩阵的性质：无向图的关联矩阵的性质：)(, 2 , 1(2) 1 (n1iij每条边关联两个顶点mjm)()2(iim1jij的度数vvdm n1iiij)(2)3(vdmm是孤立点当且仅当m1jiij0)4(vm为平行边与列相同，说明列与第若第kj)5(eekj(?定理)v4e1e2e3e4e5v1v2v3 1 1 1 0 0 0 1 1 1 0 1 0 0 1 2 0 0 0 0 0(?图与矩阵)(2

28、) 设D = 是有向图且无环，令：mij = 10则称M(D) = (mij)nm为D的关联矩阵。1D中 vi 是 ej 的始点vi 与 ej 不关联vi 是 ej 的终点有向图关联矩阵v1v4v3v2e1e2e3e4强调：顶点与边的关系，强调：顶点与边的关系， (mij)nm行行n为？为？m为？为？有向图的关联矩阵的性质：有向图的关联矩阵的性质：0, 2 , 10) 1 (ijn1iijmmjm，从而，)() 1()2(im1jijvdmmvdmn1iin1im1jij)() 1(从而有)() 1(im1jijvdmmvdmn1iin1im1jij)() 1(孤立点？两列相同？有向图的关联矩

29、阵所有元素之和为？孤立点？两列相同？有向图的关联矩阵所有元素之和为？v1v4v3v2e1e2e3e4 -1 0 0 0 1 -1 0 0 0 1 -1 1 0 0 1 -1 (?图与矩阵)邻接矩阵：设邻接矩阵：设G = 是一个图，它有是一个图，它有n个个顶点，顶点，V = v1,v2,vn，令，令aij = x E (或 (vi, vj)E 环?2)0 E (或 (vi, vj)E)称A(G) = (aij) 为G的邻接矩阵。二、邻接矩阵及其性质v1v4v3v2e1e2e3e4e5e6强调：顶点与顶点的关系，强调：顶点与顶点的关系， (aij)nn行行n为？为？v4e1e2e3e4e5v1v2

30、v3无向图邻接矩阵的特性：无向图邻接矩阵的特性：(1) 邻接阵是对称阵；(2) 同一行或者同一列的元素和为对应顶点的度数；或即)()(jn1iijin1jijvdavda(3) 矩阵中所有元素的和为边数的2倍)(2n1jn1iij握手定理即ma 0 2 1 0 2 0 1 0 1 1 2 0 0 0 0 0 v4e1e2e3e4e5v1v2v3(?图与矩阵)有向图邻接矩阵的特性有向图邻接矩阵的特性(1) 同一行的元素和为对应顶点的出度(2) 同一列的元素和为对应顶点的入度)(in1jijvda即)(jn1iijvda即(3) aij= ？v1v4v3v2e1e2e3e4e5e6 0 0 0 0

31、 1 1 0 0 0 1 0 1 0 0 1 1 (?图与矩阵)强调：对无向图环计强调：对无向图环计2次，对有向图环计次，对有向图环计1次次 ？三、应用v4v1v2v3问：1） 求此图中长度为1通路总数与回路总数？2） 求此图中长度为2通路总数与回路总数？3求此图中长度为3通路总数与回路总数？4、5、n?4） 求此图中长度小于4的通路总数与回路总数？ 1 2 1 0 0 0 1 0 0 0 0 1 0 0 1 0 v4v1v2v3A=A2= 1 2 3 1 0 0 0 1 0 0 1 0 0 0 0 1 1 2 4 3 0 0 1 0 0 0 0 1 0 0 1 0 1 2 6 4 0 0 0

32、 1 0 0 1 0 0 0 0 1 A3=A4=求此图中长度为求此图中长度为n通路总数与回路总数？通路总数与回路总数？长度小于或等于长度小于或等于n通路总数与回路总数？单向连通图？通路总数与回路总数？单向连通图？通路数与回路数的矩阵算法： 设A是有向图D的邻接矩阵，V = v1,v2,vn， Al (l1)中元素aij(l)为vi到vj长度为l的通路数的中长度为为lDn1in1j(l)ija通路总数通路总数的中长度为为lDn1i)(iila回路数回路数1. 求通路数与回路数(1) 求图中长度为求图中长度为n通路总数与回路总数通路总数与回路总数 设A是有向图D的邻接矩阵，B1 = A，B2 =

33、 A+A2,，Br = A+A2+Ar，则Br中元素bij(r) 为D中vi到vj长度小于等于 r 的通路数。的通路总数中长度小于为rDbji,(r)ij的回路总数中长度小于为rDbn1i(r)ii(2) 求图中长度小于或等于求图中长度小于或等于r的通路总数与回路总数的通路总数与回路总数设D = 为一有向图，V = v1,v2,vn，令pij = 10i jpii = 1 i = 1,2,n 称(pij)nn 为D的可达矩阵。vi 可达 vj否则(3). 求可达矩阵求可达矩阵可达矩阵的求法：由邻接矩阵A计算A2,A+A2, A+A2+A(r) = B = (bij(r)nn pij = 1 b

34、ij(r) 00 bij(r) = 0那么 i jpii = 1即得可达矩阵 P(D) = (pij)nxn 说明说明: 求通路求通路r|v| ; 求回路求回路r=|v| 例. 求下图的可达矩阵，判断它是否为强连通图？V1V4V2V3V5解：1. 写出邻接矩阵0101100001110100010000010A2. 计算 A2, A3, A4, A5.11120001001113101112110103A00111000100111211010001002A23253011123436312332111315A12222110101233211131011124A3. 计算 B = A +A2

35、 + A3 + A4 + A5 , 并求出1111111111111111111111111P考虑：考虑：若是单向连通图，其可达矩阵应满足什么？若是单向连通图，其可达矩阵应满足什么？习题习题若若D是具有结点是具有结点 V1,V2,V3,V4的有向图，它的邻接的有向图，它的邻接矩阵表示为：矩阵表示为： 0，1 ，0，1 0，1， 2，0 1，0，0， 1 1，0，0， 0画出此图画出此图D是单向连通，还是强连通？说明理由是单向连通，还是强连通？说明理由求该图中长度小于等于求该图中长度小于等于3的通路与回路总数的通路与回路总数可达矩阵可达矩阵看看P196 6.24带权图：对于有向图或无向图的每条边

36、附加一个非零正实数w(e)，则得带权图。如果G1是带权图G的子图，称)()(1)E(Ge11GwGew，记作：的权为w(e) 为边e上的权(当e = 时，权记作wij)，记作：G = 一、带权图及其最短路径问题G = 为带权图，且G中各边带的权均大于等于0，从顶点u到顶点v的所有通路中求带权最小的通路问题，称为最短路径问题一般为简单图）。最短路径问题：如果如果v1v2 vn1vn是是v1到到vn的最短路径，的最短路径，则则v1v2 vn1也必然是也必然是v1从到从到vn1的最短路径。的最短路径。求最短路径的戴克斯德拉(Dijkstra)算法基本思想：考虑考虑 ：从始点到终点的最短路径，必然是始

37、点到该路：从始点到终点的最短路径，必然是始点到该路径上各点的径上各点的 最短路径最短路径 ？也必然是该路径上各点到终？也必然是该路径上各点到终点点 的的 最短路径最短路径 ？最短路径？最短路径 唯一？唯一？G = , V=v1,v2,.vn,W=(wij)nxn是距离矩阵是距离矩阵二、求最短路径的戴克斯德拉(Dijkstra)算法求求v1点到其他各点的距离的点到其他各点的距离的Dijkstra算法：算法： l(vi)表示表示vi点到点到v1的最短距离，的最短距离， A V 初始化： A= v1， = Vv1 ， l (v1)=0， l (vi)= ，i为2,3,n。 i=0A(2) 假设 为空

38、集，打印A，否则转3） A(3) 对vi 所有点计算：AvjAl (vi) = minl (vi) , l (vj)+w ji(4) 令l(vi+1) = min l (v)， A= Avi+1 ， = vi+1 i=i+1，转2）AAvA算法解释：算法解释：求求v1点到其他各点的距离的点到其他各点的距离的Dijkstra算法：算法： 距离矩阵：相同点距离矩阵：相同点0，相邻点距离为权，否则，相邻点距离为权，否则A=v1, = V-v1； = 则打印A，否则继续；在 中找与A相邻的所有点，计算它们到v1的最短距离；在 中选择各点最短距离的最短点，将其加入到A中，同时删除 此点，转第2 步。AA

39、AAA例例8.7 求下图中顶点求下图中顶点v0与与v5之间的最短路径之间的最短路径v0v2v1v4v3v5121475326例: 求下图中顶点v0与v5之间的最短路径v1v31v0v2v4v512145126Dijkstra算法又称标号说明：算法又称标号说明：(1) 可求任何顶点Vs到其它任一顶点之间的最短路径，只是算法的“ 开场步中 ,顶点Vs加入A，然后算法往下计算。(2)若已经求出从vi到vj的最短路径，则从vi到此路径上其余各顶点的最短路径也都求出了。 实施一个工程计划时，若将整个工程分成若干个工序，有些工序可同时实施，有些工序必须在完成另外一些工序后才能实施，工序之间的次序可用有向图

40、表示，该图称为PERT图计划评审图），特点：有向连通图；简单图；无回路；一个顶点入度为0发点），一个顶点出度为0 （收点）带权非负图。记权为 wij，一般表示时间设D = 为有向图， vV ，称 D+（v）= x | xV E 为v的后继元素； D-（v）= x | xV E 为v的先驱元素。求项目工程完成的最早时间问题就是关键路径问题，因为关键路径上任何点时间的耽误，就是整个工程的耽误。vj D- (vi)TE(vi) = max ( TE(vj) +wji) i=2,3nvi点最早完成时间点最早完成时间TE(vi)：自发点记：自发点记v1开始沿最长开始沿最长路径到路径到vi点所需的时间。点

41、所需的时间。 TE(v1) =0vj D+ (vi)TL(vi) = min ( TL(vj) - wij) i=1,2,n-1vi点最晚完成时间点最晚完成时间TL(vi)：在保证收点：在保证收点vn最早完成时最早完成时间不变的条件下，自间不变的条件下，自v1最迟到最迟到vi点所需的时间。点所需的时间。 TL(vn) =TE (vn) vi点缓冲时间点缓冲时间 TS(vi)= TL(vi) - TE(vi) ：。：。例例8.8 求下图各顶点最早、最晚完成时间及关键路径求下图各顶点最早、最晚完成时间及关键路径v1v3v2v4v5124343112v6v7v80446注意：注意：求求vi最早完成时间前必须求出其所有先驱点的最早最早完成时间前必须求出其所有先驱点的最早完成时间，故从发点开始求；完成时间，故从发点开始求；求求vi最晚完成时间必须求出其所有后继点的最迟完最晚完成时间必须求出其所有后继点的最迟完成时间，故从收点开始求；成时间，故从收点开始求；收点的最早完成时间等于最