管理决策之网络分析与应用培训课件(ppt 38页)

内容摘要
图论(GraphTheory)
是运筹学的一个分支，已广泛应用在物理学、化学、控制论、信息论、科学管理、计算机等各个领域中。
网络分析（NetworkAnalysis）
作为图论的一个重要内容，已成为对各种系统进行分析、研究和管理的重要工具。本章主要介绍运输问题、最短路问题、最小支撑树问题、最大流问题，以及网络计划评审与优化问题。
图与网络的基本概念
图论中的图，是反映现实世界中具体事物及其相互关系的一种抽象工具,它比地图、分子结构图、电路图等更抽象。
图的定义：简单的说，一个图是由一些点(Vertices)及点间的连线(Edges)所组成的。点可以作为现实世界中事物的抽象，而点间的连线表示事物间的关系。
无向图：如果一个图由点及边所构成，则称之为无向图，记为G=(V，E)。其中，V是一个有限非空的点集合，称为G的点集，一般表示为V={v1，v2，…，vn}；E是一个边集合，称为G的边集，一条连接vi和vj的边一般表示为一个无序对e=（vi，vj）。
有向图：如果一个图由点及弧所构成，则称之为有向图，记为D＝(V，A)。其中，V是点的集合；A是弧的集合，一条从vi连接到vj的弧一般表示为一个有序对a＝(vi，vj)。

 

 

..............................