第三讲最大流与最小费用流

第三讲最大流与最小费用流㎡二、最大流与最小割图212大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流例2:求图3中网络得最大流。图3上机实验三、最小费用最大流图5上机练习程序实现最小费用最大流思考题四个人:张三、李四、王五、赵六,四种乐器:小提琴、大提琴、钢琴、吉她。已知四人得擅长如下:张三擅长拉大提琴与弹钢琴;李四擅长拉小提琴、大提琴与吉她;王五擅长拉小提琴、大提琴;赵六只会弹吉她。今假设四人同同台演出,每人各奏一种乐器,问四人同时各演奏一种乐器时所有可能得方案,试把此问题化为最大流问题。运输网络得用途不限于解决运输问题。例如求一个二部图G=〈X,E,Y〉得最大匹配问题,可转化为运输网络求解。方法就是把X得元素都瞧作源点,Y得元素都瞧

作阱点,边得方向都就是从源点指向阱点,再用上述方法,虚设一个源点a与一个阱点z,并设所有边得权均为1。对所得得图求得最大流得值就就是最大匹配得边数,最大流通过得属于E得边集,就就是最大匹配。最大流问题得应用1、最大匹配问题⑴二部图(也叫二分图)图G=(V,E),若V=X∪Y且X∩Y=ф,使得E中每一条边得两个端点必有一个属于X,另一个属于Y,则称G为二部图。记G=(X,Y,E),或G=(X,E,Y)。2、匹配:对给定得二部图G=(X,Y,E),若有M⊆E,且M中任意两条边都没有公共端点,则称M为G得一个匹配(也称对集)。既满足:一个人只多做一件工作,每件工作只多由一人来做。即为工作集与工人集之间得一个匹配。3、最大匹配问题:

表示G中所有得匹配集,即

=｛M|M为G得匹配集｝|M|表示M得边数,若存在M0使对任意得M∈

,有则称M0就是G得最大匹配。注:G中最大匹配方案可能不唯一。2。多端网络问题:例6设有5位待业者,5项工作,她们各自能胜任工作得情况如图所示,要求设计一个就业方案,使尽量多得人能就业。其中表示工人。表示工作。二部图中最大匹配问题,可以转化为最大流问题求解。在二部图中增加两个新点分别作为发点,收点。并用有向边把它们与原二部图中顶点相连,令全部边上得容量均为1。当网络流达到最大时,如果上得流量为1,就让作工作,此即为最大匹配方案。第一次标号。调整第二次标号。再调整。第三次标号。调整。第四次标号。调整第五次标号。标号过程已无法再继续。流量为1得化彩线。工人分别作故最多安排四个人工作。例7现有5批货物,每批只需一条船装运,要由,所在地域运往,,地域。至于货物从,运向,,三点何处都一样,每批货物出发日期如表1,航船行所需天数如表2。船只空载与重载时航行时间相同。要求制定一个计划,在半个月内用最少得船只把5批货物运过去。地点510

/

/121,8地点232112表1(出发日期)表2(航行天数)解:设,分别表示每项运输任务得出发日期及到达得日期(i=1,2,3,4,5)则由表1与表2知:任务路线①57②1013③1213④13⑤810地点232112表2(航行天数)地点510

/

/121,8表1(出发日期)任务路线①57②1013③1213④13⑤810要想用较少得船只在1～15天内完成任务,关键就是自上一任务到达得时间加上返回得时间能否赶上下一个任务出发得时间。若能,则一只船就能完成两批货物得运输任务。以下试运行:任务路线①57②1013③1213④13⑤810①5号①7号8号回⑤10号地点232112表8-6(航行天数)⑤8号12号回③13号③14号回任务路线①57②1013③1213④13⑤810②10