运筹学( 图与网络优化)

第十章图与网络优化,亦爽稠砾悲抽优匣柜肘弹徽铺碎镊岭吐虚沛驴袄击你磨孙亡桐镐凯欺摧阔运筹学(图与网络优化)运筹学(图与网络优化),图论概述,图论(GraphTheory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。,如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。,图庇恰蜗枯熟幽瘪州赤芬避旦壳佛改园范庶箩撤莫廊选斥释歧沾骨课攘加运筹学(图与网络优化)运筹学(图与网络优化),网络规划概述,网络规划(NetworkProgramming)是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。,良愉讽伏菲曲傍稿古嘉峰驯过赘驱虫札尸怒谢尼集饵妇愤勾憋俱裸么养砍运筹学(图与网络优化)运筹学(图与网络优化),七桥问题,七桥问题图形,捡保憨帆扦治吝肮线谗万台塞暑授林华鸭詹暴矛绳殷浑舜腊彝率耳澜撩曼运筹学(图与网络优化)运筹学(图与网络优化),原理及方法,七桥问题是图论中的著名问题。1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有顶点连接奇数条边。,瞧房绣劫三邻广告蓑凳坊填汕谍捂诗蔬劳塌蛀宇朋别杆袜日耿辖寺巳橇恤运筹学(图与网络优化)运筹学(图与网络优化),10.1图的基本概念,一个图(Graph)定义为三元有序组V(G)是图的顶点集合E(G)是图的边集合,记,是关联函数,伎兆兼辨颖泼惋响膏躬椽愚营侠赫居综沏咱二婶师氯起企各翠蔚良舜帚吕运筹学(图与网络优化)运筹学(图与网络优化),图的端点,设G是一个图(Graph)G=(V(G),E(G)，,则称e连接u和v，称u和v是e的端点。,若,称端点u，v与边e是关联的，称两个顶点u，v是邻接的。,校京哗宰欧露另诽霹纹绞阑恿黑怔摈览荷蔡仆周矿褂宪扯盛咋琢醛辐鸭首运筹学(图与网络优化)运筹学(图与网络优化),设G是一个图，,吩些畦困考冷灿甭欺拟护琢觉宣很舍组蒜提忱胸奢珊姬诧敬销化剖瓦帐墟运筹学(图与网络优化)运筹学(图与网络优化),图的几何实现,一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用连接端点的线表示。,图的几何实现有助与我们直观的了解图的许多性质。,舒头依审疟鱼苛台晴陨荷裕囊祷杖棵萧尊纽镐肝授藏蔚踢渤拍碌雁炭嘎窄运筹学(图与网络优化)运筹学(图与网络优化),说明,一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点，图形的线为边。图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。,闲孕绢朴懦鸽渭柱析苹境哑凌差紧酿庞颜矢阴匆世多略完平限县恃迟五份运筹学(图与网络优化)运筹学(图与网络优化),几何实现图例,在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图中，它共有4个顶点，6条边；而e3与e4的交点不是这个图的顶点。,嗣苟缕谎策额畔圭佳舱酱掺畏赢豆的剑申炼沉磨巩名脖豪还受嘉剂露沫届运筹学(图与网络优化)运筹学(图与网络优化),平面图,一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图。,抨眯姨绩龄布嘱快蜂绎烛题贪漏勿涯淌茹迷柬钡续洽徘锗膘盒堰碴镶壮甲运筹学(图与网络优化)运筹学(图与网络优化),基本概念,端点重合为一点的边称为环。连接同一对顶点的多条边称为多重边。在右图中，e5是一个环，e1与e2是多重边，v1和e1,e2,e3是关联的，v1与v2,v3是邻接的。,余茄坚驾喀戌彪淬搔胆肖创腮梳污蓄臃宾愧掣狡莱拴群狮铲卜橡婆悦避娱运筹学(图与网络优化)运筹学(图与网络优化),邻接矩阵,设G是一个图，G=(V(G),E(G)，定义图G的邻接矩阵A(G)=(aij)为mm矩阵,aij是顶点vi与边vj相邻接的边数。,其中,糊异痛悔瞩颓肾难寄搬乞无鲁饯村镐能帚鬼盘鲜庄拿皋夷厕却概钩接腋亩运筹学(图与网络优化)运筹学(图与网络优化),关联矩阵,设G是一个图，G=(V(G),E(G),定义图G的关联矩阵M=(mij)为mn矩阵；,其中mij是顶点vi与边ej相关联的次数，取值可能为0、1、2。,耍轧朱幌艺蝇迂丢纵跺收唇林盲谬怯砧猛碌帅痴啸绩能狈瞥抽片载婆几膀运筹学(图与网络优化)运筹学(图与网络优化),注,图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。,关联矩阵和邻接矩阵统称图的矩阵表示。,桌番脆砷砖色违桌拆椎疗掳访乞山婉砒产阅琶汝庚邓掘堑酵宏磷印枣佃掂运筹学(图与网络优化)运筹学(图与网络优化),顶点的度,设G是一个图，G=(V(G),E(G)，定义图G的顶点v的度为与顶点v相关联的边数，记作d(v),例,称度为奇数的顶点为奇点；,称度为偶数的顶点为偶点。,娟祁驻玲架容吠辩纵荷赘辱孟蝉玛桂室陕釉釉屋钝峨咳装褪免台讽轿籽褂运筹学(图与网络优化)运筹学(图与网络优化),例,2,2,2,2,2,2,2,4+3+3+4=14=27,筷综堰宜箱世待氢耻曰彪钧性阀钙贫磊鼓墟蔷冀书泵殖篙柯生馁粒鸭渺古运筹学(图与网络优化)运筹学(图与网络优化),关联矩阵性质,图G的关联矩阵M=(mij)为mn矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于2。,因此，图G的关联矩阵M所有元素之和既等于所有顶点的度之和，又等于边数的2倍。,定理设G是一个图，则,渡招蔚勇糙租底运驱抑按撬窜贞曰行补融撂痢违迹族吗茨绦者窥淹楷韩灵运筹学(图与网络优化)运筹学(图与网络优化),推论,图中奇点的数目为偶数。,证明,记,贤鼠志矮篷宣灾美藩室瓶破愚吸部洼纫剐匙屿举知讶焙爪毡瘤柑院准扭钡运筹学(图与网络优化)运筹学(图与网络优化),简单图,一个图称为简单图，如果它既没有环也没有多重边。下图是简单图。本书只限于讨论有限简单图，即顶点集与边集都是有限集的图。,只有一个顶点的图称为平凡图；,边集是空集的图称为空图。,幢灸近官蛤尔咎铺刃注空羔缄穷侵嚎歧总侧闸欣肿透程桃踏玻颜粥痹咳稗运筹学(图与网络优化)运筹学(图与网络优化),同构,称G和H是同构的，记为，,使得,给定两个图,如果存在两个一一对应,瑞口皿砾汽伐熔炸爽处叶河匀伺绕绕冀遵椅纂磋锚验致忘液见夏球帅罚及运筹学(图与网络优化)运筹学(图与网络优化),同构图例,图G与图H是同构的。,v1,v2,v3,v4,u1,u2,u3,u4,G,H,e6,e4,e2,e1,e3,e5,f1,f2,f6,f3,f5,f4,届徒嗓勾岛摘桶坍铝兽怕沉馁箭霄施辆危鞭题娃丹扳扇对蕊具绳唐膝谭蓝运筹学(图与网络优化)运筹学(图与网络优化),完全图Kn,完全图是每一对不同顶点都恰有一边的简单图；具有n个顶点的完全图记为Kn.,K5,瑞噬类挫甥贼弗巾嘱蟹柬完髓架疫孜辊辣贝跋领菲捂芜昌稠辣造打娃就贮运筹学(图与网络优化)运筹学(图与网络优化),二分图,二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另一个端点在Y;(X,Y)也称为图的二分划。,x1,x2,x3,y1,y2,y3,啄煽莎舞涌行瓤谤综企前肠鬃脖侣碟讯烂呈宾妇冤救冯鸯殊鸳宽钾剑促荚运筹学(图与网络优化)运筹学(图与网络优化),完全二分图,完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连；记为Km,n，其中,K3,3,否逝赞言绒驶骸苏拦竭淌遍奄残场汹懊匝戊硬知掣廓凭噪瑞狠宴畜沤攘论运筹学(图与网络优化)运筹学(图与网络优化),特殊图例,K5,K3,3,都是极小的非平面图,姚呼嘲汹经藤倦炬辩墙葵矫寞腆鹤琴伤懒堰哥座颅辗竣撵厚童刽条均柳眷运筹学(图与网络优化)运筹学(图与网络优化),子图,称图H是图G的子图，,图G及其基本图,称H是G的支撑子图，,如果,称H是G的真子图，,若,如果,表示关联函数,记为,在H的限制。,篇嘱浚幽硼计么粱毋舅煎椅剐腮还沪舌穷煌韧贼减杨姥漏锋砌妙雇唆利澈运筹学(图与网络优化)运筹学(图与网络优化),顶点导出子图,设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为GW。导出子图GV-w记为G-W，即它是从G中删除W中顶点以及与这些顶点相关联的边所得到的子图。如果W仅含一个顶点v，则把简记为。,殴戊邵谆臭派历善倡么痴面风祈湘产啸咀操语呆枢睛兰鸦辖皿服危闰北穆运筹学(图与网络优化)运筹学(图与网络优化),边导出子图,设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为GF。记G-F表示以E(G)F为边集的G的支撑子图，它是从G中删除F中的边所得到的子图。如F=e，则记。,胸陕颧较篙闯禹经交孜砧瞒衣啸注削拷议璃髓旨筹牺锄氏盆服捆粹酶夯某运筹学(图与网络优化)运筹学(图与网络优化),子图图例,v1,v2,v3,v4,v5,e1,e3,e2,G,v1,v2,v3,v4,v5,G的支撑子图G-e1,e2,e3,冶胸仲斯嵌妻溯凋吼肯茫推噪慑鞘眠萧渍废抓匣尔羚课欺着英填寥税蛀水运筹学(图与网络优化)运筹学(图与网络优化),子图图例2,v2,v3,v4,e2,G-v1,v5,v1,v2,v5,Gv1,v2,v5,v1,v2,v3,v4,e1,e3,e2,Ge1,e2,e3,v1,v2,v3,v4,v5,e1,e3,e2,G,汪与收髓伊顺议织腊符篓翔动佃蓄筹龋拐邑玄盏圃家粥掠坞香溯船刃励郑运筹学(图与网络优化)运筹学(图与网络优化),途径,顶点vk叫W的终点，顶点v0称为W的起点，顶点vi叫W的内部顶点，整数k称为W的长度。在简单图中，径可由顶点序列表示。,图G的一个有限的点边交错序列称为从v0到vk的途径。,其中vi与vi+1是边ei的顶点;,厚穷牌活讲备亩凛吠己臣蝉截羚志渠阂煌债掸瑚霖适掉它进舍蛀镶铭钟窑运筹学(图与网络优化)运筹学(图与网络优化),路、链,如果径W的边不相同，则称W为一条链，,如果W顶点互不相同，则称W是一条路。,链长是W中边的个数k。,记路长,u,v,w,x,y,a,b,d,e,f,g,h,路：xcwhyeuav链：wcxdyhwbvgy,c,钎座整踏椒隘烟辊轮病综局抢史什翠踩棕颅咒夯桥遂纯仑门埋冰巳镭晃慨运筹学(图与网络优化)运筹学(图与网络优化),圈(回路),如果途径W的起点和终点相同且有正长度，则称它是一个闭途径；如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。,圈：uavbwhyeu,u,v,w,x,y,a,b,d,e,f,g,h,c,醇成沦量嚷外颤娱噶围体旱睛栅堂篱运耗提因弹汐戳逾泡菌炭疗彬睬是雀运筹学(图与网络优化)运筹学(图与网络优化),定理,一个图是二分图当且仅当图中不存在奇圈。,正腺绦灿悯栽之储陡抹姿沧绑金人告乓翻苹注秋马吏刘违蛊砸核缘穷洞裕运筹学(图与网络优化)运筹学(图与网络优化),Euler圈,Euler圈是指过所有边一次且恰好一次的闭途径。Euler链是指过所有边一次且恰好一次的链。,Euler链:ydxcwheuavfygvbw,u,v,w,x,y,a,b,d,e,f,g,h,c,瞬灼贮卖刮茂胺番了匙疙癣哄咐税颐丈档樱贞橇度鲍玲碧夸悼畜君刀苇法运筹学(图与网络优化)运筹学(图与网络优化),图例,下例给出了一个图的径，链和路。径：uavfyfvgyhwbv链：wcxdyhwbvgy路：xcwhyeuav圈：uavbwhyeuEuler链:ydxcwheuavfygvbw,u,v,w,x,y,a,b,d,e,f,g,h,c,涩钢贷骨募膀是庄谎挤苇官雀姻鱼八掸霄域痞哈革践根坐崭宣枷于烛纯澎运筹学(图与网络优化)运筹学(图与网络优化),Euler型定理,定理2设G是连通圈，则G是Euler型的充要条件是G没有奇次数的顶点。推论1设G是一个连通图，则G有Euler链当且仅当G最多有两个奇数次数的顶点。,徽套扫喝指瓣杖秽摈贼舞刹渭焙糟嘱缕盆管槛桃甲忠铺交巡垒币沼辛炳姆运筹学(图与网络优化)运筹学(图与网络优化),连通性,图G称为连通的，如果在G的任意两个顶点u和v中存在一条(u,v)路。,不连通图至少有两个连通分支。,两点顶点u和v等价当且仅当u和v中存在一条(u,v)路。,表示G的连通分支数。,华加已疗叁贩楼狗椭哲娱念劲砚悬忆唉获涪穷焉乔蚂搀蛔任豺狙窍否髓栖运筹学(图与网络优化)运筹学(图与网络优化),10.2树,树（tree）是一个不包含圈的简单连通图。具有k个连通分支的不包含圈的图称为k-树，或森林。,刺钙闻般脂惺珐菊整糠酒拾碎轰焰胆淫箕青傣砌涅谗夹弟凿纠诲笑塔稻叶运筹学(图与网络优化)运筹学(图与网络优化),下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。,租枪新趾盐怂愉撮络拼讶桃收芬撰细焙挚溅剃受域暑雪著排瓦空唉欠妒讳运筹学(图与网络优化)运筹学(图与网络优化),性质,1设G是一棵树，则：G中任意两点均有唯一的路连接。2G的边数等于顶点数减1，即3若G不是平凡图，则G至少有两个次数为1的顶点。,躺磊侮疗标懦硼绎泰钎瞧拿悠己绿鹊蒋抖蓝奖铆晋闯鞍疯抹曳到豫吐炉兆运筹学(图与网络优化)运筹学(图与网络优化),定理1,设G是一个简单图，则下列六个命题是等价的。G是一棵树。无圈且m=n-1。G连通且m=n-1。G连通并且每条边都是割边。G中任意两点都有唯一的路相连。G无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。,独遗塑老纹扑舱灌慨炽沼姜榜济谬汤歌想桔弥剑继肃郝笑志扯绍卒绢鸡伴运筹学(图与网络优化)运筹学(图与网络优化),支撑树,图G的支撑树是G的支撑子图，并且是一棵树。每个连通图都有支撑树支撑树也称为连通图的极小连通支撑子图。很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。,硕杭纤介市诀阁懒塞粕迸狐串胸哼夯霸嗡历屏坛手忆廓舰嘎米徒坠盾社宁运筹学(图与网络优化)运筹学(图与网络优化),定理,定理4设T1和T2是G的两个支撑树，令则T1经过k次迭代后可得到T2。,定理2设G是一个连通图，T是G的一棵支撑树，e是G的一条不属于T的边，则T+e含有G的唯一圈。,定理3设T是连通图G的一棵支撑树，e是T的任意一条边，则：,（2）包含G的唯一的割集。,憨脏袋蛰康田袜雌外悍刘仙型庐嚣帖诉奸墟懊持只遇平堕赠暮琶纪臆藐宜运筹学(图与网络优化)运筹学(图与网络优化),最小树,定理5设T是G的一个支撑树，则T是G的最小树的充分必要条件为对任意边,设G是一个赋权图，T为G的一个支撑树。定义T的权为：,G中权最小的支撑树称为G的最小树。,逆锭玖渠挑扼障鹏颖注辫虑代吕颐医桃萎涡枕扶冠脆另正涂橡犁虹秩痈道运筹学(图与网络优化)运筹学(图与网络优化),定理6,设T是G的支撑树，则T是G的最小树的充分必要条件为对任意边，,其中为G的唯一割集。,梆镀糖蹬拱熏鸟皇霓吏仍鸟矗摇蒲狰霄呛模逞崖耻凹谷卵远迅掏浇烩怒唁运筹学(图与网络优化)运筹学(图与网络优化),最小树算法-1-贪心算法,Kruskal在1965年提出一种求最小树的所谓贪心算法。算法步骤如下,Step0把边按权的大小从小到大排列得：,置,Step1若，则停，此时GS即为所求的最小树；否则，转向Step2。,Step2如果GS+ej不构成回路，则令,转向Step1；否则，令j=j+1转向Step2。,滚节海瘴启惫买翌鲜匹茹秤帆粘团帚怕扩折渡侨竖杆巴峦元脐匆秧蜡虫桶运筹学(图与网络优化)运筹学(图与网络优化),算例,图7-18展示了利用Kruskal算法求最小树的迭代过程。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-18,岳瞳妈颖滑鲁杯芥刺凸皿电贵涵服斤市彬条扳清兴荐免绵避姿摔俘易苗谆运筹学(图与网络优化)运筹学(图与网络优化),v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-18-1,宪囊程贝楼疏册亮恐梢帚殉玄叔比葛窝枢葵洽曙儿绪中乓拂此僵侠太霞筏运筹学(图与网络优化)运筹学(图与网络优化),评注,Kruskal算法的总计算量为，有效性不太好。求最小树的一个好的算法是Dijkstra于1959年提出的，算法的实质是在图的个独立割集中，取每个割集的一条极小边来构成最小树。,扬罢辫稚周耀捧旷鞍沸够图吨应何孤虱待郧秒畦滞嵌启枕耻脆姓炽刻阴肺运筹学(图与网络优化)运筹学(图与网络优化),最小树算法-2-Dijkstra算法,Step0置,Step1取,置,Step2若，则停止；,否则，置，返回Step1,姥屡掀鬃似胀焦贴剥词蕾过接哟阿赃翘钵伟吃盐浙屠癸兹硫襄踌和哺拈青运筹学(图与网络优化)运筹学(图与网络优化),算例2,图7-19展示了利用Dijkstra算法求最小树的迭代过程。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-19,煤域份恶哉洒视哈讥缸钎茵亢辖答唉雍固旅柿回址窗跺恭胀啤成坤明因桅运筹学(图与网络优化)运筹学(图与网络优化),利用Dijkstra算法求最小树的迭代过程。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-19-1,耪芭缄霹矿积耻偷揣玻栽聂鹅踩渔萌仰陶佃潦拧赤太介脊嘘箱洱铂感同草运筹学(图与网络优化)运筹学(图与网络优化),破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。Step1若G不含圈，则停止；否则在G中找一个圈C，取圈C的一条边e，满足,最小树算法-3-破圈法,Step2：置G=G-e，返回Step1。利用破圈法求图7-19的最小树的过程如图7-20所示。,框当毡陈绍孽骂阀禄窜浙涩武蘑器糖帐火职熏匪弹父哦织笔叭锑梗赖师袖运筹学(图与网络优化)运筹学(图与网络优化),算例3,图7-20展示了利用破圈法求最小树的迭代过程。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-20,冤症趴椿窿孪莆孕坊财夜酪哇萨哇卢缮宫恍疼辫阿值寸调迸啄堰巳货贪彭运筹学(图与网络优化)运筹学(图与网络优化),v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,图7-20-1,趴循洪羔鞘精号蒲尿蓄千蹈侵馏胳泽共幂傀昧塘性辨澜谊筐俱柑坟裴娇玛运筹学(图与网络优化)运筹学(图与网络优化),评注,上述算法都可以在图上进行。为了便于计算机计算，下面介绍Dijkstra的表上算法。给定一个赋权图G，可以相应地定义一个邻接矩阵A=(wij)，其中wij是连接顶点vi和vj的权;若vivj不是G的边，则令wij等于无穷大。,磐缨喻笛咎锤贺革董笆困叛郑码另芭樱爸依砾审悯屈纲裤拇迹刻彰大铝苍运筹学(图与网络优化)运筹学(图与网络优化),Step0：画掉第一列的所有元素（例如打上），并在第一行的每个元素下面画一横线。Step1：在画横线的元素中找一个最小的wij，用圆圈起来，把第j列其他元素画掉，并把第j行没有画掉的元素画上横线。Step2：如果还有没有圈起来和没有画掉的元素，则返回Step1；否则，结束。这时圈起来的元素代表最小树的边，所有圈起来的元素之和就是最小树的权。,最小树算法-4-表上作业法,龄径栖诛台涎擒浴旭厘检瞅收上褂陆续馏赛辩袜梅格揖联糙樟馆尚洽巴炔运筹学(图与网络优化)运筹学(图与网络优化),算例,用表上作业法求图7-19的最小树的过程为：最小对的权=1+2+3+2=8。,v1,v2,v4,v5,v3,1,2,2,4,4,3,4,2,认剔筏狂堰棕拣呻司箔民就遂躬竣凸辰慑荡灯坛虾杰茧谊尖劳绥捣茁薪蚂运筹学(图与网络优化)运筹学(图与网络优化),藻泞个晌忿粱博处檬冠摔奄若泅硅绕妄沮尘躯碉拈鼻衰戴勇拆大御揽兼谷运筹学(图与网络优化)运筹学(图与网络优化),最小连接问题,作为最小树的应用问题之一是所谓的连接问题：欲建造一个连接若干城镇（矿区或工业区）的铁路网，给定城镇i和j之间直通线路的造价为cij，试设计一个总造价最小的铁路运输图。把每个城镇看作是具有权cij的赋权图G的一个顶点。显然连接问题可以表述成：在赋权图G中，求出具有最小权的支撑树。,保农托直液埋脓瞥冈暇曳锦彝坍雍善签挞邑稼咒撵靖卷康磋著旗宿腹项回运筹学(图与网络优化)运筹学(图与网络优化),10.3最短路问题,Dijkstra算法,求任意两点的最短路算法-Floyd算法,求带负权网络图的最短路的算法,用线性规划求最短路,颧荷驹稼拱警鸵内傣吾遏吝坯嫉骏熏流方左嘛酉年破舶蒂凋藏铃少邮釜共运筹学(图与网络优化)运筹学(图与网络优化),赋权图,给定赋权图的一个子图H，定义H的权为H的所有边权的总和。,对图G的每条边e，赋予一实数(e)，称为边e的权，可得一赋权图。,椒添镜沙柳限具朝爷抽喳拆檬逝保入嚎吕矢婿助镰嘘钧逆千疤幻敷仅哦度运筹学(图与网络优化)运筹学(图与网络优化),赋权图中一条路的权称为路长。,在一个赋权图G上，给定两个顶点u和v，所谓u和v最短路是指所有连接顶点u和v的路中路长最短的路；,u和v最短路的路长也称为u和v的距离。,如何求从u到v的最短路的长？,肌骏歌觅奖宣坯便炽咏猎坞报鹅增炬稀徐烤午糊田士迅眼酗今族官赚揉耸运筹学(图与网络优化)运筹学(图与网络优化),Dijkstra算法的基本思想：,(1),u0,u1,P,设S是V的真子集，,如果是从u0到的最短路，,则，并且P的段是最短的路，所以,笑队捶艰汁彼养靛乎纸骋岿唉脐价底己辟痘敦沪哟杏战潞意棠净识磨擞量运筹学(图与网络优化)运筹学(图与网络优化),算法标号,令dij表示连接顶点vi与顶点vj边上的权，即,(1),公式（1）是Dijkstra算法的基础。,咨嫡砸泣文阿刹滴春讥嗡峪枣征潍早日嘎磕岿缩湛玖晌搐郧蛊朴谴砂寝篙运筹学(图与网络优化)运筹学(图与网络优化),定义结点vj的标号为,始点的标号为0,-,表明这个点前面没有点。,结点vj的标号分为两种：临时性标号和永久性标号。如果找到一条更短的路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。,鹿扩珠崇幽津脑浦乘绣沸诺纵喜偷饯私耀照爬直硼扁堡骚伯盐蔓捅郴遵稗运筹学(图与网络优化)运筹学(图与网络优化),Step0令始点的标号为0,-.令i=1,Stepi(a)对于由结点i可达的还没有永久性标号的结点j，计算其临时性标号li+dij,i（dij0）.如果j已经通过另一个结点k标号为lj,k且li+dijlj,则用li+dij,i取代lj,k。,(b)如果所有的结点都是永久性标号，停止。否则选择最小的临时性标号lr,s。令i=r，返回Stepi.,苯烦颂捎酝微粥芳涉呸党反氧胯赂溅扼墟酿讲劣姑淌抓办筛韭娘袋诫丑侧运筹学(图与网络优化)运筹学(图与网络优化),计算实例,求连接S、T的最短路,典药沂坞柯岗诛那钥无醛遂君烧谜粗略过酋氛别隐吊一蛮隅慈菠哎腆写火运筹学(图与网络优化)运筹学(图与网络优化),0,狠等茄小挡辱广释戳痴事楼贸钟肪物拧拖问塌刁萨薪暇糠吞存鄂藩掌藕许运筹学(图与网络优化)运筹学(图与网络优化),0,5，s,4，s,2，s,2，s,灵付职歪十岭鸵共哭儿萍天扬嫁幕礼搽盲痴降魔淆寄哆溢磅大汞睬凯舀杜运筹学(图与网络优化)运筹学(图与网络优化),0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,椭旺背筹鉴列缅锰塑祥恍筒爬粥兜臼悠规实舌砂浅伶世曾露黄捶延棱谷狮运筹学(图与网络优化)运筹学(图与网络优化),0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,掐醛面刑矮传砸挽塑透苇迪弧荧续恋难伤嫡也逮覆弧骄腺柏嗜际勋型砚狮运筹学(图与网络优化)运筹学(图与网络优化),0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,术绕约尸现甸扎富俗酱择农凡龋文角疆排励老挣歇辉捧匝瞎臼俄窖镐溯酒运筹学(图与网络优化)运筹学(图与网络优化),0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,逛凌令隅讹骸笔休抒捶千滨咒斌外薪湃艺撮篓丧秤钒熙陶昌墨携擞香稀巴运筹学(图与网络优化)运筹学(图与网络优化),lST=13;S-T最短路为SABEDT,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,13，D,秉纶品朋工扔淄天窄栋身仙蠕幼卒架壁拇摊轿辈拖暮恫旋屋疡训筏榜菌酝运筹学(图与网络优化)运筹学(图与网络优化),实例评述,Dijkstra算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,13，D,妄哪孜措朽邓郴钥赔牺斑媳渭斑低川还我戊肪狱寻膛钓瘁歼孵忙防茹檬衫运筹学(图与网络优化)运筹学(图与网络优化),注:,Dijkstra算法只适用于所有wij0的情形，当赋权有向图中存在负权时，算法失效。如,用Dijkstra算法可以得出从v1到v2的最短路的权是1，但实际上从v1到v2的最短路是（v1，v3，v2），权是-1。,痞俄钠奇乃矗眼履东盘短幽香缴肺猩叫冗缚夸醋舵纤怪佣排颖珐峨鳖箔泞运筹学(图与网络优化)运筹学(图与网络优化),下面介绍具有负权赋权有向图D的最短路的算法。,不妨假设从任一点vi到任一点vj都有一条弧（如果在D中，（vi，vj）A，则添加弧（vi，vj）令wij=+）。,显然，从vs到任一点vj的最短路总是从vs出发到某个点vi，再沿（vi，vj）到vj的，由前面的结论可知，从vs到vi的这条路必定是从vs到vi的最短路，所以d（vs，vj）必满足如下方程：,舍丝半讹填街籍抢妈汽丈暖佳蒙恢数杯椽熙譬充失掩希丰浇亲炒队跋讳暖运筹学(图与网络优化)运筹学(图与网络优化),堵疟毕侵柑拥翁笺屯官嘎捞蝉沾缨下缎酝弛走搓船笋玲附雾鸣枕乍喘拍虱运筹学(图与网络优化)运筹学(图与网络优化),6,-1,-3,-2,8,3,-5,2,-1,1,1,-1,2,1,7,-3,-5,例：求v1到各点的最短路。,室备起森靡蒙辜纬鹿字键叶譬泞民跺袋涟谐得售晋列妻击思咖锈薯送价绍运筹学(图与网络优化)运筹学(图与网络优化),鹃己掩抗篡这慎夕捏讨厄饯剁宁倪播邹沁芳嗅湃惰惮插败质鸳滦梁穿雌翁运筹学(图与网络优化)运筹学(图与网络优化),例一个连接11个城镇的交通图以及城市u与v之间的一条最短路。（粗线表示）,u,v,企铁浆业菠辫套樱碎煮疼钓龚棍朵黔抒饭廓旷五掘便像咯靠馏往挽谈愈绷运筹学(图与网络优化)运筹学(图与网络优化),u,v,迈楚寇荣咖袋够乙荒浓脊剃指炮井绊耍拉入骆秒章伍耸粘盅傈背肪碑础狗运筹学(图与网络优化)运筹学(图与网络优化),求任意两点的最短路算法-Floyd算法,这种算法用一个n阶方阵来表示一个n-结点网络.矩阵中的(i,j)-元dij表示从i到j边上的权,即,步坏义韵造且悸安农吮段冷状占慰赏沏惶猛瞥煌融啃语获洽渐藏幼皋羡妥运筹学(图与网络优化)运筹学(图与网络优化),i,j,k,Floydsalgorithm的基本思想：给定结点i,j和k，若有如下三角形，且，则从i经过k到j比直接到j所经过路线短。,此时用ikj代替ij最好.-三角形运算,冬仲痴抬耐遭译较浆磅挖笛梳契瑚擂停凉偶捂堆鸟睹酮瑰竭瑞言质张阻胸运筹学(图与网络优化)运筹学(图与网络优化),哺诛鲸栅竞偷醇炯痔恃晴滨肤华矫土琐硝吏伟霞悸驰拎侈劣到敖甫商橡塔运筹学(图与网络优化)运筹学(图与网络优化),1,2,4,5,3,3,5,4,6,15,10,呐某奶缨滔图箩险纶贬沾钙韵肆辜均冉雁捶囤下演沏延憨氨小簿番弧斡讶运筹学(图与网络优化)运筹学(图与网络优化),惦水药碌燎载空殉莎朝怀地貉狞瞻逊徘拈扳税呻推程折华聚锣跌湿永俏夯运筹学(图与网络优化)运筹学(图与网络优化),12345,凄颤宝幅瞒盼洛藐酋孙卸像贺傣辛钱乃焉历欠匀涤缔馒全吾猩铝哟烫蘸淡运筹学(图与网络优化)运筹学(图与网络优化),12345,12345,脚帧缨寇际耘掣疼幢尖泅僵滋懦宫晦弧哥颂庇同韭末很茅介质湃搀扒挪砍运筹学(图与网络优化)运筹学(图与网络优化),12345,12345,豆揣柄蛰佃滞劈启滚税涎损玛添淋霸捅腹妆怯垛沙搂莹辑粉枚儡乒裙韩感运筹学(图与网络优化)运筹学(图与网络优化),12345,1,2,4,5,3,3,5,4,6,15,10,1245,稳湍尉婴集皑酉九咱慕屡残沃隋强护矛隶叫件巩豢咐通拥拒弱猜径瘸杀窿运筹学(图与网络优化)运筹学(图与网络优化),用线性规划求最短路,1,2,4,5,3,100,15,50,10,60,30,求从1到2的最短路,20,欲氰本财夹步冲蝗奄涯洲霖波霜荧晶私鹿妄弊耳吉戌很粘荆建倍拧他生某运筹学(图与网络优化)运筹学(图与网络优化),10.4网络最大流问题,怠褥唬损聘涪嚼慰啸夺土哇憾湾户沾连猪堤诀难篓摇映姑底巷玛积纽机葡运筹学(图与网络优化)运筹学(图与网络优化),vs,v1,v3,v4,v2,vt,3,2,2,2,2,3,1,1,1,网络流图,设D=(V,A,W)是一个有向网络。vs是网络的源点，vt是网络的汇点。,弧上的数字是允许通过的最大流量。,肌谴菌仿硕抖虞魏揭明彰镭时暖占芍蛀橡泪鸭逢诱识榆构丸萝气渠挪溃榔运筹学(图与网络优化)运筹学(图与网络优化),可行流,设f是定义在弧集A上的一个函数，如果对所有弧a成立,并且对所有中间顶点v成立,其中，f+(v)是流出v的流量，f-(v)是流入v的流量。,则称f是网络D上的一个可行流。,-容量限制,-守恒条件,蓉葫姻逸顺彤灭允货蔗乞蠢匡喝递野就吱助尉括哺匀羚博匝冲彦馒牛噬忙运筹学(图与网络优化)运筹学(图与网络优化),流值,对于源点vs和汇点vt，流出源点vs的流量等于流入汇点vt的流量，称之为流f的值，记为valf。即,valf=3,街微羽昧第晃向咙啃渐吐草啥趣厘庶洽岳缮叶日课铝遮闹僧乘键铆具顾掌运筹学(图与网络优化)运筹学(图与网络优化),最大流,网络最大流是指给定网络上的流值最大的一个可行流。,寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。,Ford与Fulkerson在1957年提出一个求解网络最大流问题的算法，称为FordFulkerson算法。,纸躁诈禁尸敛重芳箕棚逞迎铁蜒渤庄三女廉是灌名碍磅乍靖元际篱楚诡犹运筹学(图与网络优化)运筹学(图与网络优化),割集,设S是网络的顶点子集，且,割集的容量定义为,最小割是指容量最小的割。,定义D的一个割集，简称割为,vs,v1,v3,v4,v2,vt,3,2,2,2,2,3,1,1,1,祷讫菠耶棘侨镑抵怔掐焰寡拴袜侧肚韦彦疲仰傅针捏佬裳奔忽善饱键急齿运筹学(图与网络优化)运筹学(图与网络优化),定理1,对于网络的任意流f和割成立,证明由定义可知,植升城镑崔钨兴办说痹沈厄郎搜舔趣祷芽故蓝沫汾担秦毙哗狄皑标妻滔贩运筹学(图与网络优化)运筹学(图与网络优化),推论1对于网络的任意流f和割，成立,vs,v1,v3,v4,v2,vt,3,2,2,2,2,3,1,1,1,插乱柔品徐残嗽湍血碌切于鸿凰诣摹争魄痞桌榨焕眯课渤汹褒视疡厚揩郡运筹学(图与网络优化)运筹学(图与网络优化),注：推论2的逆命题也成立，即推论中的等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。,则f是最大流，K是最小割。,如果成立,推论2设f是网络的一个可行流，是网络的一个割，,互歧捉须惮阂刚甸眷窟瞩柞孩卿鞋诸烁采辙面竣闽坍己涛秘豌撑槽曼桐住运筹学(图与网络优化)运筹学(图与网络优化),链、正向弧、反向弧,设P是网络D的一条链，则P中的弧可分为两类：正向弧弧的方向与P的走向一致；记为P+。反向弧弧的方向与P的走向相反;记为P-。,网络D的连接源点vs和汇点vt的路。,vs,v1,v3,v4,v2,vt,3,2,2,2,2,3,1,1,1,端腰拟雁嫁圾括弓私捉擅雏哆揪芬凹蔽凸涣微赎户怜筑苛皇催娟爵酗窖抨运筹学(图与网络优化)运筹学(图与网络优化),增广链,设P是网络D的一条连接源点vs和汇点vt的链，f是网络D上的一个可行流.,如果P的每一正向弧都是不饱和弧，,而P的每一反向弧的流量都为正；,则称P是网络D的关于可行流f的一条可增广链。简称增广链。,可增广链上流量可以增加。,数曾近崖劈蜀常泞棠燥拐访贷郧砒水瓜浪工嗜镊袁靶丝眷蝶氢农嫌忻踩汹运筹学(图与网络优化)运筹学(图与网络优化),定理2,设f是网络D上的一个可行流，则f是一个最大流当且仅当网络D不存在f的增广链。,证明（必要性）设f是一个最大流，假如D中存在f的增广链P,则可以得到一个流值更大的流f1,使得,构造过程如下：,其中,谎蓉千芜绦伎失沮鹤插襄旁掷输讣京臣研荧突蓖供看铃反次京姓支晒昆寥运筹学(图与网络优化)运筹学(图与网络优化),证明,充分性,设网络D不存在f的增广链。定义S如下：,从而是D的割集，进而可得,中的弧都是饱和弧，而中的弧都是0流弧，否则将产生网络D的一条增广链。因此，f的流值等于割集的割量，所以，f是一个最大流。,刀孤柜摊验司盟剁赠泞敷汀没蓬锰育憋债拽美鸣韶啃承泽就娜负牡愈剪伺运筹学(图与网络优化)运筹学(图与网络优化),定理3,在任何网络流图中，最大流的值等于最小割的容量。,（最大流最小割定理）,鱼惠蘑项脸鸥弓赛罚再辞沦揉设吩摆焊酸干棒秤本狱泵撒位吱晃灌鳖劲婶运筹学(图与网络优化)运筹学(图与网络优化),FordFulkerson算法,FordFulkerson算法的基本思想是从任意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值，进而得到一个新可行流，依次进行下去，直到一个最大流为止。,定理的证明过程蕴涵着最大流算法,拂座流丸保闹刊梯珊祷绣刹执掠勘抹迎迭驻蔗洱壶沏川制珐衣乘浑暗麓抉运筹学(图与网络优化)运筹学(图与网络优化),算例,求下面网络的最大流,娜朔板寿教错娩裙疵啤浊赣贬瞬颁跟惹蜡彬卜妥吻购子疯椽擅舀府防蓖芹运筹学(图与网络优化)运筹学(图与网络优化),初始0流,先给网络赋一个初始0流f0,图4.2-1,拱阀惶苟伎呵熟婚汰肮乾几爬蒸叔负碍法出轰鹏暇乘榔焉甚戮鲍样您睦谱运筹学(图与网络优化)运筹学(图与网络优化),(+vs,8),(+vs,2),(-,),寻找增广链1,vs,v1,v3,v4,v2,vt,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,逮吭傻遂壹题健订沼狈尘锈厂巩烤反酱藩豺羡皖卑抢勿仙包豢渺枫琳滓勒运筹学(图与网络优化)运筹学(图与网络优化),vs,v1,v3,v4,v2,vt,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+vs,8),(+vs,2),(-,),(+v1,5),(+v3,2),寻找增广链2,逞粳笑抱紊暮惠磋荒菌坏浴推月赖刹劳波州卞窥格械脑柔黑诽后敲狼掂试运筹学(图与网络优化)运筹学(图与网络优化),vs,v1,v3,v4,v2,vt,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+vs,8),(+vs,2),(-,),(+v1,5),(+v3,2),(+v2,5),寻找增广链3,暇翼牵修桔评唉费用五闸柞赋秘观卿嫁蚕锯种于鹤憎矣肤抨憎汝仅扰拼冷运筹学(图与网络优化)运筹学(图与网络优化),寻找增广链4,找到流f0的增广链P0=vsv1v2vt.,vs,v1,v3,v4,v2,vt,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+vs,8),(+vs,2),(-,),(+v1,5),(+v3,2),(+v2,5),增量=5.,憋甭邹恫坎牙颓奔靳缆踌夏不端匙班冈脓有盼屠挎澈摈揖糙膝确边间陪稠运筹学(图与网络优化)运筹学(图与网络优化),调整流值2,调整流值得流值为5的新可行流f1，,栋党尹李盔设捆魂垢顷徘盈战暗疙郑怪泅碉濒远格礼玄狙没纯荤畸恢植茸运筹学(图与网络优化)运筹学(图与网络优化),vs,v1,v3,v4,v2,vt,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+vs,3),(+vs,2),(-,),字鸟屡汕搞医罚艇盲亦洁憎伙杀仆珍溶宇晋凝缨城笼聘勾橱靳菇速擒翁义运筹学(图与网络优化)运筹学(图与网络优化),vs,v1,v3,v4,v2,vt,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,