资源描述：
《最小生成树在通信网建设中地应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论课程论文设计（论文）题目：Prim算法在通信网络架设中的应用学院名称：通信与信息工程学院学生姓名：专业：学号：填表时间：2014年12月摘要通信网络系统架设属于典型的图论优化问题，针对通信网络系统的特点，抽象问题，简化模型，以通信网络系统架设费用那个最小为优化目标，应用Prim算法进行通信网络系统架设模型研究。首先简述了五个城市之间架设通信网络系统问题，然后应用数学建模知识对隐含在该问题中的图论模型进行了抽象研究，进而构造问题的数学模型，最后应用Prim算法设计了该通信网络系统架设实现流程及相应代码的编写。程序执行结果表明:准确构建了问题的数学模型及
2、应用Prim算确求解了该数学模型；并且权值因子的可变性使得该程序具有较强的通用性，易于在实际中使用。【关键字】：数学建模无向连通图最小生成树Prim算法引言随着数学科学和计算机技术的发展，数学建模知识在各领域中发挥着重要作用，抽象实际问题、建立正确的数学模型已成为解决实际应用问题的关键[1]。通过数学建模，就可以对实际问题进行抽象、简化，确定变量和参数，并应用某些“规律”建立起变量、参数间的确定的数学模型；一个理想的数学模型，它应满足两个条件；一是模型的可靠性，即在允许的误差围，能正确反映所考虑系统相关特性的在联系，反映客观实际；二是模型的可解性，即它易
3、于数学处理和计算[2]。本文主要研究的是架设通信网络系统的费用最小问题，应用数学建模知识，建立相应的数学模型，其中求最小生成树可以通过Prim算法和Kruskal算法，根据本文所要解决问题的特点，主要采用Prim算法[3]。依据算法的基本思想加入了不同的权值，解决不同情况下网络架设的费用最小问题，并编写了相关程序，该程序具有较强的通用性，易于在实际中使用。一、相关知识介绍1.树树包含n（n>=0）个节点。当n=0时表示为空树。其定义如下：T=(D,R)其中，D为树中节点的有限集合，关系R满足一下条件：①有且仅有一个节点k0属于D，它对于关系R来说没有前趋
4、节点，结点k0称作树的根结点。②除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点。③D中可以有多个终端结点。即除根结点无父结点，其余各结点都有一个父结点和n（n>=0）个子结点。2.邻接矩阵图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]， 用来存放顶点的信息和边或弧的信息。是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方
5、阵：①无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。②无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。3.最小生成树在一给定的无向图G=(V,E)中(u,v)代表连接顶点u与顶点v的边(即),而w(u,v)代表此边的权重,若存在T为E的子集（即)且为无循环图，使得的w(T)最小则此T为G的最小生成树。二、提出问题与问题抽象1.提出问题假设在五个城市架设通信网络系统，任意两个城市之间都可直接架设通信网络，最终目标是以最小总费用在五个城市架设通信网络系统。表1为各城市之间的距
6、离，单位为公里。各城市之间架设网络每公里费用为10000元。其中五个城市分别用A、B、C、D、E表示。表1：五城市之间距离关系ABCDEA010122122B0211513C01214D017E02.问题的数学抽象因为任意两个城市之间都可直接架设通信网络，并且网络连接无方向性，所以五个城市之间的连接图如图1可以认为是一个无向连通赋权图G(V,E,W)，其中，V表示顶点集，E表示边集,W表示各边权值，本问题代表为公里数。这样问题就转化为一个图论问题，变为了一个在无向连通赋权图G中求解一棵最小代价生成树问题，该树满足以下条件：①树中任意两点之间至多只有一条边
7、②树中边数等于树的顶点数减一③树中任意去掉一条边，即得一个不连通图④树中各边权值之和是该连通赋权图中所有可能树中各边权值之和最小的。图1：五城市之间连通图3.建立问题求解模型对连通赋权图G（V,E,W）,一般来说，生成树不止一个，因此，最小代价生成树不一定是唯一的。我们的目的是找出一棵关于图G的最小代价生成树。设T(V,E)为G的一棵生成树，其各边加权之和：W(T)=∑W(ei)称为树T的权，找G中树权值最小的生成树T*,T*为G的最小代价生成树。4.数学模型的算法设计基于具有五个顶点的无向连通赋权图G的每个生成树刚好具有四条边，所以问题是用某种方法选择
8、四条边使它们形成G的最小生成树。此处用到了Prim算法[4]。4.1构造最小生成
