运用图论的思想解决通信网中的站址问题.doc

2010届图论论文 题 目: 运用图论的思想解决通信网中的站址问题 院系名称： 通信学院 专业班级： 电子与通信工程8班 学生姓名： 郭鑫 学 号： S100131025 指导教师： 陈六新 教师职称： 教授 2010年12月09日 摘 要 随着科学的发展，由于生产管理、军事、交通运输等方面提出大量实际问题的需要，图论的理论及其应用研究得到飞速发展．各门科学已强烈地显示出数学化的趋势。在无线电网络、程序设计、无线传感网、中继网络资源复用问题等应用领域。本文由图论的基础知识引申到站址问题的建模和设站总代价的计算问题，推导出设站的最优解。 关键词：图论应用 设站问题 最优解 1.绪论 1.1 图论的应用意义 经典的最短路径问题是图论、设站问题中一个重要的研究内容，它不仅可用于解决生产实际中的许多问题，而且还常常作为一个基本工具用于解决其他优化问题。然而，大量现实世界中的网络都具有动态、随机特性，这种网络中两节点问最短路径的定义及其求解方法都不同于传统最短路径问题，对其进行研究具有广泛的实际应用价值和理论研究价值。本文针对动态随机网络最短路径问题进行了较为深入的系统研究。 1.2 图论的起源，发展及其应用 数学是研究现实世界数量关系和空间形式的科学，它具有抽象的概念、严密的逻辑、明确的结论和完整的体系。数学在形成人类理性思维和促进个人智力发展的过程中发挥着独特的、不可替代的作用。数学的应用越来越广泛，正在不断地渗透到社会生活的方方面面，它与计算机技术的结合在许多方面直接为社会创造价值，推动着社会生产力的发展。人们在运用数学过程中，不断地经历直观感知、观察发现、归纳类比、空间想像、抽象概括、符号表示、运算求解、数据处理、演绎证明、反思与建构等思维过程。这不仅能提升人的思维能力同时也是个将数学中常见的数学模型思想、划分思想、集合思想、数形结合思想、函数思想、归纳思想等渗人到各个思想领域的过程。 图论是一门富有趣味性和应用极为广泛的学科，它在化学、生物学、计算科学以及通信网络等方面都有广泛的应用。本文主要研究图的强定向和最优强(K，d)定向以及图论在站址问题中的应用等课题。 1.3 本论文的研究内容及结构安排 本文对通信网中的站址问题做了详细的阐述，并列举了其建模思想。在实际工作中，如何利用数学理论知识来解决各学科的问题，这需要我们将数学思想进行转化和构造。即是进行站址问题的数学建模。 论文的主要研究内容： 站址问题的模型建立； 站址问题的计算分析； 站址问题代价的最优计算； 本文第一章回顾了图论的起源，发展及其应用意义； 第二章介绍了图论的基础知识，为第三章的建模、计算的引申知识点； 第三章为全文的重点，主要分析三个问题站址问题的模型建立，站址问题的计算分析，站址问题代价的最优计算； 第四章对全文做出总结，并展望了建模对应用领域的好处。 2.基本知识简介 图论是研究离散对象二元关系系统的一个数学分支，是一门应用十分广泛的学科，它已广泛地应用在物理学、化学、通讯、管理、电子计算机等各个领域。在实际生活、生产和科学研究中，有很多问题可以用图论的理论和方法来解决。随着科学技术的发展以及电子计算机的出现与广泛应用，图论的理论得到进一步发展。将庞大复杂的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的问题。图论受到数学、工程技术及经营管理等各个方面越来越广泛的重视。为了叙述方便，本章仅简单介绍后面将要用到的图论的一些基本概念。 2.1 图 图G是指一个有序三元组（V(G),E(G), ），其中V(G)是非空的顶点集，E(G)是不与V(G)相交的边集，而是关联函数，它使G的每条边对于与G的无序顶点对(不必相异)。若e是一条边，而u和v是使得的顶点，则称e连接u和v；顶点u和v称为e的端点。某个边的两个端点相同，称该边为环。 2.2 链和圈 若图G的一个点和边的交替序列｛｝满足，则称这个点边序列为一条从到的链，简称。 在链中，若，则称之为圈。 2.3 赋权图 对图G的每条边e，赋以一个实数，称为边e的权。每个边都赋有权的图称为赋权图。若H是赋权图的一个子图，则H的权是指它的各边的权和。 2.4 有向图和弧 由点集V和弧集A组成的图D=(V，A)，其中V是点集，A是弧集。所谓弧就是点与点之间有方向的线，即点集矿的有序偶是弧的起点，而是弧的终点，一般用v记点，用a记弧。 2.5 网络和流 网络N：给一个有向图D=(V