《最新图的基本概念llyppt课件.ppt》由会员分享，可在线阅读，更多相关《最新图的基本概念llyppt课件.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、18世纪： 哥尼斯堡(Konigsiberg)七桥问题 图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于数学游戏的难题研究。acdbadcb 实际中，图的画法：用小圆圈表示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(1)v4e1e2e3e4e5e6v1v2v3v5(2)如(2)：G=，V=v1,v2,v3 ,v4 ,v5， E=(v2,v2),(v1,v
2、2),(v2,v3),(v1,v3),(v1,v3), (v1,v4)有向图有向图：有向图有向图D是一个二元组是一个二元组，其中，其中(1) V是非空集是非空集 顶点集顶点集 V(D)(2) E是笛卡尔积是笛卡尔积V V 的可重子集，的可重子集，其元素为有向边其元素为有向边 实际中，画法同无向图，只是要根据E中元素的次序，由第一元素用方向线段指向第二元素由第一元素用方向线段指向第二元素。2. 有向图有向图v1v4v3v2e1e2e3e4e5e6(a)v1v4v3v2e1e2e3e4e5e6(b)如(a)：D=，V=v1,v2,v3,v4， E=,如(b)：D=，V=v1,v2,v3 ,v4，
3、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和和ei至少有一个公共顶点关联，至少有一个公共顶点关联，则称则称ek与与ei相邻相邻。若若ek为有向边，则
4、称为有向边，则称vi邻接到邻接到vj, vj邻接于邻接于vi 。ek=e1e2e3e4e5e6v1v2v3v5v4v1v4v3v2e1e2e3e4e5e6孤立点孤立点：无边关联的顶点。无边关联的顶点。平行边平行边：无向图中，关联一对结点的无向边无向图中，关联一对结点的无向边多于一条，平行边的条数为多于一条，平行边的条数为重数重数；多重图多重图：?包含平行边的图。包含平行边的图。有向图中，关联一对顶点的有向边有向图中，关联一对顶点的有向边多于一条，且始、终点相同。多于一条，且始、终点相同。简单图简单图： ?既不包含平行边又不包含环的图。既不包含平行边又不包含环的图。环环： ek = 中，若中，若
5、 vi = vj，则，则ek称为环。称为环。 例：例：判断多重图与简单图？v1v4v3v2e1e2e3e4e5e8e6e7v5e1e2e3e4e5v1v2v3v5v4e1e3e2e4v1v2v3v5v4度：(1) 在无向图G = 中，与顶点v(vV)关联的边的数目 (每个环计算两次每个环计算两次)， 记作：d(v)。二、度二、度e1e2e3e4e5e6v1v2v3v5v4思考：思考：无向图中度与边的关系无向图中度与边的关系?(2) 在有向图D = 中，以顶点v(vV)作为始点始点的边的数目，称为该顶点的出度出度，记作： d+(v)；出度与入度之和，称为顶点v的度：度是图的性质的重要判断依据。d
6、(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) | v V最小度最小度： (G) = min d(v) | v V度与边数的关系度与边数的关系：在任何图中，顶点度数的总在任
7、何图中，顶点度数的总和等于边数之和的两倍。和等于边数之和的两倍。Vv|2)( Evd即握手定理的推论握手定理的推论：任何图中，度为奇数的顶任何图中，度为奇数的顶点个数一定为偶数。点个数一定为偶数。？(握手定理握手定理？)出度与入度的关系出度与入度的关系：在有向图中，各顶点的出在有向图中，各顶点的出度之和等于各顶点的入度之和度之和等于各顶点的入度之和？。度数序列度数序列：设设V = v1,v2,vn为图为图G的顶点集，的顶点集，称称(d(v1), d(v2), d(vn)为为G的度数的度数序列。序列。度数序列之和必为偶数度数序列之和必为偶数(?)。mvdvdniinii11)()(例例8.1 (
8、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 中至少有多少个顶点？正则图正则图：各顶点的度都相同的图为正则图；各顶点的度都相同的图为正则图；各顶点的度均为各顶点的度均为k的图为的图为k次正则图。次正则图。完全图完全图：(1) 设设G = 是是n阶的无向简单图，如果阶的无向简单图，如果G中任何一个顶点都与其余中任何一个顶点都与其余
9、n1个顶点相个顶点相邻，则邻，则G为为无向完全图无向完全图，记作：，记作：Kn。三、正则图与完全图思考思考： 1) 正则图与完全图关系（举例）正则图与完全图关系（举例） 2) n阶无向完全图中，总的边数？阶无向完全图中，总的边数？ 3) n阶阶无向无向简单图中，简单图中，若 (G)=n-1,则则 (G)=？(2) 设D = 是n阶的有向简单图，如果D中任意顶点u，vV(uv)，即有有向边 ，又有有向边，则称D为n阶有向完全图阶有向完全图。如：思考思考 : 1) n阶有向完全图中每个顶点的度数？总的边数？阶有向完全图中每个顶点的度数？总的边数？ 2) n阶有向完全图是多少阶有向完全图是多少次正则
10、图。？次正则图。？ 3）完全图是简单图）完全图是简单图 ？1阶有向完全图？阶有向完全图？四、子图与母图(1) G = ， G = 若VV， EE，则G是G的母图母图， G是G的子图子图，记作： G G。(2) 若GG 且 V=V，则G是G的生成子图生成子图？。注：注：空图是有意义的，但一般求子图时，不将空图考虑其中空图是有意义的，但一般求子图时，不将空图考虑其中(3) 设V1V，且V1，以V1为顶点集，以两以两端点均在端点均在V1中的全体边中的全体边为边集的G的子图，称为V1导出的导出子图导出的导出子图。(4) 设E1E，且E1，以E1为边集，以以E1中边中边关联的顶点的全体关联的顶点的全体为
11、顶点集的G的子图，称为E1导出的导出子图导出的导出子图。v1v4v3v2e1e2e3e4e5e8e6e7v5思考思考:V= v1,v2顶点集的导出子图顶点集的导出子图?E=e1,e3为边集的导出子图为边集的导出子图?例例8.3 列举下图的一些子图、真子图、生成子图、导出子图。v3e3e1e2e4e5v4v1v2解解：自己对照定义做一做！(1) 子图：子图的定义？举例(2) 真子图：举例(3) 生成子图生成子图：定义？举例(4) 导出子图导出子图：定义？举例e3e1e4v4v1v2图1图2思考思考：图图1有多少个生成子图有多少个生成子图？补图补图：给定一个图给定一个图G = ，以，以V为顶点集，
12、为顶点集，以所有能使以所有能使G成为成为完全图完全图的添加边组成边的添加边组成边集的图。记作：集的图。记作：G五、补图如:(1)(2)思考思考:构造补图的关键是什么？构造补图的关键是什么？相对补图相对补图：设：设G G, 如果另一个图如果另一个图G = ，满足满足 (1) E = E E(2) V中仅包含中仅包含E中的边所关联的结点。中的边所关联的结点。则则G是子图是子图G相对于相对于G的补图的补图。如：图为的子图，则图(1)(2)(3)为(1)相对于(2)的补图。图同构图同构：对于对于G = ，G = ，如果，如果存在存在 g:VV 满足：满足： (1) 任意边任意边e = (vi,vj)
13、E，当且仅当，当且仅当e = (g(vi), g(vj) E(2) e与与e的重数相同的重数相同则说则说G G 1）图是表达事物之间关系的工具，在画图时，由于在画图时，由于顶点位置顶点位置不同，边的曲直不同不同，边的曲直不同，同一事物之间的关系可能有不同形状来，同一事物之间的关系可能有不同形状来表示，从而引入同构图表示，从而引入同构图，应此同构图同构图可以看成同一个图可以看成同一个图。2）由于同构图顶点之间一一对应，边之间一一对应，关联关系对应相同，判断同构图的必要条件判断同构图的必要条件:？ 举例说明举例说明六、同构图例例8.4 画出4个顶点3条边的所有可能非同构的无向简单图。（3）例例8.
14、5 画出3个顶点2条边的所有可能非同构的有向简单图。 （4）思考：思考：3顶点顶点3边的所有可能非同构的有向简单图？边的所有可能非同构的有向简单图？例例8.5 3个顶点2条边的所有可能非同构的有向简单图。解：解： 3个顶点2条边的无向简单图只有一个：由这个图可派生出下列4个非同构的有向简单图： G为为n阶简单图，阶简单图，G为为G补图，若补图，若G G称自补图；称自补图；问：问：4个顶点个顶点3条边的所有非同构的无向简单图中有几个自补图？条边的所有非同构的无向简单图中有几个自补图？ 3阶有向完全图所有非同构生成子图中有几个自补图？阶有向完全图所有非同构生成子图中有几个自补图？通路与回路：给定图
15、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为通路且顶点顶
16、点v0 v1 vk 互不相同。思考：思考：顶点顶点v0 v1 vk 互不相同，边会相同吗？（反之？）互不相同，边会相同吗？（反之？）初级通路、简单通路及通路关系？初级通路、简单通路及通路关系？初级回路(圈圈)： v0 = vk。例例8.6 就下图中V1到 V3初级通路多少条?简单通路?通路?， V1到 V1长度为6的初级回路?简单回路?回路?。v1v5e2e5v2v3v4e1e7e3e6e4解解： 7, 9,?,0, 4,？(不考虑同构性)二、通路与回路的性质：(1) 在一个n阶图中，如果从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于n1的通路。证明证明：设vi vk
17、vj为vi到vj的长度为L的一条通路，则序列中必必有有L+1个顶点个顶点。 如果Ln1，则此通路的顶点数L+1n，从而必有顶点从而必有顶点vs，它在序列中不止出现一次它在序列中不止出现一次，即有序列vi vs vs vj 。 在上述通路中，去掉去掉vs到到vs的这些边，至少去掉一条边后的这些边，至少去掉一条边后仍是仍是vi到到vj的一条通路。的一条通路。此通路比原来通路长度至少少1。 如此重复下去如此重复下去，必可得到一条从vi到vj的不多于n1条边的通路。(2) 在n阶图中，如果从vi到vj (vivj)存在通路，则必存在从vi到vj 的长度小于等于长度小于等于 n1的初级通路初级通路。（简
18、单通路？）(3) 在n阶图中，如果存在从vi到自身的回路，则从vi 到自身存在长度小于等于长度小于等于n的回路的回路。(4) 在n阶图中，如果从vi到自身存在一条简单回路，则从vi 到自身存在长度小于等于长度小于等于n的的初级回路初级回路。 思考思考：在在n阶图中，若两点之间存在初级通路，阶图中，若两点之间存在初级通路，则其长度则其长度一定一定小于等于小于等于 n1？ 若为简单通路若为简单通路？思考思考：在在n阶图中，如果从阶图中，如果从vi到自身存在一条初级回路，到自身存在一条初级回路，则从则从vi 到自身的长度到自身的长度一定一定小于等于小于等于n？（简单回路？）？（简单回路？）两顶点连通
19、：u,v为无向图G的两个顶点，u到v存在一条通路。连连 通通 图图：G 中任何两个顶点是连通任何两个顶点是连通的；否则是分离图分离图。三、无向图的连通性连通分支：无向图G中每个划分块称为G的一个连通分支连通分支，p(G)表示连通分支的个数。p(G) = ？为连通图。连通性的性质：无向图中顶点之间的连通关系是顶点集V上的等价关系等价关系。(1) 自反性：由于规定任何顶点到自身总是连通的；证明证明：(2) 对称性：无向图中顶点之间的连通是相互的；(3) 传递性：由连通性的定义可知。四、有向图的连通性：(1) 如果有向图 D = 中所有有向边的方向去所有有向边的方向去掉后所得图为掉后所得图为无向连通
20、图无向连通图，则说D为弱连通图弱连通图。(2) 弱连通图中， 任何一对顶点之间，至少有一任何一对顶点之间，至少有一顶点可达另一个顶点顶点可达另一个顶点，则 是单向连通单向连通的；(3)任何两个顶点之间互相可达任何两个顶点之间互相可达，称强连通强连通。思考：思考：弱连通、单向连通、强连通关系弱连通、单向连通、强连通关系？图图1图图2图图3v1v1v1v2v2v2v3v3v3v4v4v4有向连通图的判定有向连通图的判定：仅仅仅仅弱连通弱连通:有向连通图中至少有两个以上顶点有向连通图中至少有两个以上顶点为全入度或全出度为全入度或全出度单向连通单向连通:依次从各顶点出发依次从各顶点出发,寻找到其他所有
21、寻找到其他所有顶点的可达性顶点的可达性.-(存在经过每点至少一次的通存在经过每点至少一次的通路路)强连通的充要条件强连通的充要条件:当且仅当当且仅当D中存在一条回路，中存在一条回路，它至少经过每个顶点一次它至少经过每个顶点一次.-(存在经过每点至存在经过每点至少一次的回路少一次的回路)有向图D强连通，当且仅当D中存在一条回路，它至少经过每个顶点一次。 (充分性充分性) 如果D中存在回路，它经过D中的每个顶点至少一次，则D中的任意两个顶点都在回路中的任意两个顶点都在回路中，以，D中任意两个顶点都是可达，因而D是强连通。(必要性必要性) D是强连通的，则D中任何两个顶点都中任何两个顶点都是可达的是
22、可达的。不妨设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)P(G)， 2)而删除删除V中任何中任何真子集真子集V”后P(G-V”)=P(G) ，则V是G的点割集。 如果点割集中只有一个顶点，该点为割点割点。五、割集思考：思考：如果点割集中顶点如
23、果点割集中顶点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，边割集中会含割边吗？，边割集中会含割边吗？V2, V4 是点割集？V6, V1, V5是点割集？ V6是割点？ V1？ V5？e9, e7, e8是边割集？ e9是
24、割边？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的关联矩阵关联矩阵。vi 关联 ej（环环?2）vi 不关联 ej一、关联矩阵及其性质v4e1e2e3e4e5v1v2v3强调：强调：顶点与边的关系顶点与边的
25、关系， (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) 设D = 是有向图且无环无环，令：mij = 10则称M(D) = (mij)nm为D的关联矩阵关联矩阵。1D中 vi 是 ej 的始
26、点vi 与 ej 不关联vi 是 ej 的终点有向图关联矩阵v1v4v3v2e1e2e3e4强调：强调：顶点与边的关系顶点与边的关系， (mij)nm行n为？m为？有向图的关联矩阵的性质有向图的关联矩阵的性质：0, 2 , 10) 1 (ijn1iijmmjm，从而，)() 1()2(im1jijvdmmvdmn1iin1im1jij)() 1(从而有)() 1(im1jijvdmmvdmn1iin1im1jij)() 1(孤立点孤立点？两列相同两列相同？有向图的关联矩阵所有元素之和为有向图的关联矩阵所有元素之和为？v1v4v3v2e1e2e3e4 -1 0 0 0 1 -1 0 0 0 1
27、-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为？v4e1e2e3e4e5v1v2v3无向图邻接矩阵的特性无向图邻接矩阵的特性：(1) 邻接阵是对称阵；(2) 同一行或者同一列的元素和为对应顶点的度数；或即)()(jn1iijin1jijvdavd
28、a(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 1 1 0 0 0 1 0 1 0 0 1 1 (?图与矩阵图与矩阵)强调强调：对无向图环计无向图环计2次，对有向图环计次，对有向图环计1次次 ？三、应用v4
29、v1v2v3问：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 1 0 0 1 0 0 0 0 1 A3=A4=求此图中长度为求此图中长度为n通路总数与回路总数？通路总数与回路总数？长度小于或等于长度小于或等于n通路
30、总数与回路总数通路总数与回路总数？单向连通图单向连通图？通路数与回路数的矩阵算法： 设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 = A+A2,，Br = A+A2+Ar，则Br中元素bij(r) 为D中vi到vj长度小于等于长度小于等于 r 的通的通路数路数。的通路总数
31、中长度小于为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 bij(r) 00 bij(r) = 0则 i jpii = 1即得可达矩阵 P(D) = (pij)nxn 说明说明:
32、求通路求通路r|v| ; 求回路求回路r=|v| 例. 求下图的可达矩阵，判断它是否为强连通图？V1V4V2V3V5解：1. 写出邻接矩阵0101100001110100010000010A2. 计算 A2, A3, A4, A5.11120001001113101112110103A00111000100111211010001002A23253011123436312332111315A12222110101233211131011124A3. 计算 B = A +A2 + A3 + A4 + A5 , 并求出1111111111111111111111111P思考：思考：若是单向连通图，
33、其可达矩阵应满足什么？若是单向连通图，其可达矩阵应满足什么？习题习题若若D是具有结点是具有结点 V1,V2,V3,V4的有向图，它的邻接的有向图，它的邻接矩阵表示为：矩阵表示为： 0，1 ，0，1 0，1， 2，0 1，0，0， 1 1，0，0， 0画出此图画出此图D是单向连通，还是强连通？说明理由是单向连通，还是强连通？说明理由求该图中长度小于等于求该图中长度小于等于3的通路与回路总数的通路与回路总数1)可达矩阵可达矩阵看看P196 6.24带权图：对于有向图或无向图的每条边附加一个非零正实数w(e)，则得带权图带权图。如果G1是带权图G的子图，称)()(1)E(Ge11GwGew，记作：的
34、权为w(e) 为边e上的权(当e = 时，权记作wij)，记作：G = 一、带权图及其最短路径问题G = 为带权图，且G中各边带的权均大于等于0，从顶点顶点u到顶点到顶点v的所有通路中求带权最小的的所有通路中求带权最小的通路问题通路问题，称为最短路径问题（最短路径问题（一般为简单图一般为简单图）。最短路径问题：如果如果v1v2 vn1vn是是v1到到vn的最短路径，则的最短路径，则v1v2 vn1也必然是也必然是v1从到从到vn1的最短路径的最短路径。求最短路径的戴克斯德拉(Dijkstra)算法基本思想基本思想：思考思考 ：从始点到终点的最短路径，必然是始点到该路径上各点的 最短路径 ？也必
35、然是该路径上各点到终点 的 最短路径 ？最短路径 唯一？G = , V=v1,v2,.vn,W=(wij)nxn是距离矩阵是距离矩阵二、求最短路径的戴克斯德拉(DijkstraDijkstra)算法求求v1点到其他各点的距离的点到其他各点的距离的Dijkstra算法算法： l(vi)表示vi点到v1的最短距离， A V 初始化： A= v1， = Vv1 ， l (v1)=0， l (vi)= ，i为2,3,n。 i=0A(2) 若 为空集，打印A，否则转（3） A(3) 对vi 所有点计算：AvjAl (vi) = minl (vi) , l (vj)+w ji(4) 令l(vi+1) =
36、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 步。AAAAA例例8.7 求下图中顶点v0与v5之间的最短路径v0v2v1v4v3v5121475326例: 求下图中顶点v0与v5之间的最短路径v1v31v0v2v4v512145126
37、Dijkstra算法（又称标号）算法（又称标号）说明：说明：(1) 可求任何顶点Vs到其它任一顶点之间的最短路径，只是算法的“ 开始”步中 ,顶点Vs加入A，然后算法往下计算。(2)若已经求出从vi到vj的最短路径，则从vi到此路径上其余各顶点的最短路径也都求出了。 实施一个工程计划时，若将整个工程分成若干个工序，有些工序可同时实施，有些工序必须在完成另外一些工序后才能实施，工序之间的次序可用有向图表示，该图称为PERT图（计划评审图），特点：有向连通图；简单图；无回路；一个顶点入度为0（发点），一个顶点出度为0 （收点） 带权（非负）图。记权为 wij，一般表示时间设D = 为有向图， vV
38、 ，称 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点所需的时间。 TE(v1) =0vj D+ (vi)TL(vi) = min ( TL(vj) - wij) i=1,2,n-1vi点最晚完成时间点最晚完成时间TL(vi)：在保证收点vn最早完成时间不变的条件下，自v1最迟到vi点所需的时间。 TL(vn) =TE (
39、vn) vi点缓冲时间点缓冲时间 TS(vi)= TL(vi) - TE(vi) ：。缓冲时间缓冲时间 为0例例8.8 求下图各顶点最早、最晚完成时间及关键路径v1v3v2v4v5124343112v6v7v80446注意：注意：求vi最早完成时间前必须求出其所有先驱点的最早完成时间，故从发点开始求；求vi最晚完成时间必须求出其所有后继点的最迟完成时间，故从收点开始求； 收点的最早完成时间等于最晚完成时间。 如果存在一条通路，它经过G的每条每条边一次且仅一次边一次且仅一次，并且行遍图中并且行遍图中每每个个顶点顶点，则称该通路为欧拉通路欧拉通路；具有欧拉回路欧拉回路的图 欧拉图欧拉图。欧拉图：给
40、定无孤立顶点的图G，存在一条回路，它经过G每条边一次且仅一次，每条边一次且仅一次，并且行遍图中每个顶点并且行遍图中每个顶点，则此回路为欧拉回路欧拉回路。如果思考：思考：欧拉通路是简单通路？反之呢？欧拉通路是初级通路？欧拉通路是简单通路？反之呢？欧拉通路是初级通路？欧拉图是否一定存在欧拉通路？欧拉图是否一定存在欧拉通路？有向欧拉图是强连通图？反之呢？有向欧拉图是强连通图？反之呢？例例8.8 下列图哪些为欧拉图？哪些存在欧拉通道？：(1)(2)(3)(4)欧拉图的判定定理（必须掌握！必须掌握！说明理由）(1) 无向图G具有一条欧拉回路，当且仅当G是连通连通的，并且所有顶点的度数全度数全为偶数为偶数
41、；(2) 有向图D具有单向欧拉回路，当且仅当D是连通连通的，并且每个顶点的入度等入度等于出度于出度。证明较复杂证明较复杂 (略略) ，反证思维理解！反证思维理解！(1) 无向图G有欧拉通路，当且仅当它连通连通且有零个或两个零个或两个奇数度顶点；(2) 有向图D有欧拉通路，当且仅当它连通连通且除除两个除顶点外两个除顶点外，各顶点的入度均等于出度入度均等于出度，或者各顶点的入度均等于出度入度均等于出度。此两个特殊顶点中，一个顶点的入度比出度大1，而另一个顶点的出度比大入度1;欧拉通路的判定定理：（必须掌握！必须掌握！说明理由）证明较复杂证明较复杂 (略略) ，反证思维理解！反证思维理解！哈密尔顿图
42、：给定图G，如果存在一条经过G的每个每个顶点一次且恰好一次顶点一次且恰好一次的通路(回路)，则称该通路(回路)为哈密为哈密尔顿通路尔顿通路(回路回路)。具有哈密尔顿回路的图具有哈密尔顿回路的图称为哈密尔顿图哈密尔顿图。哈密尔顿图是否一定是初级回路？反之呢？哈密尔顿图是否一定是初级回路？反之呢？哈密尔顿图是否一定存在哈密尔顿通路？哈密尔顿图是否一定存在哈密尔顿通路？有向哈密尔顿图是强连通图？反之呢？有向哈密尔顿图是强连通图？反之呢？哈密尔顿图的充分必要条件至今仍未解决至今仍未解决。例例8.8 下列图哪些为哈密尔顿图？哪些存在哈密尔顿通道？：(1)(2)(3)(4)思考：思考： 哈密尔顿图与欧拉图
43、有联系吗？哈密尔顿图与欧拉图有联系吗？小结与学习要求小结与学习要求1. 本章围绕图中元素间的邻接与关联关系本章围绕图中元素间的邻接与关联关系讨论了图论中几个基本问题：图的连通性问题，讨论了图论中几个基本问题：图的连通性问题，道路问题，可达性问题，最短路径问题。道路问题，可达性问题，最短路径问题。2. 要仔细领会和掌握下列基本概念和相关要仔细领会和掌握下列基本概念和相关结论：子图、度、通路、回路、支、割点，割结论：子图、度、通路、回路、支、割点，割边，独立点，权，补图，同构图等。边，独立点，权，补图，同构图等。3. 熟练掌握标号法。熟练掌握标号法。例：例：v1v4v3v2e1e2e3e4e5e6e1e2e3e4e5e6v1v2v3v5v4例：例：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 82 结束语结束语