第七章图的基本概念§1无向图及有向图§2通路、回路、图的连通性§3图的矩阵表示§4最短路径及关键路径图(Graph)：可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。图是一类相当广泛的实际问题的数学模型，有着极其丰富的内容，是数据结构等课程的先修内容。学习时应掌握好图论的基本概念、基本
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
、基本算法，善于把实际问题抽象为图论的问题，然后用图论的方法解决问题。§1无向图及有向图本节介绍图的一些最常用的概念,主要有：无向图，有向图，边，顶点(或结点，点)，弧(或有向边)，顶点集，边集，n阶图，有限图，关联，多重图，简单图，完全图，母图,子图,生成子图，导出子图，补图，图的同构，入度，出度，度，孤立点等。主要定理：握手定理。[定义]图V是一个非空有限集，E是V上的一个二元关系，有序对
称为有向图(DirectedGraph)。可记为D.若将E中的有序对看成是无序的（即将e=看成e={a,b}或(a,b)），则称为无向图(UndirectedGraph)。有向图和无向图统称为图(Graph)，记为G。G=[定义]顶点Ｖ中的元素称为顶点，用带标记的点表示，也称为结点(Vertices)。[定义]边在有向图D中，若e=∈E，e称为D的有向边(directededge)。用由a到b带箭头的线把a和b连起来；在无向图G中，若e=(a,b)∈E，e称为G的无向边(undirectededge)。a,b间用连线连结。有向边和无向边统称为G的边(edge)。[定义]图的分类对图G=，若允许E是一个多重集合，则称图G为多重图(Multigraph)。其相同的元素称为平行边，平行边的条数称为重数。无环的非多重图称为简单图(SimpleGraph)。[定义]相邻和关联在无向图G中，若e=(a,b)∈E，则称a与b彼此相邻(adjacent)，或边e关联(incident)或联结(connect)a,b。a,b称为边e的端点或结束顶点(endpoint)。在有向图D中，若e=∈E，即箭头由a到b，称a邻接到b，或a关联或联结b。a称为e的始点(initialvertex)，b称为e的终点(terminal/endvertex)。[定义]孤立点若a∈V，a不与其他顶点相邻，称a为孤立点(isolatedvertex)。[定义]顶点的度在无向图G中，与a相邻的顶点的数目称为a的度(degree)。记为deg(a)或d(a)。在有向图D中，以a为终点的边的条数称为a的入度(in-degree)。记为deg–(a)或d–(a)。以a为始点的边的条数称为a的出度(out-degree)。记为deg+(a)或d+(a)。[定理1(握手定理Handshaking)]设无向图G=有n个顶点，m条边，则G中所有顶点的度之和等于m的两倍。即证明思路：利用数学归纳法。[定理2]无向图中度为奇数的顶点个数恰有偶数个。证明思路：将图中顶点的度分类，再利用定理1。[定理3]设有向图D=有n个顶点，m条边，则G中所有顶点的入度之和等于所有顶点的出度之和，也等于m。即：证明思路：利用数学归纳法。一些特殊的简单图：(1)无向完全图Kn(CompleteGraphs)(2)有向完全图(3)零图：E=.(4)平凡图：E=且|V|=1.(5)正则图：若图G＝中每个顶点的度均为n，称此图G是n-正则图(n-regulargraph)。完全图(n=1,2,3,4,5)[定理4]设无向完全图G有n个顶点，则G有n(n-1)/2条边。证明：每一顶点都与其余的n-1个顶点相邻，即每一顶点的度为n-1，共有n个顶点，则图G的度为n(n-1)，由握手定理，得边数m=n(n-1)/2.正则图（各顶点的度相同）3-正则图3-正则图[定义]子图设G=，G’=是两个图，若V’V，且E’E，则称G’为G的子图(subgraph)。注：当V’=V时，称G’为G的生成子图。当E’E，或V’V时，称G’为G的真子图。[定义]补图设G=是n阶无向简单图，以V为顶点集，以所有能使G成为完全图Kn的添加边组成的集合为边集的图，称为G相对于完全图Kn的补图，简称G的补图，记为。图G与其补图G’具有相同的顶点集，其边集不相交，构成相应完全图边集的划分。图A图B图C图D图E图F图Ａ是一个无向完全图图Ｂ，Ｃ，Ｄ，Ｅ，Ｆ均是Ａ的子图图Ｃ的顶点ａ是孤立顶点图Ｂ的边(ａ，ｂ)是孤立边图Ｄ是图Ｃ的子图图Ｅ是图Ｃ的补图例：例：例：有向图例：abcde2(a)1(b)3(d)4(c)5(e)例：(1)画出4个顶点3条边的所有可能非同构的无向简单图。(2)画出3个顶点2条边的所有可能非同构的有向简单图。•(1)(2)§2通路、回路、图的连通性连通性(Connectivity)[定义]通路(path)给定图G=，设图G中顶点和边的交替序列为T=v0e1v1e2…ekvk，若T满足如下条件：vi-1和vi是ei的端点(当G为有向图时，vi-1是ei的始点，vi是ei的终点)，i=1,2,…,k，则称T为顶点v0到vk的通路。此通路的长度为k。也可以用v0,v1,…,vk表示通路，v0为始点，vk为终点。当v0=vk时，该通路称为回路(circuit)。“巧渡河”问题问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能架船。图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。起始状态是“人狼羊菜”，结束状态是“空”。问题的解：找到一条从起始状态到结束状态的尽可能短的通路。“巧渡河”问题的解注意：在“人狼羊菜”的16种组合中允许出现的只有10种。[定义]简单通路(SimplePath)若通路中所有边互不相同，称此道路为简单通路。若回路中的所有边互不相同，称为简单回路(SimpleCircuit)。[定义]基本通路(ElementPath)一条通路中，除了始点和终点可以相同，其余顶点均互不相同，称此通路为基本通路(初级通路)。当其是回路时，称为基本回路(ElementCircuit初级回路或圈)。e5,e1,e2,e3,e4是简单通路，不是基本通路，因为c,a,b,c,d,b中b,c均出现了两次。但c,d,b,c是基本通路，也是基本回路。[定理]在一个n阶图中，若从顶点u到v(uv)存在通路，则从u到v存在长度小于等于n-1的基本通路。若存在v到自身的简单回路，则从v到自身存在长度不超过n的基本回路。证明：设T=v0e1v1…ekvk(v0=u,vk=v)为u到v的通路，若T上无重复出现的顶点，则T为基本通路。否则必存在t，若从vi到vj存在一条通路，则称vi到vj连通(connective)或可达。说明：对无向图而言，若vi到vj可达，则vj到vi也可达。对有向图而言则未必。[定理]任意一个连通无向图的任意两个不同顶点都存在一条简单通路。[定义]无向图的连通性若G=中任意两个顶点都连通，则称此无向图是连通的(connected)。[定义]连通分图(connectedcomponents)图G可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为G的连通分图。[定义]有向图的连通性(1)弱连通：若D=对应的无向图是连通图，则称G为弱连通(weaklyconnected)。(2)强连通：若D=中任意两点间都有通路，即对a和b，a到b可达，b到a可达，称G为强连通(stronglyconnected)。[定义]割点设G=是无向图，v∈V，若从G中删除顶点v后所得的连通分支数p(G-v)>p(G),则称v是G中的割点。割点设G=是无向图，e∈E，若从G中删除边e后所得的连通分支数p(G-e)>p(G),则称e是G中的割边。[定义]割边割边§3图的矩阵表示本节主要考虑三种矩阵，即关联矩阵，邻接矩阵与可达矩阵。关联矩阵反映的是顶点与边（弧）的关系；邻接矩阵反映的是顶点与顶点之间的关系；可达矩阵反映了图的联通情况。有向图与无向图将分别讨论。关联矩阵（incidencematrix）1.无向图的关联矩阵设无向图G=，V={v1,v2,…,vn},E={e1,e2,…,em}，令mij为顶点vi与边ej的关联次数，则称(mij)nm为G的关联矩阵，记为M(G)。显然mij的可能取值为0(vi与ej不关联)，1(vi与ej关联1次)，2(vi与ej关联2次，即ej是以vi为端点的环)。表示如下的无向图：v1v2v3e1e2e3e4e5v4关联矩阵（incidencematrix）要求D中无环存在2.有向图的关联矩阵设有向图D=，V={v1,v2,…,vn},E={e1,e2,…,em}，令则称(mij)nm为D的关联矩阵，记为M(D)。其关联矩阵为：v1v2v3e1e2e3e4v4e5邻接矩阵（adjacencymatrix）有向图的邻接矩阵设有向图D=，V={v1,v2,…,vn},|E|=m，令aij(1)为vi邻接到vj的边的条数，称(aij(1))nn为D的邻接矩阵，记为A(D)。其邻接矩阵为：v1v2v3v4接上例，计算A2,A3,A4如下：观察各矩阵发现，a13(2)=3,a13(3)=4,a13(4)=6，可知，D中v1到v3长度为2的通路有3条，长度为3的通路有4条，长度为4的通路有6条。a11(2)=1,a11(3)=1,a11(4)=1，可知，v1到自身长度为2,3,4的回路各有1条。[定理]设A为有向图D的邻接矩阵，V={v1,v2,…,vn}，则Al(l≥1)中元素aij(l)为vi到vj长度为l的通路数，为D中长度为l的通路总数，其中为D中长度为l的回路数。[推论]设Br=A+A2+…+Ar(r≥1)，则Br中元素bij(r)为D中vi到vj长度小于等于r的通路数，为D中长度小于等于r的通路总数，其中为D中长度小于等于r的回路总数。可达矩阵（reachablematrix）有向图的可达矩阵设有向图D=，V={v1,v2,…,vn},令称(pij)nn为D的可达矩阵，记为P(D)。定义可改为：接上例：即D的可达矩阵可通过邻接矩阵求得。§4最短路径及关键路径[定义]带权图对于有向图或无向图G的每条边附加一个实数w(e)，则称w(e)为边e上的权。G连同附加在各边上的实数称为带权图(weightedgraph)。记为G=.LetPbeanonemptypathinaweightedgraphG=(V,E,W)consistingofkedgesxv1,v1v2,…,vk-1y(possiblyv1=y).TheweightofP,denotedasW(P)isthesumoftheweightsw(xv1),w(v1v2),…,w(vk-1y).当无向边e=(vi,vj)或有向边e=时，w(e)也可记为wij.最短路径问题（shortestpathsproblem）设带权图G=，G中每条边带的权均大于等于0，x,y为G中任意两个顶点，从x到y的所有通路中带权最小的通路称为x到y的最短路径，求给定两顶点间的最短路径问题称为最短路径问题。(IfnopathbetweenxandyhasweightlessthanW(P),thenPiscalledashortestpath.)单源最短路径(Single-sourceshortestpaths)WearegivenaweightedgraphG=andasourcevertexs.Theproblemistofindashortestpathfromstoeachvertexv.Dijstra,EdsgarWybe(1930-)荷兰计算机科学家，1972年图林奖得主。最著名的成果：首先指出程序设计语言中的goto语句是有害的，并首创了结构化程序设计方法。至今仍被广泛应用的算法：解决机器人运动路径规划问题的“最短路径算法”。被引用最多的论断：“程序测试只能用来证明有错，绝不能证明无错。”被引用作为其60岁生日纪念论文集书名的另一句名言：Beautyisourbusiness求最短路径的Dijstra算法输入：连通带权图G，|V|=n,指定顶点sV输出：每个顶点v的标注(l(v),u),其中：l(v)即从s到v的最短路径长度。u是该路径上v的前一个顶点。求最短路径的Dijstra算法算法步骤：1.初始化：i=0,S0={s},l(s)=0,对其它一切vVG,将l(v)置为。若n=1，结束。2.vSi’=VG-Si,比较l(v)和l(ui)+w(ui,v)的值(uiSi)，如果l(ui)+w(ui,v)是有向带权图，|V|=n，若D是简单图（无平行边、无环），无回路。有一个顶点入度为0，称为发点，有一个顶点出度为0，称为收点。边的权wij表示时间。则称D为PERT图(PlanEvaluateReviseTechnologyGraph)。关键路径(Keypaths)在PERT图中求关键路径，就是求从发点到收点的一条最长路径，通过求各顶点的最早完成时间来求关键路径。最早完成时间自发点v1开始沿最长路径到达vi所需时间，称为vi的最早完成时间，记作TE(vi),i=1,2,…,n.显然，TE(v1)=0,vi(i1)的最早完成时间按如下公式计算：TE(vi)=max{TE(vj)+wij},i=2,3,…,n.vjTD-(vi)收点的TE(vn)就是从v1到vn的最长路径的权。最晚完成时间在保证收点vn的最早完成时间不增加的条件下，自v1最迟到达vi的时间，称为vi的最晚完成时间，记作TL(vi).显然，TL(vn)=TE(vn).in时的最晚完成时间按如下公式计算：TL(vi)=min{TL(vj)-wij},i=n-1,…,2,1.vjTD+(vi)缓冲时间ES(vi)=TL(vi)-TE(vi),i=1,2,…,n.注：在关键路径上，任何工序如果耽误了时间t，整个工程就耽误了时间t，因而在关键路径上各顶点的缓冲时间均为0。即若vi为关键路径上的顶点，则TL(vi)=TE(vi)。求关键路径的一个例子414046323411v2v5v1v3v7v8v4v62求关键路径的一个例子(续)各顶点的最早完成时间如下：TE(v1)=0;TE(v2)=max{0+1}=1;TE(v3)=max{0+2,1+0}=2;TE(v4)=max{0+3,2+2}=4;TE(v5)=max{1+3,4+4}=8;TE(v6)=max{2+4,8+1}=9;TE(v7)=max{1+4,2+4}=6;TE(v8)=max{9+1,6+6}=12.各顶点的最晚完成时间如下：TL(v8)=12;TL(v7)=min{12-6}=6;TL(v6)=min{12-1}=11;TL(v5)=min{11-1}=10;TL(v4)=min{10-4}=6;TL(v3)=min{6-2,11-4,6-4}=2;TL(v2)=min{2-0,10-3,6-4}=2;TL(v1)=min{2-1,2-2,6-3}=0.求关键路径的一个例子(续)各顶点的缓冲时间如下：TS(v1)=0-0=0;TS(v2)=2-1=1;TS(v3)=2-2=0;TS(v4)=6-4=2;TS(v5)=10-8=2;TS(v6)=11-9=2;TS(v7)=6-6=0;TS(v8)=12-12=0.关键路径为：v1v3v7v8.作业编一个程序实现Dijstra算法
浙公网安备 33021202002483