第六章图与网络分析.pptx

ABCDF哥尼斯堡七桥问题哥尼斯堡七桥问题在图中找一条经过每边一次且仅一次的路欧拉回路。ADBC由点和边组成第1页/共100页“环球旅行”问题在图中找一条经过每个点一次且仅一次的路哈密尔顿回路。F“中国邮路问题中国邮路问题”在图中找一条经过每边的最短路类似带权的欧拉回路。F“货郎担问题货郎担问题”在图中找一条经过每个点一次且仅一次的最短路带权的哈密尔顿回路。第2页/共100页1.图的基本概念 例 1:铁路交通图 例 2:球队比赛图点:表示研究对象.连线：表示两个对象之间的某种特定关系。关系的对称性：两对象之间的关系可互换。第3页/共100页 边：不带箭头的联线，表示对称关系。弧：带箭头的联线，表示不对称关系。无向图：简称图，有点和边组成。表示为：G=（V，E）V-点集合 E-边集合例：右图V=v1，v2，v3，v4 E=e1，e2，,e7e1=v1,v2e2=v1,v2,e7=v4,v4第4页/共100页 有向图：由点和弧组成。表示为：D=（V，A）V-点集合 A-弧集合点数:p(G)或 p(D)边数:q(G)弧数:q(D)v1v2v3v4v5例：右图V=v1，v2,v5A=a1，a2,a7a1=v1,v5,a2=v5,v4,a7=v1,v4第5页/共100页无向图的有关概念端点:e=u,vE,则u,v是e的端点,称u,v相邻.关联边:e是点u,v的关联边.环:若u=v,e是环.多重边:两点之间多于一条边.简单图:无环,无多重边的图.多重图:无环,允许有多重边的图.第6页/共100页 次（或度）:以点v为端点的边的个数称为v的次.表示为:d(v)悬挂点:次为1的点.悬挂边:悬挂点的关联边.孤立点:次为0的点.奇点:次为奇数的点.偶点:次为偶数的点.孤立点悬挂边第7页/共100页定理1:图G=(V,E)中,所有点的次之和是边数的两倍,即:定理2:任意一图中,奇点的个数为偶数.证明:设 V1-奇点的集合,V2-偶点的集合偶数偶数偶数第8页/共100页 链：点边交错系列，记为：圈：的链。初等链：点 均不相同。初等圈：点 均不相同。简单链：链中边均不相同。简单圈：圈中边均不相同。例：右图 无重复点,无重复边有重复点,无重复边第9页/共100页 连通图：任意两点之间至少有一条链。不连通图：连通分图：对不连通图，每一连通的部分称为一个连通分图。支撑子图：对G=（V，E），若G=(V,E),使V=V,E E,则G是G的一个支撑子图（生成子图）.G-v:图G去掉点v及v的关联边的图.第10页/共100页有向图的有关概念基础图:对D=(V,A),去掉图上的箭头.始点和终点:对弧a=(u,v),u为a的始点,v为a的终点.链:点弧交错序列,若在其基础图中对应一条链,则称为 D的一条链.圈,初等链,初等圈:类似定义.方向可以不同第11页/共100页 道路:若 是D中的一条链，且 ，t=1,2,k-1,称之为从 到 的一条道路。回路:的路.初等路:道路中点不相同.初等回路:回路中点不相同.简单有向图:无自环,无多重弧.多重有向图:有多重弧.方向相同第12页/共100页图的矩阵表示设图G=（V，E），其中n阶方阵 称为的邻接矩阵，其中第13页/共100页欧拉图欧拉图：具有欧拉回路的图定理3 一个连通图 为欧拉图的充要条件是 的每一个结点的度均为偶数。例如，哥尼斯堡七桥不存在一条欧拉回路，所以哥尼斯堡七桥问题的回答是否定的。第14页/共100页哈密顿图（具有哈密顿回路的图）哈密顿回路：经过图的每个结点一次且仅一次的回路。类似于确定哈密顿回路的问题是流动售货员的问题，流动售货员要从公司出发走销附近的所有城镇，然后返回所在地，那么如何安排他的路线，使得旅行的总距离最小。第15页/共100页2.树2.1 树及其性质2.2 图的支撑树（生成树）2.3最小支撑树问题2.4 根树及其应用第16页/共100页2.1 树及其性质例:电话线架设、比赛程序、组织结构等。树:连通的无圈的无向图称为树。第17页/共100页树的性质：树的性质：图G=（V，E），p个点、q条边下列说法是等价的（1）G是一个树（2）G连通，且恰有p-1条边。（3）G无圈，且恰有p-1条边。（4）G连通，但每舍去一边就不连通。（5）G无圈，但每增加一边即得唯一一个圈。（6）G中任意两点之间恰有一条链(简单链)。第18页/共100页2.2 图的支撑树（生成树）定义:设图T=(V，E)是图G=(V,E)的支撑子图,如果T是一个树,则称T是G的一个支撑树。定理5：图G=（V，E）有支撑树的充分必要条件是G是连通的。第19页/共100页找图中生成树的方法：找图中生成树的方法：求支撑树的破圈法第20页/共100页求支撑树的避圈法找图中生成树的方法：找图中生成树的方法：深探法广探法第21页/共100页2.3最小支撑树问题赋权图(网络）:给图G=(V,E),对G中的每一条边vi,vj,相应地有一个数wij,则称这样的图为赋权图,wij 称为边vi,vj上的权.支撑树的权:若T=(V,E)是G的一个支撑树,E中的所有边的权之和称为支撑树的权,记为w(T):第22页/共100页 定义:最小支撑树(最小树)T*:求最小树的 避圈法:例:图8-27求最小树的 破圈法:例:图8-28 第23页/共100页2.4 根树及其应用有向树中根树在计算机科学、决策论的应用F有向树：有向树：F根树：有向树根树：有向树T，恰有一个结恰有一个结点入次为点入次为0，其余各点入次为，其余各点入次为1，则称，则称T为根树。为根树。FM叉树：叉树：F二叉树：结点的出度都小于二叉树：结点的出度都小于等于等于2。根叶分点枝第一层第三层第二层三叉树第24页/共100页带权的二叉树T：有s个叶子，权分别为pi，根到各叶子的距离（层次）为二叉树的总权数F最优二叉树（最优二叉树（Huffman树）：总权数最小的二叉树树）：总权数最小的二叉树F算法步骤：算法步骤：Huffman算法算法将将s个叶子按权由小到大排列，个叶子按权由小到大排列，将两个最小的叶子合并为一个分枝点，其权为两者之和，将新的分枝点作为将两个最小的叶子合并为一个分枝点，其权为两者之和，将新的分枝点作为一个叶子，转上一步，直到结束。一个叶子，转上一步，直到结束。第25页/共100页例1、s=6，其权分别为4，3，2，2，1，求最优二叉树。123243365第26页/共100页例1、s=6，其权分别为4，3，2，2，1，求最优二叉树。123243396515123243396515第27页/共100页例2、最优检索问题。使用计算机进行图书分 类。现有五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册，问如何安排分检过程，可使总的运算（比较）次数最小？第28页/共100页例3：P235、例110.050.450.050.080.120.25一等品五等品四等品三等品二等品等外品0.100.300.180.551.0测试顺序第29页/共100页 3.最短路问题3.1 引例单行线交通网：v1到v8使总费用最小的旅行路线。最短路问题的一般描述：对D=（V，A），a=（vi，vj），w（a）=wij，P是vs到vt的路，定义路P的权是P中所有弧的权的和，记为w（P）第30页/共100页 路P0的权称为从vs到vt的距离，记为：d（vs，vt）3.2最短路算法Dijkstra算法：有向图，wij0一般结论则最短路问题为：第31页/共100页 Dijkstra算法基本思想P标号：已确定出最短路的节点的距离。T标号：为确定出最短路的节点，但表示其距离的上限。Si：P标号节点的集合。(v)：最短路中前一个节点的编号。初始值：第32页/共100页 例:第33页/共100页 第34页/共100页 第35页/共100页 第36页/共100页 第37页/共100页 第38页/共100页 第39页/共100页 第40页/共100页 总结:算法步骤:第41页/共100页 Dijkstra算法：无向图求最短链，wij0存在负权时求最短路问题 第42页/共100页4.网络最大流问题4.1基本概念和基本定理网络与流定义:对有向图D=(V,A):vs 源 vt 汇 其余-中间点c(vi,vj)-弧(vi,vj)的容量,简写为cijD=(V,A,C)-网络 fij-弧(vi,vj)上的流量第43页/共100页第44页/共100页 可行流与最大流可行流满足:流入量=流出量流出量流入量第45页/共100页 最大流问题第46页/共100页 增广链:几个概念:对可行流例:图10-23第47页/共100页 增广链:设f是一可行流,时从始点到终点的一条链,若满足下列条件,称其为一条增广链.例:图10-24截集和截量设 把始点在S,终点在T中的所有弧构成的集合,记为(S,T).可增加流量的链第48页/共100页 定义:截集定义:截量 第49页/共100页 几点结论第50页/共100页4.2求最大流的标号法网络中的点分为:标号点标号未检查点标号已检查点未标号点第51页/共100页 1)标号过程第52页/共100页 2)调整过程:沿增广链调整流量.例:图10-25第53页/共100页5.最小费用最大流定义:对D=(V,A,C),给定一个单位流量的费用bij0,最小费用最大流即:求一最大流f,使 对增广链,若调整流量=1,那么新可行流f的费用比原可行流f的费用增加:第54页/共100页 此为增广链的费用.最小费用最大流的求解构造赋权有向图w(f),定义:第55页/共100页 在w(f)中找最小费用增广链,直至没有最小费用增广链为止.若存在最小费用增广链,调整流量如下:第56页/共100页求最小费用最大流算法初初始始网网络络数数值值VsV1 V2 V3 Vt 第57页/共100页求最小费用最大流算法(4,10)(1,8)(2,4)(1,7)(2,5)(6,2)(4,10)bij Cij初初始始网网络络数数值值VsV1 V2 V3 Vt 第58页/共100页求最小费用最大流算法取初始取初始可行流可行流f(0)=0V1 V2 V3 Vs Vt 第59页/共100页求最小费用最大流算法(4,0)(1,0)(2,0)(1,0)(2,0)(6,0)(4,0)取初始取初始可行流可行流f(0)=0V1 V2 V3 Vs Vt bij fij第60页/共100页求最小费用最大流算法(4,0)(1,0)(2,0)(1,0)(2,0)(6,0)(4,0)取初始取初始可行流可行流f(0)=0构造赋构造赋权图权图W(f(0)V1 V2 V3 Vs Vt 第61页/共100页求最小费用最大流算法(4,0)(1,0)(2,0)(1,0)(2,0)(6,0)(4,0)取初始取初始可行流可行流f(0)=0构造赋构造赋权图权图W(f(0)V1 V2 V3 Vs Vt 第62页/共100页求最小费用最大流算法(4,0)(1,0)(2,0)(1,0)(2,0)(6,0)(4,0)取初始取初始可行流可行流f(0)=0构造赋构造赋权图权图W(f(0)(+,0)V1 V2 V3 Vs Vt 第63页/共100页求最小费用最大流算法(4,0)(1,0)(2,0)(1,0)(2,0)(6,0)(4,0)在初始在初始赋权图赋权图W(f(0)上求出上求出最短路最短路V1 V2 V3 Vs Vt 第64页/共100页求最小费用最大流算法(4,0)(1,5)(2,0)(1,5)(2,5)(6,0)(4,0)在最短在最短路上增路上增加流量加流量V1 V2 V3 Vs Vt 第65页/共100页求最小费用最大流算法(4,0)(2,0)(6,0)(4,0)在最短在最短路上增路上增加流量加流量原流量原流量如图所如图所示示V1 V2 V3 Vs Vt(1,0)(1,0)(2,0)第66页/共100页求最小费用最大流算法(4,0)(2,0)(6,0)(4,0)求求增增加加的的流流量量V1 V2 V3 Vs Vt 8-0 5-0 7-0最小最小f(0)(1,0)(1,0)(2,0)第67页/共100页求最小费用最大流算法(4,0)(1,5)(2,0)(1,5)(2,5)(6,0)(4,0)在最短在最短路上增路上增加流量加流量 =5得到新得到新的流量的流量f(1)=5V1 V2 V3 Vs Vt 第68页/共100页求最小费用最大流算法(4,0)(1,5)(2,0)(1,5)(2,5)(6,0)(4,0)依据新依据新的流量的流量构造又构造又一赋权一赋权图图W(f(1)*只对增广链只对增广链V1 V2 V3 Vs Vt 8第69页/共100页求最小费用最大流算法(4,0)(2,0)(1,5)(2,5)(6,0)(4,0)赋赋权权图图W(f(1)的构造的构造*只对增广链只对增广链V1 V2 V3 Vs Vt 8(-1,5)(1,5)第70页/共100页求最小费用最大流算法(4,0)(2,0)(1,5)(2,5)(6,0)(4,0)赋赋权权图图W(f(1)的构造的构造*只对增广链只对增广链V1 V2 V3 Vs Vt 8 5(-1,5)(1,5)第71页/共100页求最小费用最大流算法(4,0)(2,0)(1,5)(6,0)(4,0)赋赋权权图图W(f(1)的构造的构造*只对增广链只对增广链V1 V2 V3 Vs Vt 8 5(-2,5)7(-1,5)(-1,5)(1,5)第72页/共100页求最小费用最大流算法(4,0)(2,0)(1,5)(6,0)(4,0)构造的构造的赋权赋权图图W(f(1)*只对增广链只对增广链V1 V2 V3 Vs Vt(-2,5)(-1,5)(-1,5)(1,5)第73页/共100页求最小费用最大流算法(4,0)(2,0)(1,5)(6,0)(4,0)在在赋赋权图权图W(f(1)上求出上求出最短路最短路V1 V2 V3 Vs Vt(-2,5)(-1,5)(-1,5)(1,5)第74页/共100页求最小费用最大流算法Vs(4,0)(1,5)(2,0)(1,5)(2,5)(6,0)(4,0)在最短在最短路上增路上增加流量加流量V1 V2 V3 Vs Vt 7-5=2 10-0 最小最小第75页/共100页求最小费用最大流算法Vs(4,2)(1,5)(2,0)(1,7)(2,5)(6,0)(4,0)=2得到新得到新的流量的流量f(2)=7新的流新的流量图如量图如图所示图所示V1 V2 V3 Vs Vt 第76页/共100页求最小费用最大流算法依据新的流量构造又一赋权图W(f(2)*只对增广链V1(4,0)(1,5)(2,0)(1,5)(6,0)(4,0)V1 V2 V3 Vs Vt(-1,5)(-2,5)(-1,5)第77页/共100页求最小费用最大流算法对最短路上求新的权值V1(4,2)(1,5)(2,0)(1,7)(6,0)(4,0)V1 V2 V3 Vs Vt(-1,5)(-2,5)10第78页/共100页求最小费用最大流算法赋权图的构造W(f(2)*只对增广链V1(4,2)(1,5)(2,0)(1,7)(6,0)(4,0)V1 V2 V3 Vs Vt(-1,5)(-2,5)(-4,2)第79页/共100页求最小费用最大流算法赋权图的构造W(f(2)*只对增广链V1(4,2)(-1,5)(2,0)(1,7)(6,0)(4,0)V1 V2 V3 Vs Vt(1,5)(-2,5)7(-4,2)第80页/共100页求最小费用最大流算法赋权图的构造W(f(2)*只对增广链V1(4,2)(2,0)(-1,7)(6,0)(4,0)V1 V2 V3 Vs Vt(-2,5)(-4,2)(-1,5)(1,5)第81页/共100页求最小费用最大流算法新赋权图W(f(2)*只对增广链V1(4,2)(2,0)(-1,7)(6,0)(4,0)V1 V2 V3 Vs Vt(-2,5)(-4,2)(-1,5)(1,5)第82页/共100页求最小费用最大流算法在赋权图W(f(2)上求出最短路V1(4,2)(2,0)(-1,7)(6,0)(4,0)V1 V2 V3 Vs Vt(-2,5)(-4,2)(-1,5)(1,5)第83页/共100页求最小费用最大流算法(4,2)(1,5)(2,0)(1,7)(2,5)(6,0)(4,0)在最短在最短路上增路上增加流量加流量 =3V1 V2 V3 Vt 8-5=3 最小最小 10-0 4-0第84页/共100页求最小费用最大流算法(4,2)(1,8)(2,3)(1,7)(2,5)(6,0)(4,3)在最短在最短路上增路上增加流量加流量 =3得到新得到新的流量的流量f(3)=10V1 V2 V3 Vt 第85页/共100页求最小费用最大流算法依据新的流量构造又一赋权图W(f(3)*只对增广链V1(4,2)(2,3)(-1,7)(6,0)(4,3)V1 V2 V3 Vs Vt(-2,5)(-1,5)(-4,2)(1,8)8 10 4第86页/共100页求最小费用最大流算法赋权图W(f(3)的构造*只对增广链V1(4,2)(2,3)(-1,7)(6,0)(4,3)V1 V2 V3 Vs Vt(-2,5)(-1,5)(-4,2)(-1,8)(-4,3)(-2,3)第87页/共100页求最小费用最大流算法在赋权图W(f(3)上求出最短路V1(4,2)(2,3)(-1,7)(6,0)(4,3)V1 V2 V3 Vs Vt(-2,5)(-1,5)(-4,2)(-1,8)(-4,3)(-2,3)第88页/共100页求最小费用最大流算法在初始赋权图W(f(0)上求出最短路V1(4,2)(2,3)(-1,7)(6,0)(4,3)V1 V2 V3 Vs Vt(-2,5)(-1,5)(-4,2)(-1,8)(-4,3)(-2,3)第89页/共100页求最小费用最大流算法(4,2)(1,8)(2,3)(1,7)(2,5)(6,0)(4,3)在最短在最短路上增路上增加流量加流量V1 V2 V3 Vt 5 最小最小 10-3 4-3=1 10-2 第90页/共100页求最小费用最大流算法(4,3)(1,8)(2,4)(1,7)(2,4)(6,0)(4,4)在最短在最短路上增路上增加流量加流量 =1得新的得新的流量流量f(4)=11V1 V2 V3 Vt 第91页/共100页求最小费用最大流算法(4,3)(1,8)(2,4)(1,7)(2,4)(6,0)(4,4)*注意注意在负向在负向弧上减弧上减去增量去增量值值V1 V2 V3 Vt 5-1 第92页/共100页求最小费用最大流算法上一次的赋权图*依据新流量在最短路径上对此重求赋权值V1(4,2)(2,3)(-1,7)(6,0)(4,3)V1 V2 V3 Vs Vt(-2,5)(-4,2)(-1,8)(-4,3)(-2,3)第93页/共100页求最小费用最大流算法依据新的流量构造又一赋权图W(f(4)*只对增广链V1(4,3)(2,4)(-1,7)(6,0)(4,4)V1 V2 V3 Vs Vt(2,4)(1,8)10 5 10 4 第94页/共100页求最小费用最大流算法依据新的流量构造又一赋权图W(f(4)*只对增广链V1(4,3)(-2,4)(-1,7)(6,0)(3,4)V1 V2 V3 Vs Vt(-2,4)(-4,3)(-1,8)(-3,4)(2,4)第95页/共100页求最小费用最大流算法没有最短路，算法结束，所得为最小费用最大流V1(4,3)(-2,4)(-1,7)(6,0)(3,4)V1 V2 V3 Vs Vt(-2,4)(-4,3)(-1,8)(-3,4)(2,4)只有出弧第96页/共100页6.中国邮递员问题6.1一笔划问题欧拉链:图中存在一条链,过每边一次且仅一次.欧拉圈:图中存在一简单圈,过每边一次.欧拉图:具有欧拉圈的图.第97页/共100页 定理:连通多重图G是欧拉图,当且仅当G中无奇点.推论:连通多重图G有欧拉链,当且仅当G恰有两个奇点.奇偶点作业法 若图中无奇点,问题已解决;否则:第一可行方案的确定:奇点配对,找奇点间的一条链.调整可行方案,使重复边总长度下降第98页/共100页 a)最优方案中,每一边上最多有一条重复边.b)最优方案中,每个圈上重复边的总权不大于圈总权的一半.最优性判定:满足a)和b)两条.第99页/共100页感谢您的观看！第100页/共100页