运筹学第十章图与网络优化课件.ppt

《运筹学第十章图与网络优化课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章图与网络优化(GraphTheoryandNetworkAnalysis)图的基本概念树及最小支撑树最短路问题网络最大流问题最小费用最大流问题中国邮递员问题图论的起源和发展1736年，Euler哥尼斯堡七桥问题(KönigsbergBridgeProblem)BACDABCD一笔画问题1847年，kirchhoff，电网络，“树”；1852年，《四色猜想》；1964年，华罗庚，《统筹方法平话》。1857年，Cogley，同分异构，“树”；1956年，杜邦公司，CPM，关键路线法；1958年，美国海军部

2、，PERT，计划评审技术；1962年，管梅谷，《中国邮路问题》；第一节图的基本概念一、几个例子例1是北京、上海等十个城市间的铁路交通图。与此类似的还有电话线分布图、煤气管道图、航空路线图等。北京天津济南青岛武汉南京上海郑州连云港徐州例2分别用点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，且这条线不过其他点。如下图所示：v1v2v3v4v5可知各队之间的比赛情况如下：甲——乙、丙、丁、戊乙——甲、丙丙——甲、乙、丁丁——甲、丙、戊戊——甲、

3、丁例3“染色问题”储存8种化学药品，其中某些药品不能存放在同一个库房里。用v1,v2,…,v8分别代表这8种药品。规定若两种药品不能存放在一起，则其相应的点之间联一条线。如下图所示：v1v2v3v4v5v6v7v8可知需要4个库房，其中一个答案是：{v1}{v2,v4,v7}{v3,v5}{v6,v8}还有其他的答案。二、基本概念有向图由点及弧所构成的图，记为D=(V,A)，V,A分别是D的点集合和弧集合。无向图由点及边所构成的图。记为G=(V,E),V，E分别是G的点集合和边集合。v1v2v3v4v1v2

4、v3v4a1a2a3a4a5e1e2e3e4e5a6e6边两点之间不带箭头的联线。如e3v1v4a3弧两点之间带箭头的联线。如a3v1v4e3端点及关联边若边e=[u,v]∈E，则称u,v为e的端点，也称u,v是相邻的，称e是点u(及点v)的关联边。如：v1,v4为e3的端点，v1,v4是相邻的，e3是v1（v4）的关联边。环若在图G中，某个边的两个端点相同，则称e是环。如e7v1v2v3v4e1e2e3e4e5e6e7多重边若两个点之间有多于一条的边，称这些边为多重边。如e1,e2简单图一个无环，无多重边

5、的图。多重图一个无环、但允许有多重边的图。点v的次以点vi为端点边的个数，记为dG(vi)或d(vi)。v1v2v3v4e1e2e3e4e5e6e7如d(v4)=5d(v2)=4v5悬挂点次为1的点，如v5悬挂边悬挂点的关联边，如e8e8孤立点次为0的点偶点次为偶数的点，如v2奇点次为奇数的点,如v5链中间点初等链圈初等圈简单圈v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9在上图中,(v1,v2,v3,v4,v5,v3,v6,v7)是一条链,但不是初等链在该链中,v2,v3,v4,v5,v

6、3,v6是中间点(v1,v2,v3,v6,v7)是一条初等链(v1,v2,v3,v4,v1)是一个初等圈(v4,v1,v2,v3,v5,v7,v6,v3,v4)是一个简单圈连通图图G中，若任何两个点之间，至少有一条链，称为连通图。否则称为不连通图。连通分图(分图)若G是不连通图，则它的每个连通的部分称为连通分图。v1v2v3v4e1e2e3e4e5e6v5v6e7如左图就是个不连通图，它是由两个连通分图构成的。支撑子图给定一个图G=(V,E)，如果图G’=(V’,E’)，使V’=V及E’E，则称G’是G的

7、一个支撑子图。v1v2v3v4(G)v1v2v3v4(G’)基础图给定一个有向图D=(V,A)，从D中去掉所有弧上的箭头，所得到的无向图称为基础图。记之为G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7路初等路回路v5简单有向图多重有向图权与网络在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或

8、收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。图的矩阵表示权矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437图的矩阵表示定理1图G=(V,E)中，所有点的次之和是边数