- 1、本文档共44页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第六章 图与网路分析;;6.1 图与网路的基本概念; 6.1.2 无向图与有向图; 6.1.3 端点,关联边,相邻,次; 6.1.3 端点,关联边,相邻,次; 6.1.4 链,圈,路径,回路,连通图;6.2 树图与最小生成树; 6.2.1 树的定义及其性质; 6.2.2 图的生成树; 6.2.3 最小生成树; 6.2.3 最小生成树; 6.2.3 最小生成树;6.3 最短路问题;例1 狄克斯特拉算法; Dijkstra最短路算法的特点和适应范围; 6.3.2 Warshall-Floyd算法 (1962);例 6.3.2 求下图具有负权网络图始点v1到终点v 8的最短路径及其长度。;; 6.3.4 最短路应用举例——市话扩容 (实装率=0.8);最短路应用举例 —市话扩容;小结;6.4 网路的最大流和最小截; 6.4.2 截集与截集容量; 6.4.3 确定网路最大流的标号法; 6.4.3 确定网路最大流的标号法; 最大流最小截的标号法步骤; 最大流最小截的标号法步骤;最大流最小截集的标号法举例;最大流最小截集的标号法举例; 6.4.4 多端网路问题; 6.4.5 最小费用最大流;6.4.5 最小费用最大流
一、基本原理
1、若f ={fi, j}是流量为V(f)的所有可行流中费用最小者,而 ?是关于f的所有增广链中费用最小的增广链,那么,沿?去调整f得到的可行流f ‘就是流量为V(f ’)的所有可行流中的最小费用流。这样,当
f ‘是最大流时,它就是所求的最小费用最大流。
2、因为di j =0, f ={fi, j}=0必是流量为0 的最小费用流,因此,可从
f ={fi, j}=0开始。
3、给定有向网络G=(V,A),设f ={fi, j}是流量为V(f)的最小费用流,为寻找是关于f的最小费用增广链,构造年一赋权图W(f),该图的节点与原图G相同,但将网络中的每一弧变成两个相反方向的弧,其权定义如下:;二、基本步骤
1、取初始可行流为f(0) = 0;
2、构造W(f(0))并寻找从s到t 的最短路,即寻找关于f(0)的最小费用增广链 ,若不存在最短路,则f(0)就是最小费用最大流;若存在最短路,则在原网络中得到相应的最小费用增广链?,在?上对f(0)进行调整得f(1);
3、以f(1)代替f(0)重复2,直到找到最小费用最大流。
三、例 6.6 求如下图费用容量网络的最小费用最大流。图中,每一弧的第2个数字表示容量,第1个数字表示单位流量费用。
(P179-181); 6.4.5 以最短路为基础汇总???路上的流;6.5 欧拉回路和中国邮递员问题; 解中国邮递员问题的步骤; 解中国邮递员问题的步骤;6.6 哈密尔顿回路及旅行推销员问题; 6.6.2 旅行推销员问题(Traveling Salesman Problem); 6.7 选址问题;1、边上某点到节点的最短距离
dij 代表 vi 与 vj 间的最短距离,ars 代表边(r, s)的边长,令 h 为边(r, s)上一点的百分位,0? h? 1
边上对应 h 的一点到 vj 的最短距离为
d[h(r, s), j]=min[h?ars+drj, (1?h)?ars+dsj]
2、节点到某边上最远一点的距离
指定节点 j,它到边(r, s)上对应 h百分位点有两条路,最远点必使两条路一样长,故有
d[j, (r, s)]=0.5[djr+ djs+ ars]; 6.7.2 中心的选择; 例6.7.1~6.7.2
您可能关注的文档
- 药物血浆半衰期的测定讲述.pptx
- 药物制剂讲述.ppt
- 语文初三名著阅读讲座02(镇江实验学校)详解.ppt
- 药物过敏应急预案及程序讲述.ppt
- 药物经济学T软件的简介讲述.ppt
- 语文第一部分第四章病句的辨析与修改[配套课件]详解.ppt
- 语文乐园(四)王欣组详解.ppt
- 药理学第三十章抗组胺药讲述.ppt
- 药剂学课件-新型药物制剂(上)讲述.ppt
- 语文七年级下鲁教版7.1《骆驼祥子》课件6详解.ppt
- 2024至2030年中国人造棉面料行业投资前景及策略咨询报告.docx
- 重庆市渝中区遴选公务员2024年国家公务员考试考试大纲历年真题10340笔试历年典型考题及解题思路附.docx
- 2024至2030年中国甲基苯乙酮行业深度调研及发展预测报告.docx
- 2024至2030年中国羚羊角类饮片行业深度调查与前景预测分析报告.docx
- 重庆市面向中国农业大学定向选调2024届大学毕业生2024年国家公务员考试考试大纲历年真题14笔试历.docx
- 重庆市面向西北工业大学定向选调2024届大学毕业生00笔试历年典型考题及解题思路附答案详解.docx
- 中国不动杆菌感染治疗药行业市场现状分析及竞争格局与投资发展研究报告2024-2029版.docx
- 2024至2030年全球与中国ETL软件市场现状及未来发展趋势.docx
- 初中八年级(初二)生物下册期末考试1含答案解析.docx
- 干簧式继电器项目申请报告.docx
文档评论(0)