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

----------------------------精品word文档 值得下载 值得拥有----------------------------------------------

第七章 图与网络方法建模

　　瑞士数学家欧拉（E.Euler）在研究哥尼斯堡七桥问题的同时开创了图论研究的先河。经过两百多年的发展，尤其是在20世纪中叶以后，伴随着计算机科学的发展，图论也得到迅速发展和广泛应用，内容及其丰富。这里仅介绍图论中的几个最常见问题，主要目的是通过一些例子来阐述它们的应用价值。

§1 消防设施安置
一、 图的几个基本概念
1、图
图是由顶点集，边集以及各顶点和各边之间确定的关联关系组成的一种结构，记作。
例如：

2、 图的矩阵表示
（1）关联矩阵 （为顶点数，为边数），其中

例如：上图的关联矩阵为

（2）邻接矩阵，其中

例如：上图的邻接矩阵为

3、图的最小复盖
是的一个子集，若图的每条边都至少有一个顶点在中，则称是的一个复盖，含顶点数最少的复盖称为最小复盖。最小复盖不一定唯一。
是图的复盖的关联矩阵中的各顶点所对应的行内，每列至少存在一个元素1。从关联矩阵中找最小复盖的方法是：每次取1个数最多的一行，所在，划去该行及该行中1所在的列，直至结束。
二、 应用举例
一个非常简化的居民小区如上图所示，表示街道，表示交叉路口，现计划在某些路口安置消防设施，只有与路口直接相连的街道才能使用它们。为使所有街道必要时都有消防设施可用，同时安置的设施最节省，问题就归结为求图的最小复盖。
（1）中取，划去行和列，得

（2）再取，划去行和列，得

（3）再取，划去行，过程结束。可见只在顶点设置设施最节省。
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------