Homework (2011/12/23) Use Algorithm 5.1 to find a maximum flow and a minimum cut for the network shown below. (Assume f(a)=0 for each arc a.) s y x u.

Slides:



Advertisements
Similar presentations
苏少版《音乐》教材分析与 教学研究 江苏省中小学教研室 戴海云. 提 纲 第一部分 《音乐》教材分析 编写思路 主要特点 第二部分. 《音乐》教学实验与研究 教学研究 案例分析.
Advertisements

1 主持人:洪泰雄主任 104 年 6 月 23 日. 2 議 程 主席報告 監試手冊導讀 播放監試簡報 近年案例說明 考區重要提醒 提問與回應 5 分鐘 10 分鐘 15 分鐘 5 分鐘 10 分鐘.
第八章 土地行政管理.
「互联网金融2.0时代」与房地产的融合 广州互联网金融协会会长、广州e贷总裁 方颂.
企业会计学(三) 人大版本 吕 昌.
学生入党材料写作规范.
中国建筑特色 2013美国富布莱特项目 ——华文教师班暑期课 授课人:邵 英
小学科学中的化学 武威十九中 刘玉香.
中华传统文化 ——礼俗、宗法.
公平正义与中国社会转型 漫谈 主讲人:路振召 工作单位:河南科技大学马克思主义学院
第十一章 量測、分析及改善 8.0 量測、分析及改善包括: 規劃量測、分析及改善流程; 監督及量測; 不合格品管制; 資料分析及改善.
據點考核與評鑑 報告人:臺南市政府 照顧服務管理中心.
102年度統一入學測驗 報名作業說明會 時 間:101年12月14日(星期五) A.M.9:00~10:20 地 點:行政七樓講堂
P2P金融信用调查服务 2015年4月 诚信为先 中道厚德.
法學緒論第三單元:立法程序 課程設計: 財經法律系 --楊東連 法學緒論-3.
宋词四首.
特殊族群運動健康訓練(I).
依据教材 全国高等教育自学考试指定教材 《西方行政学说史》, 竺乾威主编,高等教育出版社。
丹 溪 翁 传 戴 良.
正 信 讀 書 會 主 持 群 : 姚 永 錩 、 鄭 健 、 陳 淑 珍 佛法的生活應用 2008/07/23.
非法集资典型案例评析 南京师范大学法学院 蔡道通 2016年1月.
专题(二) 交往沟通 掌握技能 命 题 解 读 背 景 材 料 新 题 演 练 考 点 链 接 1.
姓名:劉芷瑄 班級:J201 座號:39號 ISBN:957-33-1963-2
请说出牛顿第一定律的内容。.
小微企业融资担保产品介绍 再担保业务二部 贾天
民间器乐 第五章.
松竹梅岁寒三友 步入建交 桃李杏村暖一家 迈进职教 活出精彩.
2007年房地产建筑安装企业 税收自查方略 河北省地方税务局稽查局 杨文国.
™ 全球,唯一支持第三方自动部署的交易系统 中国产权交易所有限公司 二〇一四年十月 超级交易系统V1.0
就 业 协 议 书 将此幻灯片插入到演示文稿中 将此模板作为演示文稿(.ppt 文件)保存到计算机上。 打开将包含图像幻灯片的演示文稿。
大家都来关注国家安全 南京市江宁中学 傅德柱.
第八单元第二课第一课时 严守法律 温州四中 蒋莉青.
2008年工资统计报表填报要求 及指标解释 人事教育局薪酬与社会保障处
考研辅导讲座PPT 思想道德修养与法律基础 主讲:蒋中挺.
众筹实战培训 内蒙古环交所 李 蒙.
高级财务会计.
默写基础知识: 1、家庭是由 关系、 关系或 关系而结合成的亲属生活组织。家里有 ,家中有 。
Network Optimization: Models & Algorithms
什么是颈椎病? 颈椎病是指颈椎间盘退行性变,及其继发性椎间关节退行性变所致脊髓、神经、血管损害而表现的相应症状和体征。
組長:黃家逸 組員:殷浩賢、楊煜、吳家朗 毒品的害處.
广州市中考代数三大板块 数与式 方程(组)与不等式(组) 函数及其图象. 广州市中考代数三大板块 数与式 方程(组)与不等式(组) 函数及其图象.
第一单元 中国传统文化主流思想的演变.
孔子傳第三集: 興辦私學-禮學之美 生命教育工作坊.
学习贯彻十七大 提出的国防和军队 建设的方针原则和任务要求
时政发布 制作:宋虹雷.
密室逃脫在教學上的應用 綜合活動領域輔導團 林蓉姿.
公務人員退休法、撫卹法 法制與實務講習 銓敘部退撫司 中華民國99年8月.
《傅雷家书》 学 科:语文 年 级:九年级 授课教师:王宁宁.
八桥初中九年级思想品德课复习导学案之五---
小说与诗歌、散文、戏剧并称为四大文学体裁。
國三第五課 亞洲音樂漫遊.
第一節 行政裁量與不確定法律概念 第二節 行政裁量
《战国策》:范雎说秦王学习要点 一、《战国策》题解 二、长沙马王堆汉墓简介 三、《范雎说秦王》说明 四、《范雎说秦王》语言角度分析
初中图书馆综合阅读课程 图书馆知识普及 2013年3月.
苏轼的才能炉火纯青,苏轼的诗文才气贯天,苏轼的思想博大精深,苏轼的人格光芒万丈。 
本课设置5个环节 一、限时秒杀--5分钟 二、摩拳擦掌--9分钟 三、刀锋相见--20分钟 四、现炒现卖--5分钟 五、相约课后--1分钟.
从中国与联合国的关系演进 看联合国的产生与发展
LOM-領隊導向多人連線遊戲自動匹配演算法
特定消耗品說明 (指碳粉匣、墨水匣) 國立清華大學 保管組製作.
小学5.
第3节  认识简单机械.
加減法文字題 國小低年級學生對加減法文字題的瞭解 小組成員 陳育娟 羅珠綾 侯宜孜
飛行器製作與飛行 講師:劉修建.
乾坤袋:打造金融生态 互联网金融与产业金融的协同发展 王利丽 亿润投资互联网金融中心总经理 乾坤袋创始合伙人.
人民音乐出版社 七年级.
因果性:一个形而上学的预设 赵敦华 2008年5月.
臺中市龍山國小 校園常見瓢蟲辨識   瓢蟲屬於鞘翅目瓢蟲科。目前世界上約有5000多種瓢蟲,台灣地區約有80種以上,其中能捕食有害生物的瓢蟲約七十種之多。瓢蟲因為捕食有害生物為主食,所以又稱為『活農藥』。
裕民國小 100學年度第一學期 多元文化社團 直笛社團&合唱社團 期末成果發表會
Maximum Flow.
11506: Angry Programmer ★★★★☆ 題組:Contest Set Archive with Online Judge
Presentation transcript:

