2375运筹学基础复习资料8

第八章图论方法P150
图的基本概念P150（领会）
图的最基本的要素是：点 、点与点之间的一些连线（简称线或边）通常点表示对象，线表示关系；根据需要，在图的点旁或边旁标上数（称为权），不同的场合，赋予不同的含义
树和树的逐步生成法P151（简单应用）
连通图：所有的点通过相互之间的连线必须连成一片
树：不含圈的连通图，称为树，任一树中的线数必定是它的点数减一
最小枝杈树问题P152（简单应用）
所谓最小枝杈树问题是关于在一个网络中，从一个起点出发一所有接点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度是最小的，或敷设费用最小
有两种方法：普赖姆法、克鲁斯喀尔法（仅适于小的手工计算的网络）
普赖姆法算法：最小枝杈树算法是把最近的未接点连接到那些已接点上去的方法来进行的
最短路线问题P154（简单应用）
当通过网络的各边所需的时间、距离或费用为已知时，找出从入口到出口所需的最少时间，最短距离或最少费用的路径问题，这些问题称做网络的路线问题
方法：从终点开始逐步逆向推算；先看与终点连接的点，在结点上方写上最短路线及权数；
再将每个（每个与终点连接的点）看成新的终点，以此类推
所谓最短路线，即看与此结点连接的箭尾有几条就有几条路线，选其中权值总和最小的一条即可
可应用于公路运输、铁路运输、电缆架设、管道铺设及个人旅行中
最大流量问题P155（简单应用）
当以物体、能量或信息等作为流量流过网络时，怎样使流过网络的流量最大，或使流过网络的流量的费用或时间最小，通常，把设计这样的流量模型问题，叫做网络的流量问题
最大流量问题，就是在一定条件下，要求流过网络的流量为最大的问题
计算方法：
任意选择从起点到终点的第一条路线，找出其流量能力最小的支线，在这条线路的每个结点处标上流量数及路线序数1，例：最小流量为2，第一条路线，则标上   2（1）。然后用最小流量能力来做减数，来减每条支线的流量能力，把差数写在相应的支线的起点结点处，该支线流量能力值的圆括弧内。
另选第二条从起点到终点的路线，按同样方法标注
直到找不到这样的一条路线为止：所有各条支线的流量能力全为正数，但最小的流量能力为0
网络最大流量为，每条线路的最小流量之和
最大流量算法，对规划铁路、公路的运输工作及城市交通流量等，有用处