线性规划-图与网络分析

《线性规划-图与网络分析》由会员分享，可在线阅读，更多相关《线性规划-图与网络分析（93页珍藏版）》请在文档大全上搜索。

1、图与网络是专门研究图的理论图与网络是专门研究图的理论 图论中的图是用点和边（弧）来反图论中的图是用点和边（弧）来反映系统中各对象之间相互关联的关系，映系统中各对象之间相互关联的关系，它与几何图、工程图是不一样的，图中它与几何图、工程图是不一样的，图中点的相对位置、点与点之间连线的长短点的相对位置、点与点之间连线的长短曲直，对于反映对象之间的关系并不是曲直，对于反映对象之间的关系并不是重要的。重要的。 简单图与多重图例：5、路：简单路（边不同）；、路：简单路（边不同）； 初等路（点也不同）初等路（点也不同）. 圈（回路）：圈（回路）：连通图与非连通图连通图与非连通图（1）指边或弧的有关数量指标。

2、根据实指边或弧的有关数量指标。根据实 际背景可赋予不同含义，如距离、时间、际背景可赋予不同含义，如距离、时间、 费用、容量等。费用、容量等。（3）指定了指定了的的的的 。包括无向网络、有向网络、混合。包括无向网络、有向网络、混合 网络。网络。（2）图图G中点、边中点、边(弧弧) 以及边（弧）上的以及边（弧）上的 权的总体，称为赋权图。权的总体，称为赋权图。(1) 、权矩阵(2)、关联矩阵(3)、相邻矩阵V3V4V6无向图有向图V4连通图连通图树树练习题练习题1：下图中：下图中1表示某生产队的水源地，表示某生产队的水源地，其它图形表示水稻田，用堤埂分割为很多小其它图形表示水稻田，用堤埂分割为很多

3、小块。为了用水灌溉，需要挖开一些堤埂。问块。为了用水灌溉，需要挖开一些堤埂。问最少挖开多少堤埂，才能使水浇灌到每小块最少挖开多少堤埂，才能使水浇灌到每小块稻田。稻田。 123456789101112将水源地及每小块稻田各用一个点来表示，边表示它们之间有堤埂相连，那么连接这些点的树图的边数即为至少要挖开的堤埂数。在任一图G=（V，E）中，当点集V确定后，树图是G中边数最少的连通图。练习题2：如图所示，有一菜园被田埂分割为6块，现菜园各块均灌溉了水，问至少需要打通多少田埂才能把所有的水排放掉？ 若将树作为图的一个子图来考虑若将树作为图的一个子图来考虑例：连通图G支撑子图1是一个树支撑子图2是一个树

4、支撑子图3是一个树支撑子图4是一个树支撑子图5是一个树TijwTWmin*)(步骤：步骤：1、先任取一个圈，从圈中去掉一条权最大的边，若在同一个、先任取一个圈，从圈中去掉一条权最大的边，若在同一个圈中有几条都是权最大边，则任选其中的一条边去掉。圈中有几条都是权最大边，则任选其中的一条边去掉。2、在余下的子图中，重复上述步骤，直至没有圈为止。、在余下的子图中，重复上述步骤，直至没有圈为止。避圈法：开始选一条最小权的边，在以后的每一步中，避圈法：开始选一条最小权的边，在以后的每一步中，总从未被选取的边中选一条权最小的边，并使之与已总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈，如果