数学建模案例分析--最优化方法建模1消防设施安置

第七章图与网络方法建模瑞士数学家欧拉（E.Euler）在研究哥尼斯堡七桥问题的同时开创了图论研究的先河。经过两百多年的发展，尤其是在20世纪中叶以后，伴随着计算机科学的发展，图论也得到迅速发展和广泛应用，内容及其丰富。这里仅介绍图论中的几个最常见问题，主要目的是通过一些例子来阐述它们的应用价值。§1消防设施安置一、图的几个基本概念1、图图是由顶点集),,,(21nvvvV，边集),,,(21meeeE以及各顶点和各边之间确定的关联关系组成的一种结构，记作),(EVG。例如：2v1e2e5e1v3v6e5v4e3e7e4v2、图的矩阵表示（1）关联矩阵mnijrR)(（n为顶点数，m为边数），其中否则使存在0,1ijkkijvveVvr例如：上图的关联矩阵为5432111100001001100010011000100110001001vvvvvR1e2e3e4e5e6e7e（2）邻接矩阵nnijaA，其中否则使存在0,1ikjkijvveEea例如：上图的邻接矩阵为543210111010101110101010101010vvvvvA1v2v3v4v5v3、图的最小复盖K是V的一个子集，若图G的每条边都至少有一个顶点在K中，则称K是G的一个复盖，含顶点数最少的复盖称为最小复盖。最小复盖不一定唯一。K是图G的复盖G的关联矩阵R中K的各顶点所对应的行内，每列至少存在一个元素1。从关联矩阵R中找最小复盖的方法是：每次取1个数最多的一行，所在Kvi，划去该行及该行中1所在的列，直至结束。二、应用举例一个非常简化的居民小区如上图所示，721,,,eee表示街道，521,,,vvv表示交叉路口，现计划在某些路口安置消防设施，只有与路口直接相连的街道才能使用它们。为使所有街道必要时都有消防设施可用，同时安置的设施最节省，问题就归结为求图的最小复盖。（1）mnijrR)(中取Kv3，划去3v行和632,,eee列，得54211100101001010011vvvv1e4e5e7e（2）再取Kv5，划去5v行和75,ee列，得421100111vvv1e4e（3）再取Kv1，划去41,ee行，过程结束。可见只在顶点531,,vvv设置设施最节省。