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

图论课程论文设计（论文）题目：Prim算法在通信网络架设中的应用学院名称：通信与信息工程学院学生姓名：专业：学号：填表时间：2014年12月摘要通信网络系统架设属于典型的图论优化问题，针对通信网络系统的特点，抽象问题，简化模型，以通信网络系统架设费用那个最小为优化目标，应用Prim算法进行通信网络系统架设模型研究。首先简述了五个城市之间架设通信网络系统问题，然后应用数学建模知识对隐含在该问题中的图论模型进行了抽象研究，进而构造问题的数学模型，最后应用Prim算法设计了该通信网络系统架设实现流程及相应代码的编写。程序执行结果表明:准确构建了问题的数学模型及应用Prim算法正确求解了该数学模型；并且权值因子的可变性使得该程序具有较强的通用性，易于在实际中使用。【关键字】：数学建模无向连通图最小生成树Prim算法-1-引言随着数学科学和计算机技术的发展，数学建模知识在各领域中发挥着重要作用，抽象实际问题、建立正确的数学模型已成为解决实际应用问题的关键[1]。通过数学建模，就可以对实际问题进行抽象、简化，确定变量和参数，并应用某些“规律”建立起变量、参数间的确定的数学模型；一个理想的数学模型，它应满足两个条件；一是模型的可靠性，即在允许的误差范围内，能正确反映所考虑系统相关特性的内在联系，反映客观实际；二是模型的可解性，即它易于数学处理和计算[2]。本文主要研究的是架设通信网络系统的费用最小问题，应用数学建模知识，建立相应的数学模型，其中求最小生成树可以通过Prim算法和Kruskal算法，根据本文所要解决问题的特点，主要采用Prim算法[3]。依据算法的基本思想加入了不同的权值，解决不同情况下网络架设的费用最小问题，并编写了相关程序，该程序具有较强的通用性，易于在实际中使用。一、相关知识介绍1.树树包含n（n=0）个节点。当n=0时表示为空树。其定义如下：T=(D,R)其中，D为树中节点的有限集合，关系R满足一下条件：①有且仅有一个节点k0属于D，它对于关系R来说没有前趋节点，结点k0称作树的根结点。②除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点。③D中可以有多个终端结点。即除根结点无父结点，其余各结点都有一个父结点和n（n=0）个子结点。2.邻接矩阵-2-图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，用来存放顶点的信息和边或弧的信息。是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：①无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。②无向图的邻接矩阵中第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为各城市之间的距离，单位为公里。各城市之间架设网络每公里费用为10000元。其中五个城市分别用A、B、C、D、E表示。表1：五城市之间距离关系ABCDEA010122122B0211513C01214D017E0-3-2.问题的数学抽象因为任意两个城市之间都可直接架设通信网络，并且网络连接无方向性，所以五个城市之间的连接图如图1可以认为是一个无向连通赋权图G(V,E,W)，其中，V表示顶点集，E表示边集,W表示各边权值，本问题代表为公里数。这样问题就转化为一个图论问题，变为了一个在无向连通赋权图G中求解一棵最小代价生成树问题，该树满足以下条件：①树中任意两点之间至多只有一条边②树中边数等于树的顶点数减一③树中任意去掉一条边，即得一个不连通图④树中各边权值之和是该连通赋权图中所有可能树中各边权值之和最小的。图1：五城市之间连通图3.建立问题求解模型-4-对连通赋权图G（V,E,W）,一般来说，生成树不止一个，因此，最小代价生成树不一定是唯一的。我们的目的是找出一棵关于图G的最小代价生成树。设T(V,E)为G的一棵生成树，其各边加权之和：W(T)=∑W(ei)称为树T的权，找G中树权值最小的生成树T*,T*为G的最小代价生成树。4.数学模型的算法设计基于具有五个顶点的无向连通赋权图G的每个生成树刚好具有四条边，所以问题是用某种方法选择四条边使它们形成G的最小生成树。此处用到了Prim算法[4]。4.1构造最小生成树的Prim算法假设G（V,E,W）为问题中五城市的连通图，顶点集V(A,B,C,D,E)，E为图中所有带权边的集合。设置两个新的集合U和EDGE,其中集合U用于存放G的最小生成树中的顶点，集合EDGE存放G的最小生成树中的边。假设构造最小生成树时，从顶点A出发，令集合U的初值为U｛A｝,集合EDGE的初值为空[5]。Prim算法的基本思想：从所有u∈U,v∈V-U的边中，选取具有最小权值的边（u,v）,将顶点v加入集合U中，将边(u,v)加入集合EDGE中，如此不断重复，直到U=V时，最小生成树构造完毕，这时集合EDGE中包含了最小生成树的所有四条边。三、算法具体实现1.Prim算法实现步骤假设V是图中顶点的集合，E是图中边的集合，EDGE为最小生成树的边的集合，则Prim算法通过以下步骤可以得到最小生成树：a：初始化：U=｛U0｝,EDGE=｛｝。此步骤设立一个只有顶点U0的结点集U和一个空的边集EDGE作为最小生成树的初始形态。b：在所有u∈U,v∈V-U的边(u,v)∈E中，找一条权最小的边(u0,vi),将此边加-5-进集合EDGE=｛(u0,vi)｝中，并将此边的非U中的顶点vi加入U中，U=｛u0，vi｝。c：如果U=V,则算法结束；否则重复步骤2。可以算出当U=V时，步骤2共执行了四次，EDGE中也增加了四条边，这四条边就是所求出的最小生成树的边。2.算法编码实现代码的编写主要通过visualstudio2013编辑器来编写，用到的编程语言为C++。具体细节如下：①首先定义一个5*5的二维数组来存储邻接矩阵值，数组名为value[5][5];定义一个结构体来存储最小生成树中边的信息，结构体定义如下：typedefstructTREE{intfrom;intto;intweight;}Tree;其中结构体中有三个整形的成员变量，from代表最小生成树中某条边的起点，to代表最小生成树中某条边的终点，weight代表最小生成树中某条边的权重。首先初始化一个结构体数组TreeTE[5]，TE[5]用于存储最小生成树中边的信息。②首先假设A为起点，以A为起点，B、C、D、E为终点的边假设为最小权边，将其分别存储在TE[1],TE[2],TE[3],TE[4]。③找出TE[]数组中权值最小的边，然后将其与TE[1]交换数据。④然后假设最小权边的终点为起点，重新比较各边的权重，跟新TE[]数组中的信息。⑤重复步骤③与④，直到找出四条最小权边。具体代码如下：voidCGraphShow::MiniTree_prim()-6-{for(inti=0;iMAX;i++){for(intj=0;jMAX;j++){value[i][j]=((CCTRLDlg*)AfxGetApp()-m_pMainWnd)-value[i][j];}}inti,j,k,m,min,t,w;for(i=1;im_ctrldlg.m_editvalue;i++){TE[i].from=0;TE[i].to=i;TE[i].weight=value[0][i];}for(j=1;jm_ctrldlg.m_editvalue;j++){m=j;min=MAX_VALUE;for(k=j;km_ctrldlg.m_editvalue;k++){if(TE[k].weightmin){min=TE[k].weight;m=k;}}Treetemp;temp=TE[j];TE[j]=TE[m];TE[m]=temp;k=TE[j].to;for(i=j+1;im_ctrldlg.m_editvalue;i++){t=TE[i].to;w=value[k][t];if(wTE[i].weight){TE[i].weight=w;TE[i].from=k;}-7-}}}3.运行结果①构建邻接矩阵见图2图2：邻接矩阵图②画出五个城市之间连接图，见图3-8-图3：连通图③生成最小生成树，见图4图4：最小生成树4．结论通过程序求出的仿真图形我们可以求出最小生成树，所以在五座城市之间架设通信线路费用最少为：Y=(10+12+13+12)*10000=470000元。四、结论本文综合应用数学建模和图论知识，针对通信网络系统架设的特点及优化目标，建立了问题的数学模型，并应用Prim算法求解该数学模型，最后编写相应代码。程序执行结果表明了建立的数学模型的正确性和Prim算法解决架设通信网络系统费用最小问题的有效性；同时也证明了该应用程序具有较强的通用性，可以调整输入的权值以匹配不同的网络架设情况，从而使程序易于在实际中使用。-9-参考文献[1]朱建青.数学建模[M].解放军出版社,,1996.[2]殷剑宏,吴开亚.图论及其算法[M].中国科学技术大学出版杜,2003.[3]徐俊明.图论及其应用[M].中国科学技术大学出版社,2000.[4]宋增民.图论与网络最优化[M].东南大学出版杜,1990.[5]张清华.图论及其应用[M].清华大学出版社,2012.