图论应用

最小生成树在通信网络架设中的应用

姓 名： XX 学 号： XXXXX 专 业： 信息与通信工程

2013年12月

摘 要

通信网络架设属于典型的图论优化问题，针对通信网络系统的特点，抽象问题，简化模型，以通信网络架设费用最小为优化目标，应用最小生成树进行通信网络架设模型研究。

本文首先首先简述了最小生成树相关理论，然后描述通信网络架设问题，接着应用数学建模知识对隐含在该问题中的图论模型进行抽象分析，进而构造问题的数学模型，最后应用最小生成树理论设计了改通信网络架设的实现流程和相应代码编写。

关键词：最小生成树 通信网络架设 Prim算法

一、最小生成树相关理论

1、图

图是由一个非空的顶点集合、一个边集合和一个描述顶点与边的关系的集合组成。它可以形式化的定义为：

G=

其中，G表示一个图；V(G)为图G的结点集合，V(G)={v1,v2,?,vn}且不为空集；E(G)为G的边集合，E(G)={e1,e2,?,em}，ei={vj,vt}表示结点vj和vt间的无向边，ei=表示由结点vj到vt间的有向边；φ(G)为关联函数，φ(G)：E→V×V。 2、树

树是无圈连通无向图。树中只连有一条边的节点称为树的叶，树中连有多条边的结点称为树的分枝点或内点。如果树T的结点数为n，那么树的边数为n-1。 3、生出树

连通图 G 上的一个子图，该子图连通，无回路且包含图G 的所有节点，称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。 4、最小生成树

对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因此这些生成树的各边权值之和也不一定相同，其中权值最小的生成树被称为该带权连通图的最小生成树。 5、邻接矩阵

表示顶点之间相邻关系的矩阵，本文主要为无向图的邻接矩阵。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。

二、通信网络架设实际问题及分析

某公司规模不断扩大，在全国各地设立了7个分公司，为了提高公司的工作效率使各分公司之间的信息可以更快、更准确的进行交流，该公司决定要在各分公司之间架设通信网络，由于地理位置和距离等其它因素，使各分公司之间架设通信网络的费用不同，公司想使各分公司之间的通信网络畅通并且把架设费用降到最低，那么应该怎样来设计各分公司及总公司间的线路？ 1、确定问题影响元素

由于影响实际问题的因素很多，要解决实际问题就要建立适当层次上的数学

模型，即要把建模对象所涉及的次要因素忽略掉，否则所得模型会因为结构太复杂而失去可解性；同时又不能把与实质相关的因素忽略掉，而造成所得模型因为不能足够正确反映实际情况而失去可靠性。因此需要对实际问题进行抽象、简化，确定变量和参数，并应用某些“规律”建立起变量、参数间确定的数学模型。

架设通信网络所涉及的因素很多，譬如公司员工分布情况、通信网络流量、各地架设费用、路径长度等，而实际要解决的问题是如何架设通信网络达到架设费用最小，因此各地架设费用和路径长度是影响解决本问题的主要因素，人口分布情况、通信网络流量等次要因素均可忽略掉。

事实上，各地架设费用和路径长度可以归结为各城市间总的架设费用，即各地架设费用乘以相应的路径长度。 2、问题的数学抽象

因为任意两个城市之间都可以直接架设通信网络，并且网络连接无方向性，所以七个城市之间的连接图可以认为是一个无向连通加权图，这样问题就转化为一个图论问题。七个城市可以抽象为图的七个顶点，城市间线路架设可以抽象为图中顶点之间的边，而城市间总的线路架设费用则可以抽象为各边上的权值。问题进而转化为一个在无向连通加权图中求解一棵最小代价生成树的问题，该树满足以下条件：

1）树中任意两点之间至多只有一条边； 2）树中边数等于树的顶点数减1；

3）树中任意去掉一条边，就会得到一个不连通图； 4）树中任意添加一条边，就会构成一个回路；

5）树中各边权值之和是该连通加权图中所有可能树中各边权值和中最小的。

考虑实际情况，剔除部分明显花费过大的边，七个城市间架设通信网络抽象如下图所示：

f a 2 1 7 b 3 15 4 c 5 d 8 e 10 g 9 6 16