资源描述：
《《工程系统分析》教学课件 第4章 网络模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章网络模型§4-1网络模型及其特征§4-2图论基础§4-3最短路模型§4-4最大流模型§4-5最小费用流模型§4-6最小树模型§4-1网络模型及其特征网络模型的构成及其分类网络模型的特征§4-1网络模型及其特征一、网络模型的构成及其分类1.网络模型的构成（1）节点系统的组成要素（2）弧要素间的关系（3）流量要素间关系的量化a,b,ca,b§4-1网络模型及其特征一、网络模型的构成及其分类1.网络模型的构成2.网络模型的分类（1）以物质为流量§4-1网络模型及其特征一、网络模型的构成及其分类1.网络模型的构成2.网络模型的分类（1）以物质为流量（2）以信息为流量§4-1网络模型
2、及其特征一、网络模型的构成及其分类1.网络模型的构成2.网络模型的分类（1）以物质为流量（2）以信息为流量（3）以能量为流量§4-1网络模型及其特征一、网络模型的构成及其分类1.网络模型的构成2.网络模型的分类（1）以物质为流量（2）以信息为流量（3）以能量为流量（4）以时间、距离、费用等为流量§4-1网络模型及其特征一、网络模型的构成及其分类二、网络模型的特征1.能够直观地反映系统元素及其相互关系2.以不同的流量表述不同的系统问题3.特定流量具有特定的算法4.简单直观，易于掌握§4-2图论基础图的有关概念连通图与树§4-2图论基础一、图的有关概念1.图节点与弧的集合。设N为节点
3、的集合，E为弧的集合，则图G可以表示为：G={N，E}1234e1e2e3e4e5e6G={N，E}N={n1，n2，n3，n4}E={e1，e2，e3，e4，e5，e6}§4-2图论基础一、图的有关概念1.图2.自环首尾均在一个节点的弧如e21234e1e2e3e4e5e6§4-2图论基础一、图的有关概念1.图2.自环3.关联与邻接1234e1e2e3e4e5e6(1)节点与弧相互关联§4-2图论基础一、图的有关概念1.图2.自环3.关联与邻接1234e1e2e3e4e5e6(1)节点与弧相互关联(2)弧与弧相互关联§4-2图论基础一、图的有关概念1.图2.自环3.关联与邻接1
4、234e1e2e3e4e5e6(1)节点与弧相互关联(2)弧与弧相互关联(3)节点的邻接前导节点后续节点§4-2图论基础一、图的有关概念1.图2.自环3.关联与邻接4.链的有关概念1234e1e2e3e4e5e6对于任一节点序列n1,n2,…,nk+1,ei为ni-1,ni构成的弧，则弧的系列e1,e2,…,ek构成一条链。n1为链的始点，nk+1为链的终点，弧的数目k称为链的长度。（1）链例如，节点序列2,3,4构成的链234e3e5234e3e6e3234e4§4-2图论基础一、图的有关概念1.图2.自环3.关联与邻接4.链的有关概念1234e1e2e3e4e5e6（1）链（
5、2）路全部由同向弧组成的链例如，节点序列2,3,4构成的路234e3e5234e3e6§4-2图论基础一、图的有关概念1.图2.自环3.关联与邻接4.链的有关概念1234e1e2e3e4e5e6（1）链（2）路（3）圈始点和终点为同一节点的链（闭合链）例如，节点序列2,3,4构成的圈e5234e3234e3e6e4§4-2图论基础一、图的有关概念1.图2.自环3.关联与邻接4.链的有关概念1234e1e2e3e4e5e6（1）链（2）路（3）圈（4）回路始点和终点为同一节点的路全部由同向弧组成的圈例如，节点序列2,3,4构成的圈e5234e3§4-2图论基础一、图的有关概念二、连
6、通图与树1.连通图与不连通图1234e1e2e3e4e5e6（1）连通图：图中任意两节点间至少存在一条链（2）不连通图：图中至少有两节点间不存在链1234567§4-2图论基础一、图的有关概念二、连通图与树1.连通图与不连通图2.子图1234e1e2e3e4e5e6（1）由节点子集生成的子图：包括该节点子集及两个端点都在该节点子集上的所有弧。例如，由节点2,3,4生成的子图234e2e3e4e5e6§4-2图论基础一、图的有关概念二、连通图与树1.连通图与不连通图2.子图1234e1e2e3e4e5e6（2）由弧子集生成的子图：包括该弧子集及该弧子集的所有端点。例如，由弧e2,e
7、3,e4生成的子图e2234e3e4§4-2图论基础一、图的有关概念二、连通图与树1.连通图与不连通图2.子图3.树1234e1e2e3e4e5e6无圈的连通图或子图234e3e4§4-2图论基础一、图的有关概念二、连通图与树1.连通图与不连通图2.子图3.树4.有向图与无向图(1)有向图：规定了弧的方向的图（至少包含一条箭线）(2)无向图：未规定弧的方向的图（不包含任何箭线）§4-3最短路模型一、问题的提出通过网络各边所需要的时间、距离或费用等为已知时，欲找出从始点s至终点t的
