资源描述：
《运筹学与图论.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图与网络分析(GraphTheoryandNetworkAnalysis)1.图的基本概念与模型2.最小生成树问题3.最短路问题本章主要内容：图论运筹学的重要分支主要应用领域物理学、化学、控制论、信息论、科学管理、电子计算机等图论理论和方法应用实例在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法求解都很简便。图论的起源与发展欧拉
2、在1736年发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥问题。七桥问题：哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥。当时那里的居民热衷于这样的问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。图(a)欧拉将此问题归结为如图(b)所示图形的一笔画问题。即能否从某一点开始，不重复地一笔画出这个图形，最后回到出发点。欧拉证明了这是不可能的，因为图(b)中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。图：由点及点与点的连线构成，反映了实际生活中某些对象之间的某些特定关系。点
3、：代表研究的对象；连线：表示两个对象之间特定的关系。图：是反映对象之间关系的一种抽象。一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对反映对象之间的关系并不重要。1.图的基本概念与模型(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。a1a2a3a4a14a7a8a9a6a5a10a12
4、a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。下图就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。图的概念图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形。两点之间不带箭头的连线称为边，带箭头的连线称为弧。如果一个图G由点及
5、边所构成，则称之为无向图(也简称为图)，记为，式中V，E分别是G的点集合和边集合。一条连结点的边记为［］(或［］)。如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为()。无向图的例子其中无向图有向图的例子其中有向图v3e7e4e8e5e6e1e2e3v1v2v4v5边e可表示为e=[vi,vj]，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei
6、和ej相邻。端点,关联边,相邻如果边e的两个端点相重合，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5环,多重边,简单图图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。链，圈，连通图设图G＝（V，E），对G
7、的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。①②③④⑤⑥910201571419256网络（赋权图）图的模型应用例6.1有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F6个项目的比赛。下表中打√的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ABCDEF甲√√乙√√√丙√√丁√√戊√√√
8、己√√√解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。ABCDEF在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A一个班级的学
