图与网络分析基础知识ppt课件.ppt

《图与网络分析基础知识ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章图与网络分析1.问题的提出2.问题的模型3.问题的求解基础知识部分1.问题的提出1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支-----图论与几何拓扑。也由此展开了数学史上的新进程。问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。一笔画：三个结论结论⒈凡是由偶点组成的连通图，一定可以一笔画

2、成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。结论⒉凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。结论⒊其他情况的图都不能一笔画出。（奇点数除以二便可算出此图需几笔画成。）图论主要研究的对象如果用点表示研究的对象，用边表示对象之间的关系，则图G可以定义为点V和边E的集合。图论主要研究的对象如果用点表示研究的对象，用边表示对象之间的关系，则图G可以定义为点V和边E的集合。图论主要研究的对象如果用点表示研究的对象，用边表示对象之间的关系，则图G可以定义为点V和边E的集合。V={vi，

3、vj}图论主要研究的对象如果用点表示研究的对象，用边表示对象之间的关系，则图G可以定义为点V和边E的集合。E={ei，ej}基本概念&图的模型端点若e={vi，vj}，vi和vj为e的端点（顶点&节点）关联边相邻环多重边简单图无环，无多重边的图次，奇点，偶点，孤点evivj基本概念&图的模型链点边交替序列，边不重。圈点边交替序列，点边均不重复。路点边交替序列，起点和终点不重复。回路点边交替序列，起点和终点重复。连通图如果每一对顶点之间至少存在一条链完全图一个简单图中，任意两点之间均有边相连。基本概念&图的模型偶图（二分图）两图内顶点不相邻，图间顶点相邻

4、。完全偶图两图内顶点不相邻，图间所有顶点均相邻。边数m*n。子图点边均属于或等于母图。（点和边可能均不等于母图）部分图点相等，边不相等。子图不是部分图基本概念&图的模型树图无圈的连通图树图性质1任何树图必存在次为1的点。树图性质2具有n个顶点的树图的边数恰好为（n-1）条。树图性质3任何具有n个顶点，（n-1）条边的连通图是树图。说明1树是无圈连通图中边数最多的，加上一条边，就出现圈说明2树中任意两点之间有一条且仅有一条惟一通路。最小部分树如果G1是G2的部分图，又是树图，则称G1是G2的部分树（支撑树）。树图的各条边称为树枝。一般G2有多个树图，其中

5、树枝总长度最小的部分树称为最小部分树。基本概念&图的模型有向图（以前研究的都是无向图）如果规定连线是有方向的，称之为“弧”。就构成有向图。容量网络指对网络上的每条弧给出一个最大的通过能力（容量cij）发点（源点s）中间点收点（汇点t）网络最大流是指网络从发点到收点之间允许通过的最大流量。流是指加在网络各条弧上的一组负载量（fij）。零流（也是可行流）网络上所有fij=0。可行流在容量网络上，满足下列条件的一组流，称为可行流。（1）容量限制条件0≤fij≤cij（2）中间点平衡条件∑fij-∑fji=0网络总流量f（s-t）=∑f（s-i）=∑f（j-t

6、）所谓求网络最大流：就是指满足容量限制条件和中间点平衡条件下，使得总流量达到最大。显然是一个线性规划问题。2.问题的模型对于我们要研究的问题，确定具体对象及对象之间的性质联系，并且，用图的形式表示出来。这就是对研究问题建立图的模型。例如：最小部分树，最短路，中国邮路，网络最大流最小割等问题。广泛应用于：交通运输，管网规划，网络规划，通讯联络，城镇规划，市政建设，建环与设备工程，物流工程等。3.问题的求解类型1.相邻概念的应用类型2.求最小部分树。避圈法和破圈法类型3.求最短路问题。Dijkstra算法。类型4.城规问题。求任意两点间最短距离。类型5.求

7、网络最大流与最小割。Ford-Fulkerson标号算法。类型6.求最小费用流问题。类型1.相邻概念的应用P168【例1】由甲乙丙丁戊己六名运动员，报名参加ABCDEF六项比赛。他们分别申报的项目如表6-1所示。问，六个项目的比赛顺序应如何安排，能够实现每位运动员不连续参加两项比赛。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√将研究对象用点表示。对象与对象之间用边表示。ABCDEF甲√√√乙√√√丙√√丁√√戊√√√己√√√将研究对象用点表示。对象与对象之间用边表示。AABCDEF甲√

8、√√乙√√√丙√√丁√√戊√√√己√√√将研究对象用点表示。对象与对象之间用边表示。ABABC