Homework (2011/12/23) Use Algorithm 5.1 to find a maximum flow and a minimum cut for the network shown below. (Assume f(a)=0 for each arc a.) s y x u v t 5 3 6 1 2 w r 7 z

Sol: (a) 找maximum flow: (1) 建立輔助圖D1 s y x u v t w r z 找s-t shortest path: 2,0 1,0 6,0 D=1 2,1 改為 1,1 6,1

原先的flow變成 s y x u v t 5 3 6 1 6,1 2,1 1,1 w r 7 2 z (不必重畫,直接在題目的圖做修改即可)

(2) 建立輔助圖D2 s y x u v t w r z 找s-t shortest path: 5,0 3,0 7,0 6,0 D=3 改為 5,3 3,3 7,3 6,3

flow變成 s y x u v t 5,3 3,3 6,3 5 1 6,1 2,1 6 1,1 3 w r 7,3 2 z (直接在題目的圖做修改即可)

(3) 建立輔助圖D3 s y x u v t w r z 找s-t shortest path: 1,0 5,0 2,0 6,3 D=1 改為 1,1 5,1 2,1 6,4

flow變成 s y x u v t 5,3 3,3 6,4 5,1 1,1 6,1 2,1 6 1 3 w r 7,3 2 z (直接在題目的圖做修改即可)

(4) 建立輔助圖D4 s y x u v t w r z 找s-t shortest path: 5,3 3,0 5,1 2,1 6,4 D=1 改為 5,4 3,1 5,2 2,2 6,5

flow變成 s y x u v t 5,4 3,3 6,5 5,2 1,1 6,1 2,1 6 1 3 w r 7,3 2,2 2 3,1 z (直接在題目的圖做修改即可)

(5) 建立輔助圖D5 s y x u v t w r z 找s-t shortest path: 2,1 3,0 5,2 1,0 6,1 D=1 改為 2,2 3,1 5,3 1,1 6,2

flow變成 s y x u v t 5,4 3,3 6,5 5,3 1,1 6,2 2,2 6 3,1 w r 7,3 2 z (直接在題目的圖做修改即可)

(6) 建立輔助圖D6 s y x u v t w r z 找s-t shortest path: 5,4 3,1 5,3 6,0 7,3 6,5 D=1 改為 5,5 3,2 5,4 6,1 7,4 6,6

flow變成 s y x u v t 5,5 3,3 6,6 5,4 1,1 6,2 2,2 6,1 3,1 w r 7,4 2 3,2 z (直接在題目的圖做修改即可)

(7) 建立輔助圖D7 s y x u v t w r z 此時已不存在s-t shortest path,表示前一頁的flow是maximum 且f(N)=8 (b) 找minimum cut: 上圖中,由 s 出發只能走到 s, 故P={s},P={u,v,w,r,x,y,z,t} minimum cut = (P,P) = {(s,u), (s,r), (s,x)} (這三條邊上的容量和剛好是8)