企业运筹学--图与网络理论讲义(ppt 81页)

企业运筹学--图与网络理论讲义目录：
一、图的概念
二、网络概念
三、网络最短树问题
四、网络最短路问题
五、网络最大流问题

 

企业运筹学--图与网络理论讲义内容提要：
图的概念
所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为E，则图可以表示为：G＝（V，E），点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。
在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。
……

在有些图中，边是没有方向的，即[u,v]=[v,u]，这种图称为无向图。
而有些关系是不对称的，例如父子关系、上下级关系、加工工序的先后顺序等都具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为弧。
从顶点u指向υ的弧a，记作＝a=(u,v),(u,v)≠(v,u)，其中u称为a的起点，v称为a的终点，这样的图称为有向图。仍以V表示点的集合，以A表示弧的集合，则有向图表示为D＝（V，A）
……

最短树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最短。
在实际应用中，经常碰到需要求一个赋权连通图的最短树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。
求最短树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为破圈法，一种称为生长法。

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