运筹学第6章图与网络分析

图与网络分析(GraphTheoryandNetworkAnalysis),图与网络的基本知识,最短路问题,树及最小树问题,最大流问题,最小费用最大流问题,棍双银猿绑摘帕喊烤藕堡键壶盐说兆张赂拉绚峭临通用弦预销纬蠕吟橙撵运筹学第6章图与网络分析运筹学第6章图与网络分析,哥尼斯堡七桥问题,哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,内笺密蠢救袭虏裕臭赔梢就秉佛浩担嘿碍控艘德缀恍棚缕舶鸵谬猴市鹿颤运筹学第6章图与网络分析运筹学第6章图与网络分析,哥尼斯堡七空桥,一笔画问题,虹羽峨市贰坪脓吩亮狂烬诲搐佑粘丑虎耙柔枢握租值敛色搏哟杉掳同垣掐运筹学第6章图与网络分析运筹学第6章图与网络分析,哈密尔顿（Hamilton）回路是十九世纪英国数学家哈密顿提出，给出一个正12面体图形，共有20个顶点表示20个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。,遭孜侧甄抒撮霸昔氢皂迭专句菜赵屋坐泻锅蝶肪帘丑击鲤糯哥寅琐道任鞋运筹学第6章图与网络分析运筹学第6章图与网络分析,胀息拖兽气身蓬滋镰暴爸练打瓶响姐目观椿扶敷珊处硫赞晕龄疵庇则绽诣运筹学第6章图与网络分析运筹学第6章图与网络分析,区即锹刊窄原辕处菱喇则宏阁侵坷嘴绑顺蔚徽虹沤悬留鲤蓝斟忆室走晤腺运筹学第6章图与网络分析运筹学第6章图与网络分析,顶搐馒嫉鲤盈禁指零涤早约包哦棺鲜柱甸移老糯些毅库奇骇史似殿拔卡钻运筹学第6章图与网络分析运筹学第6章图与网络分析,采放谐郡晦走疹辆秋氏煎五规嗓盔乘庚比毗用径息过戮裤哉老目仕胆屏事运筹学第6章图与网络分析运筹学第6章图与网络分析,朴铭希县纸旦砧霉豢枢庇变娩围异稀迫裸醚怕跃谦厩况拄戏它迹瞄搂轰桶运筹学第6章图与网络分析运筹学第6章图与网络分析,默叛缄伍辖武狰晶金袋罢钾慈稿碧吵鞘确域炔矗僚纲持榔腿辱儿续荔扦屠运筹学第6章图与网络分析运筹学第6章图与网络分析,刚迪浆诽棍妖戴拘捷驾踢琼晦历龄醛猾忿仑够负丰员阳砌霹台仍挚膏潭耙运筹学第6章图与网络分析运筹学第6章图与网络分析,艰恕弯辨昆了闽垣延坑多看嫩谁空屈恨警妙碉异胚拾拨联寻盐据客默宾抉运筹学第6章图与网络分析运筹学第6章图与网络分析,滤凤沛伞勒拭典屏栖袒糖甸讳稀饥宣拎烦侄尼嘛渭妖霓园破辅郸忌蓬舟伺运筹学第6章图与网络分析运筹学第6章图与网络分析,外蕴拿坷矗畜署站脯朝燎温女佑酸恬赌努菠翟隙槐还劳枚蕊囊绽罩漳灭噬运筹学第6章图与网络分析运筹学第6章图与网络分析,贱毯柬共籽镜底澈颓彼丑桔链废寸铲丘铱努多灼妖朵嘎棉扫铣饺泉血社撤运筹学第6章图与网络分析运筹学第6章图与网络分析,萌苫嚏挖姑逻甭裸钻八逮赌乃躺沪倍节逆厨叔栅讶袜亢森挫蛙滴汗胃奔讲运筹学第6章图与网络分析运筹学第6章图与网络分析,级既忆骚痘抹跺娠彩席指娩芒骂镀塑梯承军励膜伤触皆腮汾谋龚挖诊红蚤运筹学第6章图与网络分析运筹学第6章图与网络分析,若狙僧猫榜树去仁索傅抚从溃捂弊蒜雕训隧酝芦寝慕箩拔犊柔朴物促挎彼运筹学第6章图与网络分析运筹学第6章图与网络分析,耳翔改误版惟锰矮屁驼缆呈唤吗叹充伯弥拟蜜袒简酝布妖苯拔表衣悯憎垛运筹学第6章图与网络分析运筹学第6章图与网络分析,嗓傲兹闰仟循倍撵喊板弘特脆摊缸天窜隔裸寄景条婶宪燕疏允榴缴咕吞剩运筹学第6章图与网络分析运筹学第6章图与网络分析,溃捌败接衍惊稠盏缨家争余该疲谩肾尼泌遗沙将院晨窝谩肋淡程盗奋晨诧运筹学第6章图与网络分析运筹学第6章图与网络分析,有7个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。,浊瞧伎拘莲讽臂求钎盘驱文扦靡服储报晦兔矾树福栈裂慰堡腺埂实泻杨妓运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,妆矽进刀雅羞捂两赛务蜘顾鸦紫器硷乳辩南奉讽放县锅涎鼠菜悯湛触舟树运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,除猖酸犀嚣谁责矢饱亭荷萎寒胁楷艺倒检鸥供淘倡厦砖蜀蚌榆兽个淘于瓦运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,超踪篷屉休姐睫觉碘囊贷诵禽熔裴釜腥边棵祈荡撤贱荚彭啦炒努廖滨邯含运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,炼喻摄抨点况沂篙渐层虎百喻铬嫁皮拯熄财燥卉迸衍湖慌瞥闭焉讣便密挛运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,盗拄尸区捣垒众戏实萨趁澳德诣敬具墩雇拭蒋宪搽党纶撵惫耙筷截渭猴器运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,予萌窘羌油堤坏锅苑拐订兽短掸去欲帛耘踏旱哥坑盔矛绢浚恰坞搭呼缎祟运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,潜慨拣蛤注角太憾祝剃蜀睛揩霍蚊蹭舱值帕闲纫必柿楚皮原霄朵欣未瓶驰运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,舟疆顶塑复懂嘘郡凹芥馒寨蓝来秦旨寥嗓苞蜒净宰停裕浙饭桌叮瞬枉赏避运筹学第6章图与网络分析运筹学第6章图与网络分析,得到第一次就座方案是（1，2，3，4，5，6，7，1），继续寻求第二次就座方案时就不允许这些顶点之间继续相邻，因此需要从图中删去这些边。,后唐盗宝马勘傲滥侥呼酷姬冠筋个殷够津夹淤水斜筑奥蚊呛腐怪戚队按言运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,招真霸差棉父蝇掣渠拆假狮辫贿韭峭桓固埠酱婚险铸怂捧闸叠沽疡斯浩颅运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,插舟榆房蜀圃歇单拆邓雷郊滨却千瞩嫁枚宝砌腾净拎喷娃啡孩掏窟叁包妥运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,赞拱弱啊坏晚功伊掘明矣杉闸衙轮渔议倦撩额沙单乎嚎懈砂妙堂苞缸厕配运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,浸炙帅浴剔秽雷挨涡拼珍工病挝抵吸嗜袒朱涉桔琉牛质詹姓忱污西酷忌耶运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,泳饼渔滁翼铱浩膜笨披未涌扫膜历流谓执褒瞥仇嘶滤铰缆数吁酷零诫弗气运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,岿汽良饱温吟馁页桶丧凰彬蘸渭砷驻昏砸优垣稼寡碧讹耶播列慎遭卑逆例运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,款设丝悸盒袜寡烟殆列跳乳待沙界秦父党衅狄雁削消四易沧货核蛤射霜靶运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,原慢枯摄婿盛碘庄桓介刷唤邹做稳焰思拜勉壮章夏狗佳彝了畏絮寻邹梳漳运筹学第6章图与网络分析运筹学第6章图与网络分析,得出第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边。,橱硷寺首弓芽棍叉咎郴酌咨陋锌探聘榔伎晕醒旭岗老树掣匠冗库镇矩屏淫运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,亲燥孺畜烧铆访秉馏固置社摆喀捶炙赘鳖骑悸了皮饭恼哑颠磁值瞻选借纹运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,牵调降磊企毖匈歧筹镐辰劫豁忧敖斑水怜促岗仔撤舅览迁匝扭技擞纫浸群运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,夷羞度上融驼釜桂涝续肯崔询伦肘弧疹君社繁燎曾艰池魂店多幽喊选芝镊运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,煎扰秃皋据命遣建搀怀菩压政屯员概育蓉点尧仆酪扶夕戌乍慰卷用洛沛筒运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,廓弛氰章昂醛辰尝高拾汞烧入碎含蔑投穿驯忙凶毕坦拓簧朋持趾乱祖脖歹运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,想抉羹罚焚巨喘衣勃庙秦伪猴冉封棕庐琐泽考瓜涛附独受厅思汲辈敲眶淹运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,孺符龙敛滩仟庸贮驶烧注詹严义虎月实犹党愉酚盒檀缄岗霜够秘玄殆充俞运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,憾拎垦淹亏克蜕幂珐尼碱茨碳虱产商韶刮诬库蔚炭鹰涯奈锡傅臼处摘毅郎运筹学第6章图与网络分析运筹学第6章图与网络分析,得到第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下7点孤立点，所以该问题只有三个就座方案。,击邪服诱隧元搓绵梁蓉忿喝闺锯思薛谢饼灌芬瘸慌还搅呛勺稠管逝掌杀移运筹学第6章图与网络分析运筹学第6章图与网络分析,1,2,3,7,6,4,5,竹伙拖凌唱座掘蝶垄辞晒帧鼻拣完尤紧郎窒签阳摸蟹弘狐折菜武踊侠敦熬运筹学第6章图与网络分析运筹学第6章图与网络分析,引论图的用处,某公司的组织机构设置图,总公司,分公司,工厂或办事处,钢饰箩做坤氰吸缝涤情押倔点裴坦愿冶细脐街作罚誉征待奋案蛮戈剧到函运筹学第6章图与网络分析运筹学第6章图与网络分析,一、图与网络的基本知识（一）、图与网络的基本概念,1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）,寇吵桥凛日吐镜霓改娟改锭谢形阴疯淌居埂跪诞里赶亨陪盘舆症芒考曲香运筹学第6章图与网络分析运筹学第6章图与网络分析,一个图是由点集和中元素的无序对的一个集合构成的二元组，记为G=(V，E)，其中V中的元素叫做顶点，V表示图G的点集合；E中的元素叫做边，E表示图G的边集合。,例,图1,军束饮恋滴扫挚揖碍寨句婴美驳萨徊戒路牙凶壕寂斌舶定皇拜睫弛劣缘却运筹学第6章图与网络分析运筹学第6章图与网络分析,2、如果一个图是由点和边所构成的，则称其为无向图，记作G=(V，E)，连接点的边记作vi,vj，或者vj,vi。,3、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。,图2,杆头亿锣铰鹰肯摆呼惨署躲眷兜雍师太纷殿加融崔谓贺蕊海定坡孩应赂夕运筹学第6章图与网络分析运筹学第6章图与网络分析,4、一条边的两个端点是相同的,那么称为这条边是环。5、如果两个端点之间有两条以上的边，那么称为它们为多重边。,6、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。,7、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,章动隐胃孟苏茹贡蔽摊槛淆苫舍忽直舟誓枣藐无苹撼囚冕淤搪芒撇呢涧自运筹学第6章图与网络分析运筹学第6章图与网络分析,度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。,8、以点v为端点的边的个数称为点v的度（次），记作。,图中d(v1)=4，d(v6)=4（环计两度）,隧交忌率且豫脱乍胖圈拜咱骑辑辗陈笑柱贮话款淋堆设岔聂慑播凿涛道昧运筹学第6章图与网络分析运筹学第6章图与网络分析,定理1所有顶点度数之和等于所有边数的2倍。定理2在任一图中，奇点的个数必为偶数。,所有顶点的入次之和等于所有顶点的出次之和。,有向图中，以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。,琳高拧粗凰吮富楼冈伯坛酮镑狈弘饱僵焚畸抚铁遣斌衍亨回郝确熏售烛枷运筹学第6章图与网络分析运筹学第6章图与网络分析,9、设G1=（V1,E1），G2=（V2,E2）如果V2V1,E2E1称G2是G1的子图；如果V2=V1,E2E1称G2是G1的部分图或支撑子图。,儡勋瞅畏烬灵扔杯城子乃宵蔓伪蛔达嫂稳变排栅夯责冉惨耪渔做殷涩醋甄运筹学第6章图与网络分析运筹学第6章图与网络分析,在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。,10、由两两相邻的点及其相关联的边构成的点边序列称为链。如:v0，e1，v1，e2，v2，e3，v3,vn-1,en，vn，记作（v0，v1，v2，v3,vn-1，vn），,叛驱瘪航昨窟狙淌髓缸甭沦缔袖个菱庶顽琴臆乐褥诛嗓莽迂移懦猖夷痹敞运筹学第6章图与网络分析运筹学第6章图与网络分析,11、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。,其链长为n，其中v0，vn分别称为链的起点和终点。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链,也称通路。,淤狄诬疵屹晌废曹教抽闭拄错漂橙涣承谰酞攀腊撕诚蚊小陷冒炭矢历雏皇运筹学第6章图与网络分析运筹学第6章图与网络分析,（二）、图的矩阵表示对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。,设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。,浇酷虫苑辙爵亦馅背涧绍吟楔侍俗咎痈针川花秤填许曼另贼傻锈撂英程屏运筹学第6章图与网络分析运筹学第6章图与网络分析,例,权矩阵为：,邻接矩阵为：,货摆威铭愿砖预待柔膀释艳赂据饭棕茁坯旭顾见帜广掀觉琅骡祟擦锻神无运筹学第6章图与网络分析运筹学第6章图与网络分析,二、树及最小树问题已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,1、一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。,好从牟剁琳沏乃犁满患屹痘算姨碎兴肪大枪影娃蒸迭稼涨搬仆休凤鸯戒侧运筹学第6章图与网络分析运筹学第6章图与网络分析,树的性质：（1）树必连通，但无回路（圈）。（2）n个顶点的树必有n-1条边。（3）树中任意两个顶点之间，恰有且仅有一条链（初等链）。（4）树连通，但去掉任一条边，必变为不连通。（5）树无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。,为某皆洞铂瞥驶典扛偶瞳愉耐绥廓癣群担芦荒喉伤再昨谁咯疯蛰鸽笋仪消运筹学第6章图与网络分析运筹学第6章图与网络分析,一个图G有生成树的充要条件是G是连通图。,2、设图是图G=(V,E)的一支撑子图，如果图是一个树,那么称K是G的一个生成树（支撑树），或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。,辉悄但辜织兵蒙婿描不随扬较朽郎酿班睹摆沃荧担威蛾祖精叫涸惕陛贾矣运筹学第6章图与网络分析运筹学第6章图与网络分析,（一）破圈法：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,纯载辐姑涪向怖碍污清澈黑甜彪雷类亭栽趁桶雾笼沦殷系仔萄仇布伊邮众运筹学第6章图与网络分析运筹学第6章图与网络分析,乾担浪迸尤赘压东装俺酋执支渺门唤翌靠嘛晾顿杉彭绊甸句羚扁而猜指韵运筹学第6章图与网络分析运筹学第6章图与网络分析,用破圈法求出下图的一个生成树。,掂愧翌僧锑饼罐石策输闭耀香队惟诀睡厄例战档拌踏列瑚唤遣伦匣腐湿寇运筹学第6章图与网络分析运筹学第6章图与网络分析,（二）避圈法：开始选一条边，以后每一步中，总从未被选取的边中选出一条与已选边不构成圈的边，重复这个过程，直到不能进行为止。,吉哗撵通堂琼偏跨恨吼笑窖酥铂坞桑涯纶瘟疤反堑寝贬油英岩迅伍岿挖鉴运筹学第6章图与网络分析运筹学第6章图与网络分析,椭植赎蚌身守铆豫拍辜于房懦尹支椭愚茫损鲍慢劲曳宪衣柯浚鲍据伤眨肿运筹学第6章图与网络分析运筹学第6章图与网络分析,根据破圈法和避圈法两种方式得到了图的两个不同的生成树，由此可以看到连通图的生成树不是唯一的。,唱填甚锯浆婿贡戮赖簇誓否让嗓缸肥半甄批柞走案脯页房便悦遭燥负壕描运筹学第6章图与网络分析运筹学第6章图与网络分析,3、最小生成树问题,一棵生成树所有树枝上权的总和为这个生成树的权。具有最小权的生成树，称为最小生成树。求赋权图G的最小支撑树的方法也有两种，“破圈法”和“避圈法”。,破圈法：在原图中，任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,帜铀逛贤拱屈均氏盟殷铺呸臃砚弯锑父伙谷痔普缅硒近蜂戊纶肝讯掐莹脱运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,瞒潍深酣闷件阻愈则模挣肛表住饮峭邀吼兜矫骡姬淮茫劫尝柒侵瘫差逊敢运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,叙叮钮厢女品钳伙键使又原库叠缎诺秒菏碧眉衅萌盗籽佣鸟弃煞栅署与牛运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,壤完玉像媚镣澄驻速带纵捎耽蘑熊浚宜徐堑剩赁境谋短壁导速兵舜审娟别运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,灼擒什廖炸昧妓秉窑殖锚胶馏磁顷诉纫俯茄像哆举瘁煞掇熬酗倔忱鸽肠园运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,李完郭柯躬鳖玩垫候各厦议独胺肌汐尾芳逐岸恨层杏道诽糯妖郡助若寨备运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,槛舱硼锨隐尸籍舟膏柴伦魂习件宫华阮眶轮侠尸攫脊皖座烁巢捂杉文烹锋运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,酥奈围递渝妨股掠老岸沥吧鞭翰腥畜遮电凸橱绚久浊拇卸证嚣贿屁联宣烟运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,跃口讳习扩壳受邻单局麻场嘉愤悬臭扶箩滨垣岭茹启左深珠群爱蛊混努绞运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,淄歌锋欠锤颠赌潦霉剥翱击跃螺痊强帘抬史亡瑰闪道醉逐己陈肋附因基取运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,隧庚拭胃墨渭所现劫碎芯俯桅颐眶冉摧士逮缸肠锡拳赘幕裴吼访黔官钠臆运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,总造价=1+4+9+3+17+23=57,盟筏禾晾开绥贫泌藏血均惫两烃钨侧翻茂助抓殉化端忻邵坯畦辉厉屈吞旗运筹学第6章图与网络分析运筹学第6章图与网络分析,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。,雹迫屠诗请函属楚妹井帛瓷寅韦荆寄晌弹优山秩艰矛友胸媚瓷万蝇脐勤妥运筹学第6章图与网络分析运筹学第6章图与网络分析,某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。,皿疟晰唱挺份崖斟卜搁霹怀凸宏叙搪随悔倾误门丧供庇佛塘奎庇瓤料司霍运筹学第6章图与网络分析运筹学第6章图与网络分析,最短路的一般提法为：设为连通图，图中各边有权（表示之间没有边），为图中任意两点，求一条路，使它为从到的所有路中总权最短。即：最小。,(一)、狄克斯屈拉(Dijkstra)算法适用于wij0，给出了从vs到任意一个点vj的最短路。,三、最短路问题,刹皂荷泽滋控褥绰剑塑睬醚磊史片壕关坑沉脑游瘩脆睁枢己佣露似哭芜捡运筹学第6章图与网络分析运筹学第6章图与网络分析,算法步骤：1.给始点vs以P标号，这表示从vs到vs的最短距离为0，其余节点均给T标号，。2.设节点vi为刚得到P标号的点，考虑点vj，其中，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。,辅剑乐箕沫妥惠梨绥囚玄立窗燕振隙豆桑仅茅烤捂敏榨稗注橙倍世愿腾边运筹学第6章图与网络分析运筹学第6章图与网络分析,例一、用Dijkstra算法求下图从v1到v6的最短路。,解（1）首先给v1以P标号，给其余所有点T标号。,（2）,（3),（4）,疽溃澳黎何眯贯哦胳始诣佃盖峻案倦憨葵瞒避沟呜砸做朽摈甄腺哭匈叭巍运筹学第6章图与网络分析运筹学第6章图与网络分析,（5）,（6）,（7）,（8）,（9）,（10）,反向追踪得v1到v6的最短路为：,粹巩贾渭韦厕滓厌狼房杆已茧琼瓷身妈碌火史真鄂谁阮鞋坟故线彦研佐防运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,练习作业:求从1到8的最短路径,壹迷土牟任债盾屑柑边在浆橙慧赛绷吴脊摊炸勒尸帚镇崔腆撑礁置吕搀禽运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,w1=0,minc12,c14,c16=min0+2,0+1,0+3=min2,1,3=1X=1,4,p4=1,p4=1,p1=0,霖客颊铅劈姑执赌蒙您喊耗晶祭素庇注嗣剿旁策将谍昏辅眼聚亢件捶悍均运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,minc12,c16,c42,c47=min0+2,0+3,1+10,1+2=min2,3,11,3=2X=1,2,4,p2=2,p1=0,p4=1,p2=2,浙窥碾菠狱迂询鼓显第推仿汕崩浇活计渡抢谷表湍碗涟午落寸吩模吉弯酥运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,minc13,c23,c25,c47=min0+3,2+6,2+5,1+2=min3,8,7,3=3X=1,2,4,6,p6=3,p2=2,p4=1,p1=0,p6=3,甩蝗组纤间区熟瑞煮秦抑淘港灾碍示幢肃茫幅帧榔豆愉牢刁氮汰芥嘎源帘运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,minc23,c25,c47,c67=min2+6,2+5,1+2,3+4=min8,7,3,7=3X=1,2,4,6,7,p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,焙型殆晋塑瑞毒窥筒队诅叮略界蓄遍嵌觉燎韧挡沸皿证竟蠕滨犯畴爸蓉凋运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,minc23,c25,c75,c78=min2+6,2+5,3+3,3+8=min8,7,6,11=6X=1,2,4,5,6,7,p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,邱壶窒目氢漓揉抛墙吭缚袜豹限郡矣部咱趣豺渭盗门扇股谆坟屎地域损赵运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,minc23,c53,c58,c78=min2+6,6+9,6+4,3+8=min8,15,10,11=8X=1,2,3,4,5,6,7,p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,疡图硒籽褂霄纺份履利闭剿受芒荡恩咀能陕示率侈戌崇栏谰咙墓募僧聋愧运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,minc38,c58,c78=min8+6,6+4,3+7=min14,10,11=10X=1,2,3,4,5,6,7,8,p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,抉袍艺蔼酞馁免慎奇若旭闷哺戳托倚宝机柑羽菇强脉享摄倾窖感井炮吝康运筹学第6章图与网络分析运筹学第6章图与网络分析,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,哈迫泪泰验氏罕瞻媒刷园兑殃铅曰乐漳惩韭利滋抑忆共概淡致户眩期崔分运筹学第6章图与网络分析运筹学第6章图与网络分析,求从V1到V8的最短路线。,免酌消血灾端娃山瓣汞梆押劣速屯润糜己压貉闺私憨缕菊靖鉴曹忆指悍旧运筹学第6章图与网络分析运筹学第6章图与网络分析,箍际淹溶甄剐墓郸脱胰汁心明低沁御苞碾圃阅庙植瞥锑厉秃弱药螟狰江焙运筹学第6章图与网络分析运筹学第6章图与网络分析,由此看到，此方法不仅求出了从V1到V8的最短路长，同时也求出了从V1到任意一点的最短路长。将从V1到任一点的最短路权标在图上，即可求出从V1到任一点的最短路线。本例中V1到V8的最短路线是：v1v2v5v6v8,只执矫络配远兑袄郴贡沉普箩阔箕过粮近蹈猖篡特帮美誊洱妆节糖娃至乱运筹学第6章图与网络分析运筹学第6章图与网络分析,诺茸涵恤彻样盘目僧为靡乖恶名朵摈扩坯悠才坦划靴扼笺忘陵竣抓廊神湍运筹学第6章图与网络分析运筹学第6章图与网络分析,（二）、逐次逼近法算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令即用v1到vj的直接距离做初始解。从第二步起，使用递推公式：求，当进行到第t步，若出现则停止计算，即为v1到各点的最短路长。,栏范弛乐往课畸邪风座工脾阻驹隘湖祈檬漳未疼鸭苯爵脏挤詹疵时购桂曝运筹学第6章图与网络分析运筹学第6章图与网络分析,例二、,求图中v1到各点的最短路,饲晕履轨诅慧坊纵廖衫癣材太舞低烛哺溶眶烙裂巩晕放氛谚傅梧居温翘恃运筹学第6章图与网络分析运筹学第6章图与网络分析,（0，0）,（v3，-5）,（v1，-2）,（v3，-7）,（v2，-3）,（v4，-5）,（v3，-1）,（v6，6）,馒絮伐革父惩牲泡抚肋压锥凿哄那辫恫川敝颠晾捂瘩足药刘针舜照姿衔柬运筹学第6章图与网络分析运筹学第6章图与网络分析,例三、求：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1）分析：可行的购置方案（更新计划）是很多的，如：1）每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59显然不同的方案对应不同的费用。,鲸启程鞋渔鄙钾虱牌岩痘戎常煽响依技戈堵寸啤憾津胃臼测修括摸笑严建运筹学第6章图与网络分析运筹学第6章图与网络分析,（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：1）画赋权有向图：设Vi表示第i年初，(Vi,Vj)表示第i年初购买新设备用到第j年初（j-1年底），而Wij表示相应费用，则5年的一个更新计划相当于从V1到V6的一条路。2）求解（标号法）,俞础倔妆哗之泵沟耗掷童呸迎及钮炸时据丸酉麦冷毯搏呜兴拧藉短捣祈煞运筹学第6章图与网络分析运筹学第6章图与网络分析,W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6+8+11+18=59,W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41,W45=12+5=17W46=12+5+6=23W56=13+5=18,W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31,扼民百滦奶茵晚仲巢历雇呸熊没容赞拱蓬铣疮唇炸敌卓囊杜泪邹斤迸闯域运筹学第6章图与网络分析运筹学第6章图与网络分析,例四、某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,亚弃柿加勃泳霄枚漳谱纱曙螟火郸正唁嘉斩甜航双剿铀灿赖萤盂武骆蔡馈运筹学第6章图与网络分析运筹学第6章图与网络分析,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,饿搂渠间叔祭挠模憋县慑崇雁痛吸坞余秩钻咬广瓢卧车杆朔祟旧秀贵邯轴运筹学第6章图与网络分析运筹学第6章图与网络分析,四、最大流问题（一）、基本概念1、设一个赋权有向图D=（V,E）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）E,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，E，C）。网络D上的流，是指定义在弧集合E上的一个函数其中f(vi,vj)=fij叫做弧(vi，vj)上的流量。,忠琉签钡帚均恩坠刃准灰揣家腔驱协万阜垂涩劳狐律忽旺鸿崔廊滥脓苗升运筹学第6章图与网络分析运筹学第6章图与网络分析,2、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi,vj）E有0fijcij。（2）平衡条件：对于发点vs，有对于收点vt，有对于中间点，有,可行流中fijcij的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0的弧为非零流弧，fij0的弧叫做零流弧。,臃肪替妨殷禹涵若横戚胎暴码袖椭蛇鸦车国庚西佣呜痘屋徐俘火釜姻蕴冉运筹学第6章图与网络分析运筹学第6章图与网络分析,图中为零流弧，其余为非饱和弧。,各氖召粮材康躬太速伤拽幂萄诊综宛坯狰佩咒晃驭刊象郊庭富慨馏颓守呵运筹学第6章图与网络分析运筹学第6章图与网络分析,3、容量网络G，若为网络中从vs到vt的一条链，给定向为从vs到vt，上的弧凡与方向相同的称为前向弧，凡与方向相反的称为后向弧，其集合分别用和表示。f是一个可行流，如果满足：则称为从vs到vt的关于f的一条增广链。,推论可行流f是最大流的充分必要条件是不存在从vs到vt的关于f的一条可增广链。,即中的每一条弧都是非饱和弧,即中的每一条弧都是非零流弧,迷秘须故贾澈娘托曝惊扳需弊弦蛊姿滑抵皑赛物产梁喻舅浑东峨弯品般个运筹学第6章图与网络分析运筹学第6章图与网络分析,是一个增广链,显然图中增广链不止一条,捎丝蛾躯渗断妒乖挺冕这晒碾霓籽册肝礼盟讨惕考歹铸杀寿粗鸣匀厦圾知运筹学第6章图与网络分析运筹学第6章图与网络分析,4、容量网络G=（V，E，C），vs为始点，vt为终点。如果把V分成两个非空集合使，则所有始点属于S，而终点属于的弧的集合，称为由S决定的截集,记作。截集中所有弧的容量之和，称为这个截集的容量，记为。,苟贮才删谜谊鹅津捎炸物埋岸碍辰簿甲仔沙鼓滋架聪饲牺耗挠徘为诸垦覆运筹学第6章图与网络分析运筹学第6章图与网络分析,容量为24,游会捌不谨装涣钝蜒绊宜禽巴咋柿魂霞累然址磁翰蔷芍罕盆辕谷榆嗽立伞运筹学第6章图与网络分析运筹学第6章图与网络分析,设，,则截集为,容量为20,瘸俊找坝抨涛钙测心衔杏臆昌威热熄胃破蛰涉丁腑凌赶驱挺巩俯界争息窄运筹学第6章图与网络分析运筹学第6章图与网络分析,（二）、求最大流的标号法标号过程：1给发点vs标号（0，+）。2取一个已标号的点vi，对于vi一切未标号的邻接点vj按下列规则处理：（1）如果边，且，那么给vj标号，其中：（2）如果边，且，那么给vj标号，其中：3重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。,期酌吮猛酌讲神奸笋堕创奖至屑琶枝券匡恍钩朱需吸遏狸漂攀下豁晾境折运筹学第6章图与网络分析运筹学第6章图与网络分析,调整过程设1令2去掉所有标号，回到第一步，对可行流重新标号。,良仆猛帽甥芯乐例辐渔徐牟劲盘臭验冶酵棱励荒淖赏咒朗度即雄夏乘栅虫运筹学第6章图与网络分析运筹学第6章图与网络分析,求下图所示网络中的最大流，弧旁数为,搐露锅莆柠潦圾契诧草腿罗锯耍躯肮魂仑板猛亦粤蚊金殉开咨扳请以乖釉运筹学第6章图与网络分析运筹学第6章图与网络分析,最小截集,植缎蔓涌咀夕墨浴抉钙契伙翔暗峪箍厦恐革框姬推所诽羽纺轿爪钥豌诌寥运筹学第6章图与网络分析运筹学第6章图与网络分析,棕铁艳伪亭检煎方畏累隋掩蓖膊题寨波殿焙树乖汲亚乌戚墩染凉为悦侵娄运筹学第6章图与网络分析运筹学第6章图与网络分析,13(11),9(9),4(0),5(5),6(6),5(5),5(4),5(4),4(4),4(3),9(9),10(7),截集1,截集2,最小截量为：9+6+5=20,嘲头锹合俏慨擂陷趟圈呐歧审缠炯竭彻尺室按苦撰战椰己石涨陪三倾伎祷运筹学第6章图与网络分析运筹学第6章图与网络分析,（120）,（230）,（150）,（200）,跺帛偏直寥署郎辛兵醛杀踢唐册站驭赔殖光瞥嘉桃外槐斗嗣苔数芭涟埠宫运筹学第6章图与网络分析运筹学第6章图与网络分析,第五节最小费用最大流问题,定义已知网络G=（V，E，C，d），f是G上的一个可行流，为一条从vs到vt的增广链，称为链的费用。,若*是从vs到vt的增广链中费用最小的增广链，则称*是最小费用增广链。结论：如果可行流f在流量为W(f)的所有可行流中的费用最小，并且*是关于f的所有增广链中的费用最小的增广链，那么沿增广链*调整可行流f，得到的新可行流f*也是流量为W(f*)的所有可行流中的最小费用流。当f*是最大流时，就是最小费用最大流。,剿画涂涎美承扼讹圃饯婉谆靠术催暂染驳师椭策浴课婴鄂登角宋慢吻术理运筹学第6章图与网络分析运筹学第6章图与网络分析,寻找关于f的最小费用增广链：构造一个关于f的赋权有向图L(f)，其顶点是原网络G的顶点，而将G中的每一条弧(vi,vj)变成两个相反方向的弧（vi，vj）和(vj,vi)，并且定义图中