运筹学 网络模型

《运筹学 网络模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学OperationsResearchChapter6网络模型NetworkModeling姜海博士副教授haijiang@tsinghua.edu.cn清华大学工业工程系Ch6网络模型NetworkModel2012年1月30日星期一Page26.0基础Fundamentals6.1最小(支撑)树问题Minimal(Spanning)TreeProblem6.2最短路问题ShortestPathProblem6.3最大流问题MaximalFlowProblem6.4旅行售货员与中国邮路问题TravelingSalesmanandChinaCarrierPro

2、blemCh6网络模型NetworkModel2012年1月30日星期一Page3v18v37v5545812v23v6v64图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）若每条边上都赋有一个权，其图称为赋权图（4）建立一个网络模型，求最大值或最小值Ch6网络模型NetworkModel2012年1月30日星期一Page4点集合记为v18v37v55Vvv1,,2,v654821v23v46v6边用[v,v]表示或简记为[i，j]，集合记为ijE＝[12]

3、,[13],，，,[56]，边上的数字称为权，记为w[v,v]、w[i，j]或w，集合记为ijijWwww12,13,14,,w56网络图可记为G＝｛V，E，W｝Ch6网络模型NetworkModel2012年1月30日星期一Page5•路径peee12k...VoVV2Vk-1Vk1路径P是一系列的顶点v0,v1,…,vk且对i=1,…k,vi-1和vi相连路径p是一系列的边e,…,e且对i=2,…k边ee共用一个顶点1ki-1,i简单路：没有重复顶点的路圈：起点和终点相同的路Ch6网络模型NetworkModel2012年1月30日星期一Page6连通

4、图：任意两点之间有一条路Ch6网络模型NetworkModel2012年1月30日星期一Page7图的表示方法：邻接矩阵假设图有n个节点1A是nn的矩阵123423101101(i,j)E210104A(i,j)0其他31101400102空间消耗n-nCh6网络模型NetworkModel2012年1月30日星期一Page8图的表示方法：邻接链表Adj(v)=与节点v相邻的节点列表1123232133124443空间消耗：m+nCh6网络模型图的搜索算法NetworkModel2012年1月30日星期一Page9图的搜索算法（a）从图中某一点出发，能

5、够到达的所有节点（b）确定一个图是否互相连通（c）确定图是否有圈步骤：1.将节点s存入L中，将所有节点标记为未访问2.如果L非空，则从L中取出一个节点v，将其标记为已访问3.逐一查看与节点v相邻的节点，也即adj(v)中的节点k，如果k尚未标记为已访问a)将其标记为已访问并存入L中b)将v记为k的前节点，也即pred(k)=v4.返回第2步5.所以被标记为已访问的节点即为从s出发能够到达的节点Ch6网络模型NetworkModel2012年1月30日星期一Page10先进先出：25广度优先搜索163425L=12345616pred=1122434Ch6网络模型N

6、etworkModel2012年1月30日星期一Page11后进先出：25深度优先搜索1634251634Ch6网络模型NetworkModel2012年1月30日星期一Page12如何判断一个图是否有圈步骤：1.任选一个节点s存入L中，将所有节点标记为未访问2.如果L非空，则从L中取出一个节点v，将其标记为已访问3.逐一查看与节点v相邻的节点，也即adj(v)中的节点ka)如果k尚未标记为已访问i.将其标记为已访问并存入L中ii.将v记为k的前节点，也即pred(k)=vb)如果k已经标记为已访问，则找到了一个圈4.返回第2步5.如果所有节点均已标记为已访问，停

7、止。否则，任选一个未标记为已访问的节点，重复上面的步骤Ch6网络模型NetworkModel2012年1月30日星期一Page13练习：从节点A开始分别应用宽度优先和深度优先搜索，列出节点访问的顺序6.1最小(支撑)树问题Minimal(Spanning)TreeProblemCh6网络模型6.1最小树问题NetworkModelMinimaltreeproblem2012年1月30日星期一Page156.1.1树的概念一个无圈并且连通的无向图称为树(Tree)一些结论：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉

8、任意一条边