图与网络分析课件

第八章第八章图与网络分析图与网络分析第一节 图与网络的基本知识第二节 树第三节 最短路问题第四节 最大流问题第五节 最小费用流问题讲五节：惨泳蝇盅搪古炒委北埠如辈陛熄灵滁闲首翌坦缚缮镀须湿柑裁靠免欢紧缠+8+图与网络分析+8+图与网络分析7/15/20241第八章图与网络分析第一节 图与网络的基本知识讲五节：8-1 8-1 8-1 8-1 图与网络的基本知识图与网络的基本知识图与网络的基本知识图与网络的基本知识一、图与网络的基本概念一、图与网络的基本概念1、图及其分类图图图图是反映对象之间关系的一种工具。例如，在一个人群中，对相互认识这种关系可以用图来表示。赵(v1)钱(v2)孙(v3)李(v4)周(v5)吴(v6)陈(v7)若将“相互认识”的关系改成“认识”，可以用带箭头的连线表示。顶点边定定定定义义义义1 1 1 1 一个图是由点集V=vi和V中元素的无序对的一个集合E=ek所构成的二元组,记为G=(V,E),V中的元素vi叫做顶点顶点顶点顶点,E中的元素ek叫做边边边边。当V，E为有限集合时,G称为有限图,否则,称为无限图e1e2e3e4e5V=vi=v1,v2,v7E=ei=e1,e2,e5返回第八章目录焊蓉挪即蚂布蹿避选懒欺匀盗朝磐湛恒鄂系和息追缉蛤瘦靠洛枯匠鲁朝漱+8+图与网络分析+8+图与网络分析7/15/202428-1 图与网络的基本知识一、图与网络的基本概念赵(v1例例1 1 在图在图8-78-7中中：V V=v v1 1,v v2 2,v v3 3,v v4 4,v v5 5 E E=e e1 1,e e2 2,e e3 3,e e4 4,e e5 5,e e6 6 两条边ei,ej 属于E，如果它们有公共端点u，则称ei,ej相邻。边ei,ej称为u的关联边。对于任一条边(vi,vj)属于E，如果边(vi,vj)端点无序，则它是无向边，此时图为无向图.图8-7是无向图.如果边(vi,vj)端点有序,即它表示以vi为始点,vj为终点的有向边(或称弧),这时图G称为有向图。一条边的两个端点如果相同,称此边为环(自回路).如图8-7中的e1。两个点之间多于一条边的，称为多重边,如图8-7中的e4,e5。其中：e1=(v1,v1)；e2=(v1,v2)；e3=(v1,v3)e4=(v2,v3)；e5=(v2,v3)；e6=(v3,v4)两个点u,v属于V,如果边(u,v)属于E,则称u,v两点相邻。u,v称为边(u,v)的端点。e1v1e2v2e4e5v3v4e6v5图 8-7e3义鼻颅眼旺圃蛇触刀悯弛乙叫瀑违寇尽孔岔酪祥茄讹班橙豺疏怨倚锄歉意+8+图与网络分析+8+图与网络分析7/15/20243例1 在图8-7中：V=v1,v2,v3,v4,v5定定定定义义义义 2 2 2 2 不不含含环环和和多多重重边边的的图图称称为为简简简简单单单单图图图图，含含有有多多重重边边的图称为的图称为多重图多重图多重图多重图。有向图中两点之间有不同方向的两条边，不是多重边有向图中两点之间有不同方向的两条边，不是多重边有向图中两点之间有不同方向的两条边，不是多重边有向图中两点之间有不同方向的两条边，不是多重边。定义义3 3 每一对顶点间都有边相连的无向简单图称为完完完完全全全全图图图图。有n个顶点的无向完全图记作Kn。每一对顶点间有且仅有一条有向边的简单图，称为有有有有向向向向完全图完全图完全图完全图。(b)(c)(a)(d)图 8-8简单图简单图多重图多重图器奋挥捉喧淳绷鞠皿睦孜重倡淘吞钟泽崭膳涝黎层少挂蹲骡鸵苔召虐兴锹+8+图与网络分析+8+图与网络分析7/15/20244定义 2 不含环和多重边的图称为简单图，含有多重边的图称为定定定定义义义义4 4 4 4 图图G G(V,E V,E)的的点点集集V V可可以以分分为为两两个个非非空空子子集集X X，Y Y，即即X XU UY YV V,X XY Yf f，使使得得E E中中每每条条边边的的两两个个端端点点必必有有一一个个端端点点属属于于X X，另另一一个个端端点点属属于于Y Y，则则称称G G为为二二部部图图(偶偶图图)，有有时时记作记作G G(X X,Y Y,E E)。例如图8-9中的(a)是明显的二部图，点集X：v1,v3,v5)，Y：v2,v4,v6，(b)也是二部图，但是不像(a)那样明显，改画为(c)时可以清楚地看出。v1v2v6v5v3v4(a)v4v1v3v2(b)v1v2v4v3(c)图 8-9爸蜡开要命缘鹿瘴硬刊赘忻遏激逊忘躲台法触搪搁刃肉师卉彩炬韦孜项悍+8+图与网络分析+8+图与网络分析7/15/20245定义4 图G(V,E)的点集V可以分为两个非空子集X2.2.顶点的次顶点的次定义定义定义定义5 5 以点以点v v为端点的边数叫做点为端点的边数叫做点v v的的次次次次,记作记作deg(deg(v v),简记简记d(d(v v)。如 图 8-7中 点 v1的 次d(v1)=4,因为边e1要计算两次。点 v3的 次 d(v3)=4，点 v4的 次d(v4)=1。次为1的点称为悬悬悬悬挂挂挂挂点点点点,连接悬挂点的边称为悬悬悬悬挂挂挂挂边边边边.如8-7图中v4,e6。次为零的点称为孤孤孤孤立立立立点点点点，如图8-7中的点v5。次为奇数的点称为奇奇奇奇点点点点。次为偶数的点称为偶点偶点偶点偶点。e1v1e2v2e4e5v3v4e6v5图 8-7e3定理定理定理定理1 1 1 1 任何图中，顶点次数的总和等于边数的2倍。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。悬挂点悬挂边孤立点奇点偶点偶点郭辩篷混怖凛堡无悔筷蜘藻钧集弛乎滁泥埋奠瓮棋般虽涣共廖化本孔怒趟+8+图与网络分析+8+图与网络分析7/15/202462.顶点的次定义5 以点v为端点的边数叫做点v的次,记定理定理定理定理2 2 2 2 任何图中，次为奇数的顶点必为偶数个任何图中，次为奇数的顶点必为偶数个。证明：设证明：设V V1 1和和V V2 2分别为分别为G G中奇点与偶点的集合中奇点与偶点的集合(V(V1 1UVUV2 2=V).=V).由定由定理理1 1知知定定义义6 6 有向图中,以vi为始点的边数称为点vi的出出出出次次次次，用d+(vi)表示；以vi为终点的边数称为点vi的入入入入次次次次，用d(vi)表示。点的出次与入次之和就是该点的次。容易证明有向图中，所有顶点的入次之和等于出次之和。3.3.子图子图 定定义义7 7 图G=(V,E),若E是E的子集,V是V的子集，且E中的边仅与V中的顶点相关联，则称G=(V,E)是G的一个子图子图子图子图。特别地，若V=V，则G称为G的生成子图生成子图生成子图生成子图。骋浓抹非伦拔牟梯嘿益晶纶四森抡很潍晌囤复殿恬码娠氰鉴糊尝缠慨璃挣+8+图与网络分析+8+图与网络分析7/15/20247定理2 任何图中，次为奇数的顶点必为偶数个。证明：设V1和v4v1v5v3v2v6v7e8e4e9e6e7(c)上图中，(b)为(a)的子图子图子图子图，(c)为(a)的生成子图生成子图生成子图生成子图。4.4.网络网络网络网络在实际问题中，只用图来描述所研究对象之间的关系往往是不够的，与图联系在一起的，通常还有与点或边有关的某些数量指标，我们常称之为“权权权权”，权可以代表如距离、费用、通过能力（容量）等等。这种点点点点或或或或边边边边带有某种数量指标的图称为网络带有某种数量指标的图称为网络带有某种数量指标的图称为网络带有某种数量指标的图称为网络(赋权图)。VV,EEVV,EE.且V=Vv5v6v3v2v1e1e6v5v4(b)v7v5v2v1e10e7e9e8v3e4e5e1e2e6v4v6(a)e3寄颓哦罗窟窃劫吊挽陪嚎捐臂练恭唯宇农驳幻晦刨坑颂衔扣欧漱包亏蟹量+8+图与网络分析+8+图与网络分析7/15/20248v4v1v5v3v2v6v7e8e4e9e6e7(c)上图中二、连通图二、连通图二、连通图二、连通图e7v5v4v3v2v1v6e1e3e4e5e6e8e9e10e2图 8-12图图图图 8-12 8-12 中，中，中，中，S=S=v v6 6,e e6 6,v v5 5,e e7 7,v v1,1,e e8 8,v v5 5,e e7,7,v v1 1,e e9 9,v v4 4,e e4 4,v v3 3 为一条连结为一条连结为一条连结为一条连结v v6 6,v v3 3的链。的链。的链。的链。S S1 1=v v6 6,e e6 6,v v5 5,e e7 7,v v1 1,e e8 8,v v5 5,e e5 5,v v4 4,e e4 4,v v3 3 为一条连结为一条连结为一条连结为一条连结v v6 6,v v3 3的简单链。的简单链。的简单链。的简单链。S S2 2=v v6 6,e e6 6,v v5 5,e e5 5,v v4 4,e e4 4,v v3 3 为初等为初等为初等为初等链。链。链。链。定定义义9 无向图G中,连结vi0与vik的一条链，当vi0与vik是同一个点时,称此链为圈圈圈圈.圈中只有重复点而无重复边者为简简简简单单单单圈圈圈圈，既无重复点也无重复边者为初初初初等等等等圈圈圈圈，有向图当链(圈)上的边方向相同时,称为道路道路道路道路(回路)。v1,e7,v5,e8,v1,e9,v4,e10,v2,e2,v1为一个圈。有恃拨岩谋临祥鞠整骆水戚对敞衙匹沟条爷冷神绰啸阜润嘴厢社郑狙族水+8+图与网络分析+8+图与网络分析7/15/20249二、连通图e7v5v4v3v2v1v6e1e3e4e5e6e对于有向图可以类似于无向图定义链和圈，初等链、圈，对于有向图可以类似于无向图定义链和圈，初等链、圈，简单链、圈，此时不考虑边的方向。而当链（圈）上的边方简单链、圈，此时不考虑边的方向。而当链（圈）上的边方向相同时，称为道路（回路）。向相同时，称为道路（回路）。图图图图 8-13 8-13 中中中中,S=S=v v6 6,e e6 6,v v5 5,e e8 8,v v1 1,e e9 9,v v4 4,e e1010,v v2 2,e e3 3,v v3 3 为一条为一条为一条为一条链。链。链。链。S S1 1=v v6 6,e,e6 6,v,v5 5,e,e7 7 ,v,v1 1,e,e9 9 ,v,v4 4,e,e4 4 ,v,v3 3 为一条道路。为一条道路。为一条道路。为一条道路。S S2 2=v v1 1 ,e,e2 2 ,v,v2 2 ,e,e1111 ,v,v4 4 ,e,e5 5 ,v,v5 5 ,e e8 8 ,v,v1 1 为一个圈。为一个圈。为一个圈。为一个圈。S S3 3=v v1 1,e,e2 2 ,v,v2 2 ,e,e1010 ,v,v4 4 ,e,e5 5 ,v,v5 5 ,e,e7 7,v,v1 1 为一个回为一个回为一个回为一个回路。路。路。路。e7v5v4v3v1v6v2e10e 11e3e2e5e9e8e1e6图 8-13e4定定定定义义义义10 10 10 10 一一一一个个个个图图图图中中中中任任任任意意意意两两两两点点点点间间间间至至至至少少少少有有有有一一一一条条条条链链链链相相相相连连连连，则则则则称称称称此此此此图图图图为为为为连连连连通通通通图图图图。任任任任何何何何一一一一个个个个不不不不连连连连通通通通图图图图都都都都可可可可以以以以分分分分为为为为若若若若干干干干个个个个连连连连通通通通子子子子图图图图，每每每每一一一一个个个个连连连连通通通通子子子子图图图图称称称称为为为为原原原原图图图图的的的的一个分图。一个分图。一个分图。一个分图。饶局餐呻奇错背熏斤蔓夸涸汽诊恤万饵蜕溯樊翰护秋嚏付动煎汪搭癌烹总+8+图与网络分析+8+图与网络分析7/15/202410对于有向图可以类似于无向图定义链和圈，初等链、圈，简单链、圈三、图的矩阵表示三、图的矩阵表示三、图的矩阵表示三、图的矩阵表示定定义义1111 网络(赋权)图G=(V,E),其边(vi,vj)有权wij，构造矩阵A=(ai j)nn，其中例例2 图示 8-14所示的图 其权矩阵为：称矩阵A为网络G的权矩阵。6v5v4v3v2v1754238图 8-1494v1v1v2v3v4v5v2v4v5胺搔缕菱删檀炼皱共芍套剖柜简嫂忍粉崩愤检型宁坝卖押牙肚杖舜奄持苍+8+图与网络分析+8+图与网络分析7/15/202411三、图的矩阵表示定义11 网络(赋权)图G=(V,E),定义定义定义定义12121212 对于图对于图G=(V,E),|V|=n,G=(V,E),|V|=n,构造一个矩阵构造一个矩阵A=(aA=(aij ij)n n n n,其中：其中：则称矩阵A为图G的邻接矩阵。邻接矩阵。例例3 3 对图8-15所表示的图可以构造邻接矩阵A如下：v1v2v3v4v6v5 图图 8-15v1v2v3v4v5v6当当当当G为为为为无无无无向向向向图图图图时时时时，邻邻邻邻接接接接矩阵为对称矩阵。矩阵为对称矩阵。矩阵为对称矩阵。矩阵为对称矩阵。烁绊份抛宇畏痴棱可懊够缄粟升雁头历奸霓舜坦量摄江檄皋赔记斩底子筒+8+图与网络分析+8+图与网络分析7/15/202412定义12 对于图G=(V,E),|V|=n,构造一个矩阵A=四、欧拉回路与中国邮路问题四、欧拉回路与中国邮路问题四、欧拉回路与中国邮路问题四、欧拉回路与中国邮路问题1.欧拉回路与道路定定义义13 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧欧欧欧拉拉拉拉道道道道路路路路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路欧拉回路欧拉回路欧拉回路。具有欧拉回路的图称为欧拉图欧拉图欧拉图欧拉图（E图）。定理定理定理定理3 3 3 3 无向连通图G是欧拉图，当且仅当G中无奇点。推论1 无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路。推论2 无向连通图G有欧拉道路，当且仅当G中恰有两个奇点。定定定定理理理理4 4 4 4 连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。连通有向图G有欧拉道路，当且仅当这个图中除去两个顶点外，其余每一个顶点的出次等于入次，且这两个顶点中，一个顶点的入次比出次多1，另一个顶点 的入次比出次少1。从鞋恨舵晚升腰迭盒搞猫隋婶呀墨腐墓公佣蝇痔枣笨汽嘲枷茎耍药旅洋观+8+图与网络分析+8+图与网络分析7/15/202413四、欧拉回路与中国邮路问题1.欧拉回路与道路从鞋恨舵晚升腰2.2.2.2.中国邮路问题中国邮路问题中国邮路问题中国邮路问题一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？国际上通称这个问题为中国邮路问题。用图论的语言描述：给定一个连通图，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。中国邮路问题也可以转为如下问题中国邮路问题也可以转为如下问题：在连通图G=(V,E)中，求一个边集E1E，把G中属于E1的边均变为二重边得到图G*=G+E1，使其满足 G*无奇点,且L(E1)=Sl(e)(eE1)最小。定定定定理理理理5 5 5 5 己知图G*=G+E1无奇点 ,则L(E1)=Sl(e)(eE1)最小的充分必要条件为：（1）每条边最多重复一次；（2）对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。定理给出了中国邮路问题的一种算法，称为“奇偶点图上作业法”，下面举例说明这个算法。认伦韦长权亭耳丝捡噶箱贤瞥弘窝哗菇嫡隐弗臣壹晦阴喇丙鼠恤烃霸渭华+8+图与网络分析+8+图与网络分析7/15/2024142.中国邮路问题一个邮递员，负责某一地区的信件投递。他每天例例例例 4 4 4 4 求解图求解图 8-16 8-16所示网络的中国邮路问题所示网络的中国邮路问题第一步：确定初始可行方案。第一步：确定初始可行方案。先先检检查查图图中中是是否否有有奇奇点点，如如无无奇奇点点则则己己是是欧欧拉拉图图，找找出出欧欧拉拉回回路路即即可可。如如有有奇奇点点，由由前前知知奇奇点点个个数数必必为为偶偶数数，所所以以可可以以两两两两配配对对。每每对对点点间间选选一一条路，使这条路上均为二重边。条路，使这条路上均为二重边。图图8-168-16中中有有四四个个奇奇点点v v2 2,v v4 4,v v6 6,v v8 8，将将v v2 2与与v v4 4,v v6 6,v v8 8配配对对，联联结结v v2 2与与v v4 4的的路路有有好好几几条条，任任取取一一条条，如如 v v2 2,v v3 3,v v6 6,v v9 9,v v8 8,v v7 7,v v4 4，类类似似地地，对对v v6 6与与v v8 8取取 v v6 6,v v3 3,v v2 2,v v1 1,v v4 4,v v7 7,v v8 8。得得到到图图8-178-17，已已是是欧欧拉拉图图。对对应应这这个个可可行行方方案案 ，重复边的总长为：，重复边的总长为：2 2l l23 23+2+2l l36 36+l l69 69+l l98 98+2+2l l8787+2+2l l74 74+l l41 41+l l12 12=51=51v3v1v2v6v9v8v7v4v5图图 8-17v3v1v2v6v9v8v7v4v524344955644图图 8-163限像鞋戮砂盒严拂铰口每谅酶荫综浑拌妮摇臣叔枷瓤贝楔溉脏伤故恐黑箭+8+图与网络分析+8+图与网络分析7/15/202415例 4 求解图 8-16所示网络的中国邮路问题第一步：确第第第第二二二二步步步步：调调整整可可行行方方案案，使使重复边最多为一次。重复边最多为一次。去掉(v2,v3),(v3v6),(v4,v7),(v7,v8)各两条，得到图 8-18。重复边总长度下降为：l 12+l 14+l 69+l 98=21v3v1v2v6v9v8v7v4v52434495546图图 8-19第第三三步步：检查图中每个初等圈是否满足定理条件(2)。如不满足则进行调整，直至满足为止。检查图 8-18，发现圈v1v2v5 v4v1 总长度为24，而重复边的长为14，大于该圈总长度的一半，可以作一次调整，以(v2,v5),(v5,v4)代替(v1,v2),(v1,v4)，得到图 8-19，重复边总长度下降为：l 25+l 45+l 69+l 98=17v3v1v2v6v9v8v7v4v544335599图图 8-1846油猫仔怖酣甄傍委篙摈榴依郸廊妊宝览拳喧够绑碉腕两硕沮破牛劝征递惕+8+图与网络分析+8+图与网络分析7/15/202416第二步：调整可行方案，使重复边最多为一次。去掉(v2,v3)再检查图 8-19，圈v2v3v6v9v8v5v2总长度为24，而重复边长为13。再次调整得图 8-20，重复边总长度为15。检查图 8-20,条件(1),(2)均满足，得到最优方案。图中任一欧拉回路即为最优邮递路线。v3v1v2v6v9v8v7v4v52434495544图 8-20v3v1v2v6v9v8v7v4v544335599图图 8-1864v3v1v2v6v9v8v7v4v52434495546图图 8-194斌洁价礁黎又踏枪泉团等谩献胚敖得杜像砰拽荧缝狞贾漆迹跃熔坷渔赤宫+8+图与网络分析+8+图与网络分析7/15/202417再检查图 8-19，圈v2v3v6v9v8v5v2总长度8-2 树树一、树的概念和性质一、树的概念和性质例例5 5 乒乓球单打比赛抽签后,可用图来表示相遇情况,如图8-21所示。ECGKABD FHI JLMN运运 动动 员员图图 8-21销销 售售 科科检检 验验 科科新产品新产品 开发开发 科科技技 术术 科科生生 产产 科科设设 备备 科科供供 应应 科科动动 力力 科科人人 事事 科科总总 工工 程程 师师 财财 务务 科科生生 产产 副副 厂长厂长 经经 营营 副副 厂长厂长 图图 8-22厂长厂长定定义义1414 不含圈的无向连通图称为树树树树。树中次为1的点称为树树树树叶叶叶叶，次大于1的点称为分枝点分枝点分枝点分枝点。例例6 6 某企业的组织结构可用图8-22表示树叶分枝点树返回第八章目录纫靠规甜催盲灌念蝴淳赚埋习碌臃值舀伏啤柬咨怨兄夸靴铆气次苍浓恍拄+8+图与网络分析+8+图与网络分析7/15/2024188-2 树一、树的概念和性质ECGKABDFHIJLMN运定理定理6 6 图图T T=(=(V V,E E),|),|V V|=|=n n,|,|E E|=|=m m,则下列关于树的说法是等价则下列关于树的说法是等价的：的：（1）T 是一棵树。（2）T 无圈，且m=n-1.（3）T 连通，且m=n-1。（4）T 无圈，但每加一新边即得唯一一个圈。（5）T 连通，但每舍去一边就不连通。（6）T 中任意两点，有唯一链相连。二、图的生成树二、图的生成树二、图的生成树二、图的生成树定义定义15 若图G的生成子图是一棵树，则称该树为G的生生生生成树成树成树成树（支撑树）。或简称为图G的树。图G中属于生成树的边称为树树树树枝枝枝枝,不在生成树中的边称为弦弦弦弦。图8-23中(b)为(a)图的生成树,边e1,e2,e3,e7,e8,e9为树枝，e4,e5,e6,为弦。e3e4e1e2e6e1e2e7e8e9e5(a)e3e7e8e9(b)图 8-23树枝弦撕动靡汗苫接赋贝捂匡物束帚裕赂磐芒朴扛菇系募亲后目加船叼确逢榷吓+8+图与网络分析+8+图与网络分析7/15/202419定理6 图T=(V,E),|V|=n,|E|=m,定理定理定理定理7 7 7 7 图图G=(V,E)G=(V,E)有生成树的充分必要条件为有生成树的充分必要条件为G G是连通图是连通图。求生成树的方法：1.避圈法（加边法）在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止。（1）深探法（标号法）。步骤如下：在点集V中任取一点v,给v以标号0。若某点u已得标号i，检查一端点为u的各边，另一端点是否均已标号。若有(u,w)边之w未标号,则给以标号i+1,记下边(u,w).令w代u,重复.若这样的边的另一端点均已有标号，就退到标号为i-1的点r以r代u，重复.直到全部得到标号为止。图 8-24 的(a)为标号过程，粗线边即为生成树,图8-24(b)即是生成树，也显示了标号过程。万贝认幸抹庇矫侥粒沫政久愉园菜酥阔佩纽孩年堡池墓禹劫踢羚尼减妻娄+8+图与网络分析+8+图与网络分析7/15/202420定理7 图G=(V,E)有生成树的充分必要条件为G是连通图图图 8-24 8-24740261012813591113(b)012345698101112137(a)(2)广探法步骤如下：在点集V中任取一点v,给v以标号0。令所有标号为i的点集为Vi，检查Vi，V Vi中的边端点是否均已标号。对所有未标号之点均标以i+1，记下这些边。对标号为i+1的点重复步骤。直到全部点得到标号为止。图 8-25(a)中粗线边就是用广探法生成的树，也可表示为图8-25(b)图8-254211112222333(b)02343201122211(a)3客吹雄雅涡劝挚患皋悍穿诣赎葛吐硫见哨眉梁助汛被媳溃索糠站攘扭馈汕+8+图与网络分析+8+图与网络分析7/15/202421图 8-24740261012813591113(b)0例例例例7 7 7 7 一一个个乡乡有有9 9个个自自然然村村，其其间间道道路路如如图图 8-26(a)8-26(a)所所示示，要要以以v v0 0村村为为中中心心建建有有线线广广播播网网络络，如如要要求求沿沿道道路路架架设设广广播播线线，应应如何架设？如何架设？2.破圈法在图G中任意取一个圈,从圈上任意舍弃一条边，将这个圈破掉,重复这个步骤直到图G中没有圈为止。v6v1v2v3v4v5v7v8v0(b)(a)v6v1v2v3v4v5v7v8v0图 8-26解解：用破圈法，任取一圈(v1,v2,v2,v1)，从中去掉边(v1,v2)，再选圈(v1,v8,v0,v1)去掉边(v1,v8)，依同样方法进行，直到无圈。图8-26(b)就是一种方案。茶选诉婿浮函恨膛驻零室猫翱碍纹饮忌祷陵面搁四蛛产莎甭迄陀婚桌梳额+8+图与网络分析+8+图与网络分析7/15/202422例7 一个乡有9个自然村，其间道路如图 8-26(a)所示，321三、最小生成树问题三、最小生成树问题三、最小生成树问题三、最小生成树问题定义定义1616 连通图G=(V,E)，每条边上有非负权L(e)。一棵生成树所有树枝上权的总和，称为这个生成树的权。具有最具有最具有最具有最小权的生成树称为最小生成树小权的生成树称为最小生成树小权的生成树称为最小生成树小权的生成树称为最小生成树，简称最小树。最小树的两种算法算法1：(Kruskal算法)此法类似于求生成树的“避圈法”，步骤如下：每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够n-1条边为止。v4v5(a)v6v1v2v3v7v8v0111122334444555211v6v1v2v3v4v5v7v8v0(b)122图 8-27先将（先将（先将（先将（a a）中边按大小顺序由小）中边按大小顺序由小）中边按大小顺序由小）中边按大小顺序由小至大排列：至大排列：至大排列：至大排列：(v v0 0,v v2 2)=1)=1，(v v2 2,v v3 3)=1)=1，(v v3 3,v v4 4)=1)=1(v v1 1,v v8 8)=1)=1，(v v0 0,v v1 1)=2)=2，(v v0 0,v v6 6)=2)=2(v v5 5,v v6 6)=2)=2，(v v0 0,v v3 3)=3)=3，(v v6 6,v v7 7)=3)=3(v v0 0,v v4 4)=4)=4，(v v0 0,v v5 5)=4)=4，(v v0 0,v v8 8)=4()=4(v v1 1,v v2 2)=4)=4，(v v0 0,v v7 7)=5)=5，(v v7 7,v v8 8)=5)=5(v v4 4,v v5 5)=5)=5到翌纳执沏敏血炊亥馁窖烂粟斑协骋闰惯辗脸凤叙琉瘫淑弛分蜜游吊兰廊+8+图与网络分析+8+图与网络分析7/15/202423321三、最小生成树问题定义16 连通图G=(V,E)，每定定定定理理理理8 8 8 8 用用 KruskalKruskal 算算法法得得到到的的子子图图T*=(T*=(e e1 1,e e2 2,e en-1n-1)是是一一棵最小树。棵最小树。然后按照边的排列顺序，取定：(v0,v2)=1，(v2,v3)=1，(v3,v4)=1，(v1,v8)=1，(v0,v1)=2，(v0,v6)=2，(v5,v6)=2。由于下一个未选取边中的最小权边(v0,v3)与已选边e1,e2构成圈，所以排除。选e8=(v6,v7)。得到(b)就是图G的一棵最小树,它的权是13。定定定定理理理理9 9 9 9 图G的生成树T为最小树，当且仅当对任一弦e来说，e是T+e中与之对应的圈 me中的最大权边。定定定定义义义义17171717 若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树有向树有向树有向树。定定定定义义义义18181818 有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树（又称外向树）。根树中入次为0的点称为根根根根。根树中出次为0的点称为叶叶叶叶，其它顶点称为分分分分枝枝枝枝点点点点。由根到某一顶点vi的道路长度（设每边长度为1），称为vi点的层次层次层次层次。牲畸咽护墙垦陶震燥抓碧渐寇嗡丛霄僚竿歧降娄绑尔粤萍渍涣景榷频损榨+8+图与网络分析+8+图与网络分析7/15/202424定理8 用 Kruskal 算法得到的子图T*=(e1,e2定定定定义义义义19191919 在在根根树树中中,若若每每个个顶顶点点的的出出次次小小于于或或等等于于m m,称称这这棵棵树树为为m m叉叉树树,若若每每个个顶顶点点的的出出次次恰恰好好等等于于m m或或零零,则则称称这这棵棵树树为完全为完全m m叉树。当叉树。当m m=2=2时，称为二叉树、完全二叉树。时，称为二叉树、完全二叉树。图8-29 所示的树是根树，其中v1为根，v1,v2,v3,v4,v8为分枝点，其余各点为叶，顶点v2,v3,v4的层次为1,顶点v11的层次为3等等。图 8-29 v11v1v2v3v4v5v6v7v8v9v10(a)(b)图 8-30例如图8-30中(a)为完全三叉树、(b)为四叉树。实际问题中常讨论叶子上带权的二叉树,令有s个叶子的二叉树T各叶子的权分别为pi,根到各叶子的距离(层次)为li(i=1,s),这样二叉树的总权数：南尘剿化年叁峦尤倘禹挪醛唉依帆炮贷距淤蔼梆逞湍摊疆母脂美育缓腮制+8+图与网络分析+8+图与网络分析7/15/202425定义19 在根树中,若每个顶点的出次小于或等于m,称这棵树4 12 2 333满足总权最小的二叉树称为满足总权最小的二叉树称为最优二叉树最优二叉树最优二叉树最优二叉树(霍夫曼树）。霍夫曼树）。霍夫曼树）。霍夫曼树）。算法步骤为：将s个叶子按权由小至大排序,不失一般性，设p1p2ps。将二个具有最小权的叶子合并成一个分枝点，其权为p1+p2,将新的分枝点作为一个叶子。令ss-1，若s=1停止，否则转(1)。例 9 s=6其权分别为4,3,3,2,2,1,求最优二叉要树。解：解：该树构造过程见图8-31。总权为14+2 4+2 3+3 2+3 2+4 2=38 图 8-31 1 223334569 1 2233345 6915421 233356此算法得到的树为最优二叉树，直观意义：叶子的距离是依权的递减而增加，所以总权最小。哈椅吹奴离镶穿睫解驻燃漱拢硝兼莽俞荤枚杯扰询届闺奢挣征嚣襟皑淋嗅+8+图与网络分析+8+图与网络分析7/15/202426412 2 333满足总权最小的二叉树称为最优二例例10 10 最优检索问题最优检索问题使用计算机进行图书分类。现有五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册,E类15万册。问如何安排分检过程，可使总的运算(比较)次数最小？解解:构造一棵具有5个叶子的最优二叉树,其叶子的权分别为50,20,5,10,15,见图8-32(a)所示,按(b)进行分类.总权为：m(T)=5 4+10 4+15 3+20 2+50 1=195图 8-32105151002050501530EABCD(a)Y NE?B?A?D?ABCDE N Y Y N N Y(b)分检过程是先把A类50万册从总数中分检出来,其次将B类20万册分检出来,然后再将E类15万册分检出来,最后再将D,C分检。讳腥胸冬蜀恋滦蔬玄哼胸贷恿累跟厅钳屹阻抓渺供米蔑嘎簧慨毅丘盘兑糟+8+图与网络分析+8+图与网络分析7/15/202427例10 最优检索问题使用计算机进行图书分类。现有五类图书例例例例11111111 某某厂厂购购进进一一批批原原件件，欲欲进进行行检检验验后后按按质质量量分分为为六六等等。已已 知知 一一 等等 品品 的的 概概 率率 为为 0.450.45，二二 等等 品品 的的 概概 率率 为为 0.250.25，三三等等品品0.120.12，四四等等品品0.080.08，五五等等品品0.050.05，等等外外品品0.050.05。假假设设分分等等测测试试一一次次只只能能分分辨辨出出一一种种等等级级，而而每每次次测测试试的的时时间间皆皆为为t t。问问如何安排测试过程，使期望如何安排测试过程，使期望的时间达到最短？的时间达到最短？解解：构造 一棵具有6个叶子的最优二叉树，其叶子的权数为各等级品的概率，见图8-33所示。0.050.080.050.120.250.450.100.180.300.551.01 等品等外品 5 等品4 等品 3 等品 2 等品测试顺序图 8-33期望最短测试时间就是最优二叉树的总权，经计算得：m(T)=(5 0.05+50.05+4 0.08+3 0.12+2 0.25+10.45)t=2.13t端山骚塔俺丁兢镁邑鲤撕壬化爱灰欲佑眨詹樊嘶帘烛街敬蓉川斌掖拔灿涛+8+图与网络分析+8+图与网络分析7/15/202428例11 某厂购进一批原件，欲进行检验后按质量分为六等。已知一8-3 8-3 8-3 8-3 最短路问题最短路问题最短路问题最短路问题设G=(V,E)为连通图，图中各边(vi,vj)有权lij(lij=表示vi,vj间无边)，vs,vt为图中任意两点，求一条道路 m，使它是从vs到vt的所有路中总权最小的路。即有些最短路问题也可以是求网络中某指定点到其余所有结点的最短路，或求网络中任意两点间的最短路。一、一、Dijkstra 算法算法 基本步骤，采用标号法。可用两种标号：T标号与P标号，T标号为试探性标号，P为永久性标号，给vi点一个P标号时，表示从vs到vi点的最短路权，vi点的标号不再改变。给vi点一个T标号时，表示从vs到vi点的估计最短路权的上界，是一种临时标号，凡没有得到P标号的点都有T标号。算法每一步都把某一点的T标号改为P标号，当终点vt得到P标号时，全部计算结束。对于有n个顶点的图，最多经n-1步就可以得到从始点到终点的最短路。返回第八章目录即淀乘距亢杜焉氯惺围占鸯摩舵躲抄弃诣鸵瞒痒否暂鄙唾售屋疲究激很泥+8+图与网络分析+8+图与网络分析7/15/2024298-3 最短路问题设G=(V,E)为连通图，图中各边(vDijkstra Dijkstra 算法算法步骤：步骤：(1)给vs以P标号，P(vs)=0，其余各点均给T标号T(vi)=+。(2)若vi点为刚得到标号的点，考虑这样的点vj：(vi,vj)属于E，且vj为T标号。对vj的标号进行如下的更改：T(vj)=minT(vj),P(vi)+lij(3)比较所有具有T标号的点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则用 代vi转回（2）。vP(vi)min T(vi)罚恤柒嘶逐哈待域扮子蓖绝匡壳甘沙姥鼠旬姚云束勒阅了耙声摄鼠面己惨+8+图与网络分析+8+图与网络分析7/15/202430Dijkstra 算法步骤：(1)给vs以P标号，P(vs)例例例例12121212 用用DijkstraDijkstra算法求图算法求图8-348-34中中v v1 1点到点到v v8 8点的最短路。点的最短路。图 8-34 v1 v2 v3 v4 v5 v6 v7 v8 4 4 4 4 5 5 5 6 6 7 7 1 9 解解：(1)首先给v1以P标号，P(v1)=0，给其余所有点T标号，T(vi)=+(i=2,8)(2)由于(v1,v2),(v1,v3)边属于E,且为T标号,所以修改这两个点的标号：T(v2)=min T(v2),P(v1)+l12 =min+,0+4=4 T(v3)=min T(v3),P(v1)+l13 =min+,0+6=6 (3)比较所有T标号,T(v2)最小,所以令P(v2)=4。(4)v2为刚得到P标号的点,考察边(v2,v4),(v2,v5)的端点v4,v5。T(v4)=min T(v4),P(v2)+l24 =min+,4+5=9T(v5)=minT(v5),P(v2)+l25=min+,4+4=8 (5)比较所有T标号,T(v3)最小,所以令P(v3)=6。(6)考虑点v3，有 筏亲饥彬峪奢惺娘寓骤垃仆欲根涩无浆湍掷踩蜡射件佣巨屑患川毛塘烯歌+8+图与网络分析+8+图与网络分析7/15/202431例12 用Dijkstra算法求图8-34中v1点到v8点的T(v4)=min T(v4),P(v3)+l34 =min 9,6+4=9T(v5)=min T(v5),P(v3)+l35 =min 8,6+7=8(7)全部T标号中,T(v5)最小,令 P(v5)=8(8)考察 v5T(v6)=min T(v6),P(v5)+l56 =min+,8+5=13T(v7)=min T(v7),P(v5)+l57 =min+,8+6=14(9)全部T标号中,T(v4)最小,令P(v4)=9(10)考察v4，T(v6)=min T(v6),P(v4)+l46 =min 13,9+9=13T(v7)=min T(v7),P(v4)+l47 =min 14,9+7=14(11)全部T标号中,T(v6)最小,令P(v6)=13(12)考察v6，T(v7)=min T(v7),P(v6)+l67 =min 14,13+5=14T(v8)=min T(v8),P(v6)+l68 =min+,13+4=17(13)全部T标号中,T(v7)最小,令P(v7)=14(14)考察v7,T(v8)=min T(v8),P(v7)+l78 =min 17,14+1=15 俘尖摊抑赵胶蔑遏昌渠继兢稗玉射煽阵趴顺拇细芥诊寝猪豁亩裸群甩孩斩+8+图与网络分析+8+图与网络分析7/15/202432T(v4)=min T(v4),P(v3)+(15)(15)因只有一个因只有一个T T标号标号T(T(v v8 8),),令令P(P(v v8 8)=15)=15,计算结束。计算结束。全部计算结果见图8-35。v1到v8之最短路为v1 v2 v5 v7 v8 路长p(v8)=15，同时得到v1 点到其余各点的最短路。图 8-35(0)v1v2(4)v3(6)v4(9)v5(8)v6(13)v7(14)v8(15)4 4 4 4 5 5 5 6 6 7 7 1 9注注注注意意意意：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。这从一个简单例子就可以看到，图8-36中，我们按Dijkstra算法得P(v1)=5为从vsv1的最短路长显然是错误的,从vs v2 v1只有3。5 v2 vs v1 8-5 图 8-36裕劫伙蛤履乏帝潮卜皂另秀李糖盘贞极绪摹精惹浆逼渠废注船汐杠锻惦浸+8+图与网络分析+8+图与网络分析7/15/202433(15)因只有一个T标号T(v8),令P(v8)=15,计算二、逐次逼近算法二、逐次逼近算法二、逐次逼近算法二、逐次逼近算法本算法可用于网络中有带负权的边时，求某指定点到网络中任意点的最短路。算算法法的的基基本本思思路路：如果v1到vj的最短路总沿着该路从v1先到某一点vi，然后再沿边(vi,vj)到达vj，则v1到vi这条路必然也是v1到vi的最短路。若令P1j表示从v1到vj的最短路长，P1i为v1到vi的最短路长，则必有下列方程：即用v1到vj 的直接距离做初始解，若v1与vj 间无边，则记v1,vj间的最短路长为+。从第二步起，使用迭代公式寥廷邪甩雨福骡刷广梗瞒什笺舔阳钻擦速手发轩道蚤尚织股凭判握泰另埂+8+图与网络分析+8+图与网络分析7/15/202434二、逐次逼近算法本算法可用于网络中有带负权的边时，求某指定点例例13 13 求图求图8-378-37中中v v1 1点到各点的最短距离。点到各点的最短距离。v2v5-1-3v1v3v4v6v7v82-2-344423567图 8-37可以看出P1j(2)表示从v1点两步到vj的最短路长。全部计算过程可用表8-1表示。信脂哀具牡敢侠涸驳脏收虹胁血要脾汰庞幸聂险粤础躺化倍釉靖档柬构衅+8+图与网络分析+8+图与网络分析7/15/202435例13 求图8-37中v1点到各点的最短距离。v2v5-1表表表表 8-1 8-1（表中空格为（表中空格为（表中空格为（表中空格为+）j j i il lij ijP P1 1j j(1)(1)P P1 1j j(2)(2)P P1 1j j(3)(3)P P1 1j j(4)(4)P P1 1j j(5)(5)P P1 1j j(6)(6)v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6 v v7 7v v8 8 v v1 10 02 25 5-3-30 00 00 00 00 00 0 v v2 20 0-2-24 42 22 22 22 22 22 2 v v3 30 06 65 50 00 00 00 00 0 v v4 44 40 0-3-3-3-3-3-3-3-3-3-3-3-3 v v5 50 06 66 63 33 33 3 v v6 6-3-30 04 411116 66 66 66 6 v v7 7 7 72 20 014149 99 9 v v8 83 3-1-10 01515101010101010迭代进行到第六步时，发现P1j(6)=P1j(5)(j=1,8)则停止。表中最后一列数字分别表示v1点到各点的最短路长。如果需要知道v1点到各点的最短路径,可采取“反向追踪”的办法。沙修墟陀蹋萤肾身氯袖擦窗匣镭贯室窝索乏扔老捏使鹊俏届俩浇齿已疆迹+8+图与网络分析+8+图与网络分析7/15/202436表 8-1（表中空格为+）jlijP1j(2如需要求出如需要求出v v1 1点到点到v v8 8点的最短路径点的最短路径,已知已知P P1818=10=10而P18=minP1i+li8,在表中寻求满足等式的vi点，易知P16+l68=10,记下(v6,v8)再考查v6,由于P16=6,而6=0+6=P13+l36记下(v3,v6)考查v3,P13=0而0=2+(-2)=P12+l23，记下(v2,v3)所以由v1到v8的最短路径为 v1 v2 v3 v6 v8 由于递推公式中P1j(k)的实际意义为从v1到vj点、至多含有k-1个中间点的最短路权，所以在含有n个点的图中，如果不含有总权小于零的回路，求从v1点到任一点的最短路权，用上述算法最多经过n-1次迭代必定收敛。显然如果图中含有总权小于零的回路，最短路权没有下界。久将镐惹匣恢逊醚什版今赤放言藩富吠慕招榜银鞍翔吗堵爷粗诵晦枕缨羔+8+图与网络分析+8+图与网络分析7/15/202437如需要求出v1点到v8点的最短路径,已知P18=10而P18例例例例14141414 设备更新问题设备更新问题某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个5年的更新计划，使总支出最少。若已知设备在各年的购买费及不同机器役龄时的残值与维修费，如表8-2所示 第1年 第2年 第3年 第4年 第5年 购买费 11 12 13 14 14机器役龄 01 12 23 34 45 维修费 5 6 8 11 18 残 值 6 3 2 1 0解：解：把这个问题化为最短路问题用点vi表示第i年年初购进一台新的设备，虚设一个点v6，表示第五年年底。边(vi,vj)表示第i年初购进的设备一直使用到第j年年初(即第j-1年年底)。尝柯坛前栋仪仰尤札匡亥钝息盎浅诅炭抽楷蝶吴做袒拭涡吁伺沥诣柒都屈+8+图与网络分析+8+图与网络分析7/15/202438例14 设备更新问题某工厂使用一台设备，每年年初工厂都要作出边边(v vi i,v vj j)上上的的数数字字表表示示第第i i年年初初购购进进设设备备，一一直直使使用用到到第第j j年年初初所所需需支支付付的的购购买买、维维修修的的全全部部费费用用（可可由由表表8-28-2计计算算得得到到）。例例如如(v v1 1,v v4 4)边边上上的的2828是是第第一一年年初初购购买买费费1111加加上上三三年年的的维维修修费费5,6,8,5,6,8,减减去去3 3年年役役龄龄机机器器的的残残值值2 2；(v v2 2,v v4 4)边边上上的的2020是是第第二二年年初初购购买买费费1212减减去去机机器器残残值值3 3与与使使用用二二年年维维修修费费5,65,6之和，见图之和，见图8-388-38。图 8-38v6v1v2v3v4v521 1213141515202922411928304059 第1年 第2年 第3年 第4年 第5年 购买费 11 12 13 14 14机器役龄 01 12 23 34 45 维修费 5 6 8 11 18 残 值 6 3 2 1 0这样设备更新问题就变为：求从v1 到v6的最短路问题，计算结果表明：v1 v3 v6为最短路，路长为49。即在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。阀搜血膘沂舱渤孕巨魔花纯应咱粕贤储羡钱胚陋狈俭诌薛揭闲霜置砷啡谷+8+图与网络分析+8+图与网络分析7/15/202439边(vi,vj)上的数字表示第i年初购进设备，一直使用到第j例例例例15151515 已已知知某某地地区区的的交交通通网网络络如如图图8-398-39所所示示，其其中中点点代代表表居居民民小小区区，边边表表示示公公路路，l lij ij为为小小区区间间公公路路距距离离，问问区区中中心心医医院院应应建建在在哪哪个个小小区区，可可使使离离医医院院最最远远的的小小区区居居民民就就诊诊时时所所走走的的路路程最近？程最近？解解 ：这是个选址问题，实际要求出图的中心，可以化一系列求最短路问题。先求出v1到其它各点的最短路长dj，D(v1)=max(d1,d2,d7),表示若医院建在v1，则离医院最远的小区距离为D(v1)。v1v2v3v4v5v6v730202030151815图 8-396025再依次计算v2,v3,v7到其余各点的最短路，类似求出D(v2),D(v3),D(v7).D(vi)(i=1,7)中最小者即为所求，计算结果见表8-3。寿楼兰沾瘩瘸斌啊掣蜗彻速洁蚀拈楼亿卿流赫诞厉晕波拒所淑狡择替蠕汤+8+图与网络分析+8+图与网络分析7/15/202440例15 已知某地区的交通网络如图8-39所示，其中点代表表表表表 8-3 8-3 v1 v2 v3 v4 v5 v6 v7D(vi)v1 0 30 50 63 93 45 60 93v2 30 0 20 33 63 15 30 63v3 50 20 0 20 50 25 40 50 v4 63 33 20 0 30 18 33 63 v5 93 63 50 30 0 48 63 93 v6 45 15 25 18 48 0 15 48 v7 60 30 40 33 63 15 0 63由于 D(v6)=48最小，所以医院应建在v5，此时离医院最远的小区（v6）距离为48。绳驳得捻讥胳泻颓矽覆炊吝埠到波庭腊倡昭儡做婪烩嚎礁惠尾忧牌扼钩偷+8+图与网络分析+8+图与网络分析7/15/202441表 8-3 v1 v2 三、三、三、三、FloydFloyd 算法算法算法算法此法可直接求出网络中任意两点间的最短路。为计算方便,令网络的权矩阵为D=(dij)nn,lij为vi到vj的距离。算法基本步骤：输入权矩阵D(0)D计算D(k)(dik(k)nn(k=1,2,n)其中dij(k)mindij(k-1),dik(k-1)+dkj(k-1)D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。急拒汾梅胖矾写久绊诸熄环秽埔疽侩覆袁杰靛桅闯揍抢彪疑棍练迎拘柄尧+8+图与网络分析+8+图与网络分析7/15/202442三、Floyd 算法此法可直接求出网络中任意两点间的最短路。例例例例16161616 求图求图8-408-40所示的图中任意两点间的最短路。所示的图中任意两点间的最短路。解解解解 图8-40中有四条无向边，每条均可化为两条方向相反的有向边。则v1v2v3v4v5 由于dij(1)=mindij(0),di1(0)+d1j(0)表示从vi到vj点或直接有边或借v1点为中间点时的最短路长。圆圈中元素为更新的元。6v1v2v3v4v522221445103图 8-408镀哲环泵硕叉吱拐扯米庶沤梧共卉隧珐必销膘涡微意红与理录境臆役梆偿+8+图与网络分析+8+图与网络分析7/15/202443例16 求图8-40所示的图中任意两点间的最短路。解 Dij(2)与Dij(3)分别表示从