《系统工程PPT课件（共8章）第08章 图与网络分析》由会员分享，可在线阅读，更多相关《系统工程PPT课件（共8章）第08章 图与网络分析（171页珍藏版）》请在金锄头文库上搜索。
1、 图与网络分析 第08章第08章 图与网络分析 17:02 图与网络分析 第08章1 引言2图和网络基本概念3树图与网络分析17:024最短路问题5网络最大流67最小费用与最大流题网络计划技术中国邮路问题8 图与网络分析 第08章知识点聚焦本章主要介绍有关图的概念、图的表示方法、图的应用。如最短路问题、最大流问题、最小费用问题，网络计划等问题。同时对图的遍历可以得到另一种没有回路的形式树及其最小树作了介绍。17:02 图与网络分析 第08章17:02已经学习了哪些？ 图与网络分析 第08章17:02本章主要介绍有关图的概念、图的表示方法、图的应用。如最短路问题、最大流问题、最小费用问题，网络计
2、划等问题。同时对图的遍历可以得到另一种没有回路的形式树及其最小树作了介绍。【知识点聚焦】 图与网络分析 第08章图论是组合优化、运筹学、电子学、通讯等学科重要基础。它已广泛地应用在控制论、信息论、电子计算机、交通管理等各个领域。在实际生活、工作中，有很多问题可以用图的理论和方法来解决。例如，在组织生产中，为完成某项生产任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。再例如，各种通信网络的合理架设，交通网络的合理分布等问题，应用图论的方法都能得到较好的解决。图论是专门研究图的理论的一门数
3、学分支，属于离散数学范畴，与运筹学有交叉，它有200多年历史，大体可划分为三个阶段。17:028.1 引言 图与网络分析 第08章第一阶段从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题由游戏而产生，最有代表性的工作就是所谓的Euler七桥问题，即一笔画问题。如图8-1所示。17:028.1 引言 图与网络分析 第08章第二阶段从十九世纪中叶到二十世纪中叶，图的问题大量涌现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，同时也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等。17:028.1引言 图与网络分析 第08章第三阶段二十
4、世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。最后，数学家Euler在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基础。Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。类似问题还有很多。17:028.1引言 图与网络分析 第08章图论中所说的图与一般所说的
5、几何图形或代数函数的图形是完全不同的概念。图论中的图是指由一些点的集合V和连接其中某些点对的线构成的集合E所组成的图形。下面先通过几个直观的实例认识什么是图。17:028.2 图和网络基本概念 图与网络分析 第08章在实际生活中，人们为了反映一些对象之间的关系，常常在纸上用点和线画出各种各样的示意图。【例8-1】 图8-2是我国北京、上海等10个城市间的铁路交通图，反映了这10个城市间的铁路分布情况。若用点代表城市，用点和点之间的连线代表两个城市之间的铁路线。如图8-2所示。诸如此类的还有电话线分布、天然气管道、高速公路、高等级铁路等图。17:028.2 图和网络基本概念8.2.1图的应用实例
6、 图与网络分析 第08章【例8-2】有甲、乙、丙、丁、戊5个球队，它们之间的比赛就可以用图表示出来，如图8-4。已知甲队和其他各队都比赛过一次，乙队和甲队比赛过，丙队和乙、丁队比赛过，丁队和丙、戊队比赛过，戊队和甲、丁队比赛过。为反映比赛情况，可以用点分别代表这5个队，若两个队之间已比赛过，就在这两个队所对应的点之间连一条线，这条线不过其他的点，如图8-3所示。17:028.2.1图的应用实例8.2 图和网络基本概念 图与网络分析 第08章图是反映对象之间关系的一种工具。在一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对于反映对象之间的关系，并不是重要的。如例8-2，也可以用如图
7、8-4所示的图去反映5个球队的比赛情况，这与图8-3没有本质的区别，图论中的图与几何图、工程图等是不同的。因为研究的思路方法不同，达到的目标也不同。17:028.2.1图的应用实例8.2 图和网络基本概念 图与网络分析 第08章前面两个例子中涉及的对象之间的“关系”具有“对称性”，就是说，如果甲与乙有这种关系，那么同时乙也与甲有这种关系。在实际生活中，有许多关系不具有这种对称性。譬如人们之间的认识关系，甲认识乙并不意味着乙也认识甲。比赛中的胜负关系也是这样，甲胜乙和乙胜甲是不同的。反映这种非对称的关系，只用一条连线就不行了。如例8-2，如果人们关心的是5个球队比赛的胜负情况，那么从图8-3中就
8、看不出来了。为了反映这一类关系，可以用一条带箭头的连线表示。例如球队v1胜了球队v2，可以引一条带箭头的连线表示。图8-5反映了5个球队比赛的胜负情况，可见v1三胜一负，v4打了三场球，全负等。类似胜负这种非对称性的关系，在生产相生活中是常见的，如交通运输申的“单行线”，部门之间的领导与被领导的关系、一项工程中各工序之间的先后关系等。17:028.2.1图的应用实例8.2 图和网络基本概念 图与网络分析 第08章图是反映对象之间关系的一种工具。在一般情况下，图中点的相对位置如何，点与点之间连线的长短曲直，对于反映对象之间的关系，并不是重要的。如例8-2，也可以用如图8-4所示的图去反映5个球队
9、的比赛情况，这与图8-3没有本质的区别，图论中的图与几何图、工程图等是不同的。因为研究的思路方法不同，达到的目标也不同。17:028.2.1图的应用实例8.2 图和网络基本概念图8-4 5个球队比赛示意图 图与网络分析 第08章【定义8-1】(1)图 由点集V=（vi）和V中元素的无序对的集合E=（ek）所构成的二元组，称为图。记为G=（V，E）。其中：V=（v1，v2，vm），是m个顶点集合； E=（e1，e2，en），是n条边集合。 或者说：一个图是由一些点及一些点之间的连线(不带箭头或带箭头)所组成。17:028.2.2.图的几个基本概念8.2 图和网络基本概念 图与网络分析 第08章(
10、2)边(弧) 把两点之间的不带箭头的连线称为边，带箭头的连线称为弧。(3)无向图 由点和边所构成的图，称之为无向图(也简称为图)，记为G=(V，E)，式中V，E分别是G的顶点集合和边集合。一条连接点vi，vjV的边e，记为e=vi，vj，或e=vj，vi。(4)有向图 由点和弧所构成的图称为有向图，记为D=(V，A)，式中V，A分别表示D的顶点集合和弧的集合。一条方向是从vi指向vj的弧a记为a=。vi称为a的始点，vj称为a的终点。17:028.2.2.图的几个基本概念8.2 图和网络基本概念 图与网络分析 第08章【定义8-2】(1)顶点数和边数 图G=(V，E)中，V中元素的个数称为图G
11、的顶点数，记作p(G)或简记为p；E中元素的个数称为图G的边数，记作q(G)，或简记为q。(2)端点和关联边 若ei=vi，vjE，则称顶点vi，vj为边ei的端点，边ei是顶点vi，和vj的关联边。(3)相邻顶点和相邻边 同一条边的两个端点称为相邻顶点，简称邻点；有公共端点的两条边称为相邻边，简称邻边。(4)多重边与环 具有相同端点的边称为多重边或平行边；两个端点落在一个顶点的边称为环。17:028.2.2.图的几个基本概念8.2 图和网络基本概念 图与网络分析 第08章(5)多重图和简单图 含有多重边的图称为多重图；无环也无多重边的图称为简单图。(6)度 以vi为端点的边的条数称为顶点的度
12、(有些书中也叫做次)，记作d(vi)。(7)悬挂点和悬挂边 度为1的点称为悬挂点；与悬挂点相连的边称为悬挂边。(8)孤立点 度为零的点称为孤立点。(9)奇点与偶点 度为奇数的顶点称为奇点；度为偶数的顶点称为偶点。例如，图8-6中，P(G)=6，q(G)=8；e3=v4，v3，v3与v4是e3的端点，e3是点v3和v4的关联边；v2与v5是邻点，e3与e2是邻边；e7与e8是多重边，e4是一个环；图8-6是一个多重图；v1是悬挂点，e1是悬挂边；v6是孤立点；v2是奇点，v3是偶点。17:028.2.2.图的几个基本概念8.2 图和网络基本概念 图与网络分析 第08章【定理8-1】 图G=(V，
13、E)中，所有顶点的度之和是边数的2倍。即 (8-1)17:028.2.2.图的几个基本概念8.2 图和网络基本概念定理8-1是显然的，因为在计算各顶点的度时，每条边都计算了两次，于是图G中全部顶点的度之和就是边数的2倍。 图与网络分析 第08章【定理8-2】 任一图G中，奇点的个数为偶数。证明 设V1、V2分别是G中奇点和偶点的集合，由定理8-1可知17:028.2.2.图的几个基本概念8.2 图和网络基本概念 图与网络分析 第08章(2)边(弧) 把两点之间的不带箭头的连线称为边，带箭头的连线称为弧。(3)无向图 由点和边所构成的图，称之为无向图(也简称为图)，记为G=(V，E)，式中V，E
14、分别是G的顶点集合和边集合。一条连接点vi，vjV的边e，记为e=vi，vj，或e=vj，vi。(4)有向图 由点和弧所构成的图称为有向图，记为D=(V，A)，式中V，A分别表示D的顶点集合和弧的集合。一条方向是从vi指向vj的弧a记为a=。vi称为a的始点，vj称为a的终点。17:028.2.2.图的几个基本概念8.2 图和网络基本概念 图与网络分析 第08章(2)边(弧) 把两点之间的不带箭头的连线称为边，带箭头的连线称为弧。(3)无向图 由点和边所构成的图，称之为无向图(也简称为图)，记为G=(V，E)，式中V，E分别是G的顶点集合和边集合。一条连接点vi，vjV的边e，记为e=vi，v
15、j，或e=vj，vi。(4)有向图 由点和弧所构成的图称为有向图，记为D=(V，A)，式中V，A分别表示D的顶点集合和弧的集合。一条方向是从vi指向vj的弧a记为a=。vi称为a的始点，vj称为a的终点。17:028.2.2.图的几个基本概念8.2 图和网络基本概念 图与网络分析 第08章(2)边(弧) 把两点之间的不带箭头的连线称为边，带箭头的连线称为弧。(3)无向图 由点和边所构成的图，称之为无向图(也简称为图)，记为G=(V，E)，式中V，E分别是G的顶点集合和边集合。一条连接点vi，vjV的边e，记为e=vi，vj，或e=vj，vi。(4)有向图 由点和弧所构成的图称为有向图，记为D=
16、(V，A)，式中V，A分别表示D的顶点集合和弧的集合。一条方向是从vi指向vj的弧a记为a=。vi称为a的始点，vj称为a的终点。17:028.2.2.图的几个基本概念8.2 图和网络基本概念 图与网络分析 第08章如何把图的有关信息输入和存储到计算机里去呢?由于图的最本质的内容是顶点与顶点的关系或者边与顶点间的关联关系，因此可用矩阵来表示这种关联关系。1)关联矩阵给定无向图G=(V，E)，其中V=v1，v2，.，vn，E=e1，e2，.，en。若用矩阵的行标号i对应图G的顶点下标，用列标号j对应图G的边的下标，可构造一个n*m矩阵B(G)=(bij)n*m，与图G对应，其中17:028.2.3.图的矩阵表示8.2 图和网络基本概念 (8-3) 图与网络分析 第08章(2)边(弧) 把两点之间的不带箭头的连线称为边，带箭头的连线称为弧。(3)无向图 由点和边所构成的图，称之为无向图(也简称为图)，记为G=(V，E)，式中V，E分别是G的顶点集合和边集合。一条连接点vi，vjV的边e，记为e=vi，vj，或e=vj，vi。(4)有向图 由点和弧所构成的图称为有向图，记为D=(V，A)，式
