第六章图与网络规划课件.pptVIP

第六章 图与网络规划 上海工程技术大学——管理学院 图论是应用十分广泛的运筹学分支，它已广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活、生产科学研究中，有很多问题可以用图论的理论和方法来解决。图论的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。我们把图论在系统管理决策中卓有成效的一些理论和方法称之为网络规划。 内容提要 第一节 图的基本概念 第二节 树 第三节 最短路问题 第四节 最大流问题 第五节 最小费用最大流问题 习题 第一节 图论的基本概念 1.1图的导引 在哥尼斯堡城中有一条河叫普雷格尔河，河上有七座桥连接两岸及河中的两个岛（如图6.1所示）。当时困扰当地居民的一个问题是：是否存在一种走法，使走过桥每座桥恰好一次。虽然当时有许多人相信不存在这种走法，但没有人能解释其原因。 图6.1 图6.2 当问题被提到的数学教授Euler面前，它把每块地用一个点代替，把每座桥用连接对应点的一条边代替，把问题抽象为图6.2中的图。提出了判断一般图存在这种走法的充要条件，并给出了必要性的证明。 图的基本概念 1.2基本概念 如果用V点表示研究对象，用E边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作 G={V，E} 边：两点之间的不带箭头的连线； 弧：两点之间带箭头的连线； 无向图：由点和边构成； 有向图：由点和弧构成； 混合图：既有边又有弧的图； 自回路：一条边的两端重合； 定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D，称D为的G定向图；G为D的基本图； 简单图：无平行边的图； 多重图：一个无环但有多重边的图； 完全图：图中任意两个顶点之间恰有一条边相关联； 图的基本概念 权：在图的点或边上表明某种信息的数； 赋权图：每条边都赋上了值； 网络图：给点和边（弧）赋以具体的含义和权数的图； 出度：与顶点相连的边数称为该定点的度数（度数为零的定点称为孤立点，度数为一的点为悬挂点），以该定点为始边的边数为出度； 入度：以该定点为终边的边数为入度； 子图：删去一条边或一点剩下的图。； 生成子图：只删边不删点； 主子图：图中删去一点所得的子图； 连通图：在无向图中如果任意两点是可达的，否则是不连通图； 强连通图：在有向图中如果任意两点是互可达的； 图的基本概念 若存在经过每条边恰好一次的一个圈，则称此图为欧拉圈。若在图中只含有一个欧拉圈，则称此图为欧拉图。 如果图中存在一条通过各个顶点一次且仅一次的回路，则称此回路为图的哈密尔顿回路；具有哈密顿回路的图称为哈密尔顿图。 图6.3（a）、（b）分别是欧拉图和哈密尔图。 （a） （b） 图6.3 第二节 树 在各式各样的图中，有一类图是极其简单然而却是很有用的，这就是树图。树图的定义是无圈的连通图。这类图与大自然中树的特征相似，因而得名树图。管理组织机构、学科分类和一些决策过程往往都可以用树图的形式表示。 举一个现实生活中的例子，五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话，并且电话线的根数最少。 用五个点代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间连一条边，这样一个电话线网就可以用一个图来表示了。为了使任何两个城市都可以通话，这样的图必须使连通的。其次，若图中由圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一条电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.4代表了满足要求的一个电话线网。 树 图6.4 2.1基本概念 树——无回路且连通的无向图G称为树，树中的边