第5章图与网络模型.ppt
《第5章图与网络模型.ppt》由会员分享,可在线阅读,更多相关《第5章图与网络模型.ppt(94页珍藏版)》请在优知文库上搜索。
1、管管 理理 运运 筹筹 学学1 第五章图与网络模型第五章图与网络模型1 1图与网络的基本概念图与网络的基本概念2 2最短路问题最短路问题3 3最小生成树问题最小生成树问题4 4最大流问题最大流问题5 5车间作业计划车间作业计划6 6统筹法(网络规划)统筹法(网络规划)管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学.管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹
2、 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学221 1图与网络的基本概念图与网络的基本概念 图论中图是由点和边构成,可以反映一些对象之间的关系。图论中图是由点和边构成,可以反映一些对象之间的关系。例如:在一个人群中,对相互认识这个关系我们可以用图例如:在一个人群中,对相互认识这个关系我们可以用图来表示,下图就是一个表示这种关系的图。来表示,下图就是一个表示这种关系的图。(v1)赵赵(
3、v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5管管 理理 运运 筹筹 学学23 1 1图与网络的基本概念图与网络的基本概念 当然图论不仅仅是要描述对象之间关系,还要研究特定关当然图论不仅仅是要描述对象之间关系,还要研究特定关系之间的内在规律,一般情况下图中点的相对位置如何、点与系之间的内在规律,一般情况下图中点的相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是重要点之间联线的长短曲直,对于反映对象之间的关系并不是重要的,如对赵等七人的相互认识关系我们也可以表示如下,可见的,如对赵等七人的相互认识关系我们也可以表示如下,可见图论中的
4、图与几何图、工程图是不一样的。图论中的图与几何图、工程图是不一样的。(v1)赵赵(v2)钱钱孙孙(v3)李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5管管 理理 运运 筹筹 学学241 1图与网络的基本概念图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识”的关系,那么只用两点之间的联线就很难刻画他们之间的关的关系,那么只用两点之间的联线就很难刻画他们之间的关
5、系了,这时我们引入一个带箭头的联线,称为弧。下图就是系了,这时我们引入一个带箭头的联线,称为弧。下图就是一个反映这七人一个反映这七人“认识认识”关系的图。相互认识用两条反向的关系的图。相互认识用两条反向的弧表示。弧表示。管管 理理 运运 筹筹 学学25 1 1图与网络的基本概念图与网络的基本概念 无向图:无向图:由点和边构成的图,记作由点和边构成的图,记作G=(V,E)。)。有向图:有向图:由点和弧构成的图,记作由点和弧构成的图,记作D=(V,A)。)。连通图连通图:对无向图对无向图G,若任何两个不同的点之间,至少存在一条链,则,若任何两个不同的点之间,至少存在一条链,则G为为连通图。连通图。
6、回路:回路:若路的第一个点和最后一个点相同,则该路为回路。若路的第一个点和最后一个点相同,则该路为回路。赋权图:赋权图:对一个无向图对一个无向图G的每一条边的每一条边(vi,vj),相应地有一个数,相应地有一个数wij,则称图,则称图G为赋权图,为赋权图,wij称为边称为边(vi,vj)上的权。上的权。网络:网络:在赋权的有向图在赋权的有向图D中指定一点,称为发点,指定另一点称为收点,中指定一点,称为发点,指定另一点称为收点,其它点称为中间点,并把其它点称为中间点,并把D中的每一条弧的赋权数称为弧的容量,中的每一条弧的赋权数称为弧的容量,D就就称为网络。称为网络。管管 理理 运运 筹筹 学学2
7、62 2最短路问题最短路问题最短路问题:对一个赋权的有向图最短路问题:对一个赋权的有向图D中的指定的两个点中的指定的两个点Vs和和Vt找到一条找到一条从从 Vs 到到 Vt 的路,使得这条路上所有弧的权数的总和最小,这条路被称的路,使得这条路上所有弧的权数的总和最小,这条路被称之为从之为从Vs到到Vt的最短路。这条路上所有弧的权数的总和被称为从的最短路。这条路上所有弧的权数的总和被称为从Vs到到Vt的距离。的距离。解最短路的解最短路的Dijkstra算法算法(双标号法)双标号法)步骤:步骤:1.给出点给出点V1以标号以标号(0,s)2.找出已标号的点的集合找出已标号的点的集合I,没标号的点的集
8、合,没标号的点的集合J以及弧的集合以及弧的集合3.如果上述弧的集合是空集,则计算结束。如果如果上述弧的集合是空集,则计算结束。如果vt已标号(已标号(lt,kt),则),则 vs到到vt的距离为的距离为lt,而从,而从 vs到到vt的最短路径,则可以从的最短路径,则可以从kt 反向追踪到起点反向追踪到起点vs 而得到。如果而得到。如果vt 未标号,则可以断言不存在从未标号,则可以断言不存在从 vs到到vt的有向路。如果上的有向路。如果上述的弧的集合不是空集,则转下一步。述的弧的集合不是空集,则转下一步。4.对上述弧的集合中的每一条弧,计算对上述弧的集合中的每一条弧,计算 sij=li+cij。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 模型
