数学毕业论文范文.doc

《数学毕业论文范文.doc》由会员分享，可在线阅读，更多相关《数学毕业论文范文.doc（21页珍藏版）》请在三一办公上搜索。

1、新疆财经大学本科毕业论文题目： 图论在网络中的应用 学 号： 2007100677 学生姓名： 努尔曼古.吾布利 院 部： 应用数学学院 专 业： 数学与应用数学 年 级： 数学06-2班 指导教师姓名及职称：热西旦.湖加（讲师）完成日期： 2011年 4 月15日 摘要随着高科技时代的到来，图与网络技术的应用越来越广泛。特别是计算机科学和生物信息科学的发展提出了许多新的问题需要用图论方法来解决。现实生活中的许多问题都可以用一个图来表示。例如，用点表示城市，若两个城市之间有一条铁路相连，则在两个点之间连一条边。这样一个交通网络就可以用一个图来表示。同样地，点表示计算机，用边表示两个计算机之间有

2、信息传递，则计算机网络就可以用一个图来表示。类似地，化学中的分子结构，物理学中的电网络，生物信息学中蛋白质之间的相互作用都可以用一个图来表示。更一般地，用点表示物体，两个物体之间存在某种关系，则对应的顶点之间连一条边，所形成的图便表示物体之间的关系。将实际问题用一个图或网络来表示，通过研究图的性质来解决这些问题，这就是图与网络技术，也称为网络分析。在日常生活和生产中许多问题都可以用一个网络来描述。例如，交通网络，计算机网络，工程进度网络，生物信息网络和互联网等。而网络通常可以用一个图来表示。图论方法可用来解决网络优化中的问题，某些特殊的线性规划问题，用图论方法来解决，则会得到一些更有效地算法。

3、本论文主要介绍图和互联网络的基本概念及常用的术语，树在网络中是怎么应用和连通度的应用。关键词：图；互联网络；连通度；拓扑结构目录一、前言1二、图和互联网络的基本定义22.1 图的基本概念22.2 互联网络概念3三、图和网络中常用的术语43.1 子图和子网络43.2 度、路、链和迹63.3 图的邻接矩阵9四、树在网络中的应用9五、连通度及应用125.1 连通度135.2 网络容错性14结束语16参考文献17致谢18一、前言1731年，瑞士数学家L.Euler(欧拉)在他的一篇论文中讨论了格尼斯堡(Konigsherg)七桥问题，由此诞生了一个全新的数学分支图论(Graph Theory)。在经历

4、了200多年的发展之后，图论已经积累了大量的理论和结果，其应用领域也逐步扩大。最初，图论主要用来讨论游戏中遇到的问题；19世纪末期，图论已经用来研究电网络方程组和有机化学中的分子结构；20世纪中叶以后，借助于计算机，图论又用来求解生产管理、军事、交通运输、计算机以及通信网络等领域中的许多离散性问题，同时图论中的一些著名问题也借助于计算机科学、电子学、信息论、控制论、网络理论、社会科学和管理科学等领域中的应用越来越受到人们的重视。实践证明，图论是设计和分析网络的最基本且强有力的数学工具，因为互联网络的拓扑结构就是图。这个事实已被计算机科学家和工程技术人员所接受并广泛应用。日常生活和生产中的许多问

5、题都可以用一个网络来描述。例如，通网络，计算机网络，工程进度网络，生物信息网络和互联网等。而网络通常可以用一个图来表示。图论方法可用来解决网络优化中的问题，也称为图与网络技术。图论的应用非常广泛，不仅局限于数学和计算机科学，因此各专业的学生都应该打下一定的图论基础，这样他们就会多掌握一种强大而灵活的工具来分析的处理自己学科领域中的问题。二、图和互联网络的基本定义用图来表示互联网络拓扑结构这一事实已被计算机科学工作者和工程技术人员广泛接受和运用。而且，在实践上已被证明，图论是设计和分析互联网络拓扑结构的一个非常有用的数学工具。2.1 图的基本概念我们所说的图是由点及点之间的连线组成的有序二元组，

6、其中，是的顶点集，中元素称为的顶点；称为的边集，中元素称为的边。边中的一对顶点称为该边的端点。两个端点落在一个顶点的边称为环。具有相同端点的边称为多重边。不与任何边关联的点称为孤立点。是图中的顶点数目，也称为的阶。是的边数。只有一个点的图称为平凡图。没有任何边的图称为空图，并将空图记为。任何图，若和都是有限的，则称为有限图；否则称为无限图。既没有环，也没有重边的图称为简单图。无环，但允许有多重边的图称为多重图。一个简单图中若任意俩个点之间均有边相连，称这样的图称为完全图。具有个点的完全图记作，其边数有条。设是由个顶点组成的非空集合，是由条弧组成的集，且知中元素是中一个有序元素对，则称和这两个集

7、合构成一个有向图，记为。有向图的边称为有向边，分别称为和为的起点和终点；也称为顶点的出边，或者顶点的入边。设是一个由个顶点组成的非空集合，是一个由条边组成的集合，并且中元素是中的一个无序元素对。则称和这两个集合共同构成一个无向图(也简称为图)，记为。无向图的边有时叫无向边。若两点之间有边相连，则两点称为相邻的；若两个边有一个公共顶点，则两边称为相邻的。一个从图到图的同构是一个双射，它将映射到，将映射到，使得的端点为、的每一条边映射到一条端点为和的边：。这样的双射称为图与图之间的同构。在同构的意义下，阶完全图和完全二部图是唯一的，分别用和表示。2.2 互联网络概念一个系统可以定义为对象或者元件族

8、，它们被相互连接形成具有确定功能或者目的的整体。系统所能实现的功能是由系统中元件所具有的功能和元件的互连方式来决定的。具有多个相互独立的处理器系统称为多处理系统。因此，一个多处理系统可以被认为是包含两个或者两个以上处理器集成的计算机。定语“集成”意味着在执行程序过程中处理器之间的相互合作。由成千上万个处理器组成的多处理系统赤称为超级处理系统，它具有运行并行算法的能力以解决超大规模的实际问题。 系统中元件之间的连接模式称为该系统的互联网络，或者简称为网络。拓扑上讲，一个系统的互联网络本质上刻画了该系统的结构特征。换句话说，系统的互联网络逻辑上指定了该系统中所有元件之间的连接方式。显然，互联网络可

9、以用图来表示。图的顶点表示系统中的元件，图的边表示元件之间的物理连线，其中有向边表示单向通信连线，无向边表示双向通信连线，而关联函数指定了元件之间的连接方式。这样的图称为互联网络拓扑结构，或者简称网络拓扑。例如，以为拓扑结构的互联网络称为全连通网络。图也可以看成是某个互联网络的拓扑结构。从拓扑上讲，图和互联网络是一回事。因此，将网络、元件和连线说成是图、顶点和边，反之亦然。图是有向边的还是无向边的，根据通信连线是单向的还是双向的决定。网络拓扑通常能划分成两个范畴：动态的和静态的。在动态系统中，网络结构随开关元件的类型而变化。在静态系统中，处理器之间的连接是被动的，系统的重构是不可能的，因此网络

10、结构是固定的。三、图和网络中常用的术语3.1 子图和子网络图的子图是一个图，它满足，且中边的端点的分配和中的一样。我们用来表示“包含”。设图是的一个子图，若，则的子图称为支撑子图。设是的一个非空子集，则以作为点集、以两端点均在中的所有边为边集的子图称为由导出的的子图，记为，简称点导出子图。记号表示导出子图。设是的一个非空子集，则以作为边集，以中边的所有端点作为点集的子图称为由导出的的子图，记为，简称边导出子图。记号表示支撑子图。同样地，表示在中添加边集后得到的图。子图被用来表示子网络。如果是互联网络的拓扑结构，那么表示为了改进网络的性能而添加连线集而得到的网络；和分别表示网络包含一个故障点集和

11、故障连线集。本质上讲，互联网络应该包含某些给定类型的子网络。这些因为计算机系统的功能是执行某些算法。算法也可以用图来表示。的顶点表示执行该算法所要求的设备，的边表示这些设备之间的连线。这样的图叫做该算法的通信模式。因此，算法能在计算机系统中执行当且仅当该算法的通信模式同构与的子图。设和是的两个子图。若，则称与不交的。若，则称与边不交的或边不重的。设和是的两个子图。称以为边集，以中边关联的顶点组成的集合为顶点集的图为与的并图，记作。如果和是不交的，有时记为；称以为边集，以中边关联的顶点组成的集合为顶点集的图为与的交图，记作。3.2 度、路、链和迹定义3.1 设为一无向图，称作为边的端点次数之和为

12、的度数，简记为度，记作，在不发生混淆时，简记为。设为有向图，称作为边的始点的次数之和为的出度，记作，简记作。称作为边的终点的次数之和为的入度，记作，简记作，称为的度数，记作。在无向图中，令称，分别为的最大度和最小度。在有向图中，类似可定义最大度和最小度。另外，令分别称为的最大出度，最小出度，最大入度，最小入度。以上记号可分别简记为，。另外，称度数为0的顶点称为孤立点，度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度(奇数)顶点。在图3.1中，(a)的(注意，环提供2度)，是悬挂顶点，是悬挂边。(b)的，(环提供出度1，提供入度1)，。，(在点达到)，(在点达到)

13、，(在点达到)，(在和点达到)。(a)(b)图3.1当图表示互联网络时，顶点的入度和出度分别表示该网络中元件的输入和输出接口数；它是该元件中输入输出(I/O)设备的最大数。定理3.1 设为任意无向图，则证: 中每条边(包括环)均有两个端点，所以在计算中各顶点度数之和时，每条边被它的端点各用了一次，因此，每条边均提供2度，当然，条边共提供度。定理3.2 设为任意有向图，则，且设和是图的两个顶点。中长为的链是顶点。边都不同的链称为迹，点不同的迹称为路。在连接两个顶点和之间的所有路中，长度最短的路称为最短路。中一条路称为无弦路，如果在中任何不相邻的两顶点在中也不相邻。因为最短路中任何不相邻两顶点在中

14、不相邻，所以最短路是无弦路。起点和终点相同的链，迹和路分别称为闭链，回和圈。长为奇数的圈称为奇圈，长为偶数的圈称为偶圈。长为圈称为圈，3圈称为三角形。显然，任何链必含路，任何闭链必含回，任何回必含圈。中最短圈长称为围长，记为。无论是无向图还是有向图，没有强调边的方向。在有向图中，链称为有向链，记为链，如果对每个，是的边，即中所有边的方向与链从到的方向一致的。路是总线网络或者线形陈列网络的拓扑结构。无向圈是环网的拓扑结构；有向圈是单环网的拓扑结构。环网和单环网络是最通用的，最简单的，而且是最有用的互联网络之一。3.3 图的邻接矩阵设是图，它的顶点集。可以用它的邻接矩阵来表示。的邻接矩阵是阶方阵，

15、记为，其中显然，简单图的邻接矩阵是主对角线元素全为0的(0,1)矩阵，无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定是对称的。图的邻接矩阵是图的另一种表示，图正是以这种形式存储于计算机中。它有利于人们借助计算机来获得或者解决有关图论问题，也有利于我们借助代数方法来研究图论。显然，同构的图的邻接矩阵是置换相似的。换句话说，如果和分别是同构的两个图和的邻接矩阵，那么存在置换矩阵使得。正是这个性质，能使人们方便地利用相似的矩阵的不变量，如特征值，特征向量等，来研究图。如果图是正则的，那么是的特征值。四、树在网络中的应用树是图与网络中一个重要的基本概念，它是一类最简单、但又是十分重要的图。一个树是

16、一个连通且无回路的图，每个树至少有两个1度顶点。图的支撑子图称为支撑树，如果它是树。任何连通图必含支撑树。树作为最基本的图论模型被广泛应用于许多方面：信息论，数据结构和分析，算法设计，组合优化，运筹学，电网络理论和网络设计等等。以树为拓扑结构的网络称为树网。树网是最常见的，又是最简单的互联网络，也是最容易建造和扩充的互联网络。树网的重要性和人们对它的青睐是由于它的简单的构造和良好的性质。指定树中的一个顶点称为根，这样的树称为有根树。有根树中的1度点(根除外)称为叶，其余的顶点称为内部点。有根树称为外向树，如果它是有向图并且从根到任何叶的路是一条有向路。有根树中顶点的深度，或者层是从根到该点的路

17、长。所有叶的最大深度称为该有根树的高。图4.1 根在且高为3的2叉外树和完全2叉树有根树称为叉树，如果它的根的顶点度为，其余内部点的顶点度最多为。叉树称为完全叉树，如果它的所有内部点都是度点。图4.1中所示的图是根在，且高为3的2叉外树和完全2叉树。容易计算出高为的完全2叉树有个顶点。2叉树被广泛用于数据结构，因为它易于存储，易于处理，易于找回。在树型数据中，许多运算，比如搜索和存储，能容易地执行。另外，2叉树还用于某些并行结构。正是这些应用，激发了人们大量的研究兴趣，将2叉树嵌入各种各样的互联网络中去。在互联网络中，一个结构能被另一个结构来模拟是重要的。所谓嵌入是一个拓扑结构到另一个拓扑结构

18、的映射，它保留某些被要求的性质。设和是两个给定的图，从到的嵌入是一个从到的同态。从到的同态是一个映射使得对任何，它的象是中一条路。若存在从到的嵌入，则称能被嵌入到，称为客图，称为主图。客图能否被嵌入主图的问题称为图嵌入问题。嵌入是点对点的，如果是单射。人们关心的嵌入问题，大多数是点对点的嵌入问题。网络模拟问题能归结为图的嵌入问题。有许多理由可以说明这样的嵌入是重要的。正如前面所说，算法的通信模式可以用图来表示。因此，算法在系统中的实现是该算法的通信模式在该系统网络中的嵌入。许多多处理系统是为“一般目的”而设计的，这意味着只要时间和空间允许，任何算法如果能给予合适的编码总是可以在系统中执行。存在

19、大量算法，它们能有效地解决某些应用问题，并且为该算法的执行有最好的通信模式。对于这些算法，为达到希望的性能，某些拓扑结构的存在性是一个有意义的因素。因此，对于这些应用，被设计的网络最好能在逻辑上提供一个特殊的拓扑结构以确保该算法有效地执行。另一方面，有些算法只要稍做修改就可以完全适应另外的拓扑结构，即对算法稍加修改就能运行。如果原始算法结构能被嵌入一个新网络，那么这件事情是容易做到的。一个给定的问题，可能有确定的结构，这种结构导致一个特殊的通信模式。嵌入这个结构可以从本质上节省通信时间。在并行处理系统中，组织处理器的计算能被归结为图的嵌入问题。假定某个处理过程能自然地分解成若干个并行处理的过程

20、以及子过程之间的通信，可以得到一个图，图的顶点代表子过程，图的边代表子过程之间的通信。在一个给定的网络中把这些子过程安排到处理器将被归结为图的嵌入问题。另外，存在若干应用也能用图的嵌入来模拟。例如，如果用图来模拟存储表示和数据结构，那么为数据结构寻找有效的存储表示就归结为图的嵌入问题。显然，如果同构与的某个子图，那么和之间的任何同构能被扩充为到的一个嵌入。这种嵌入称为同构嵌入。同构嵌入是最理想的，因为它是点对点的，而且当客图被用来表示一个算法的通信模式时，在主图上运行该算法与客图上运行该算法有相同的速度。在这种情况下，主图能以同样的速度有效地模拟可图。五、连通度及应用在互联网络设计中，最基本的

21、考虑是网络的可靠性。当用图来表示网络的拓扑结构时，网络的可靠性常常用图的连通度和边连通度来度量。5.1 连通度图的一个分离集或点割是一个集合，它使得连通分量多于一个。的连通度，记作，是这样一个顶点集合的大小的最小值，它使得不连通或者只有一个顶点。如果图连通度至少为，则称它是-连通的。非完全图是-连通的当且仅当每个分离集的大小至少为。考虑的一个部分，。分别在和中至少有一个顶点的任意诱导子图都是连通的。因此，的任意分离集包含或。由于或本身也是分离集(或者仅剩下一个顶点)，因此有。的连通度是3；它是1-连通的，2-连通的，3-连通的，但不是4-连通的。顶点数大于2的图的连通度为1，当且仅当它是连通的

22、并且有一个割点。顶点数大于1的图的连通度为0，当且仅当它是不连通的。1-顶点图有不一致性问题；它是连通的，但为了讨论连通度时的一致性，我们令。由边构成的断连通集是一个集合，它使得的连通分量多于一个。如果一个至少有两个顶点的图的每一个断连通集至少含有条边，则称该图是-边连通的。至少有两个顶点的图的边-连通度，记作，是断连通集大小的最小值(这与是使为-边连通图的最大值等价)。5.2 网络容错性在并行处理系统中，为了更快地把一个大数据包从结点传到结点，人们往往首先把该数据包分拆成个小数据包。每个小数据包可以看成是单一的信号，而且有相同的源和目的地。然后，沿着条不同的路同时从传到。为避免信息相互冲突，

23、这条不同的路必须是内点不交的或者是边不交的。的最大值就是或者。利用不交路传输数据不仅缓解了数据拥塞，加快数据传输，而且容许由于故障的出现而引起的数据丢失。任何系统都有两种可能的故障：硬件发生故障和软件出现错误。大部分的硬件故障是由物理原因引起的，比如元件磨损和电磁干扰等。软件错误是属于设计出错而引起的。硬件故障对网络性能的影响可以用数学方法来描述，而软件错误要想用数学方法来描述是困难的。如果超级计算机系统在故障发生时仍具有功能，那么称该系统为容错的系统。有两个基本的功能性准则已引起人们的足够注意。根据第一个准则，系统只要它的网络拓扑结构逻辑上包含某个拓扑结构，那么该系统被认为是有功能。利用这种

24、功能性准则来达到系统容错性的方法是通过系统的冗余元件和重组来实现的。第二个功能性准则，只要网络中任何两个非故障元件之间存在非故障通信路线，就认为该系统具有功能。换句话说，尽管故障出现，但网络的拓扑结构仍保持连通。这种容错模型的大规模超级计算机系统特别适用于运行这样的并行算法，它的性能对网络拓扑结构的微小变化几乎不敏感。但这样的系统一般是容许故障弱化的。如果图表示互联网络的拓扑结构，那么的连通度（或者边）就是导致网络瘫痪的所需的最小元件个数（或者连线条数）。换句话说，网络能容许个元件或者（条连线）同时发生故障，而剩余网络仍能继续保持正常运行。因此，图的连通度和边连通度越高，它所代表的互联网络的可

25、靠性越大。另一方面，如果是正则连通的，那么有最有连通度和最小的边数。因此，正则连通图代表了最经济最可靠的网络拓扑结构。由此可知，连通度和边连通度是网络容错性最重要的确定性度量参数。结束语图论在网络中的应用是非常广泛的，除了上述以外还有网络传输延迟、互联网络的路由选择、容错直径、宽直径、De Brujin 网络、Kautz 网络和双环网络都是利用图论概念的基础上解决的。这篇论文，旨在用图论的语言介绍有关互联网络拓扑结构设计和分析中最基本的问题、概念和已获得的基本结果。由于我的理解范围有限，因此某些定理除了陈述以外还给出了证明，而某些基本的图论结果只做了陈述。毕竟，图论的范围非常广泛，是无限的也是

26、互通的。而我只是以自己所学的范围与所领会的概念只是陈述了它的一小部分，相信它的价值并不只限于此。参考文献1Douglas B.West .图论导引.第2版.李建中,骆吉洲译.北京:机械工业出版社,20062Fred Buckley,Marty Lewinter .图论简明教程.李慧霸,王凤芹译.北京:清华大学出版社,20053E.米涅卡.网络和图的最优化算法.李家滢,赵关旗译.北京:中国铁道出版社,19844离散数学.第2版.耿素云,屈婉玲编著.北京:高等教育出版社,20045运筹学基础及应用.第4版.胡运权编著.北京:高等教育出版社,2004 6运筹学.汤代焱编著.湖南:中南大学出版社,20

27、02 7运筹学.第3版.刁在筠,刘桂真,宿洁,马建华编著.北京:高等教育出版社,2007致谢首先我要向新疆财经大学数学学院的热西旦老师致以深深的谢意。本文是在热西旦老师的悉心指导下完成的。从论文撰写，到完成，每一步都凝聚着热西旦老师的心血。没有热西旦老师给予的悉心指导、无私帮助和严格要求，本人不可能在学业上有所进步，更不可能完成毕业论文。在论文的写作过程中，我深切地感受到导师严谨的科学态度、虚怀若谷的崇高品质、开阔敏锐的学术思维以及求真务实的工作作风，对我来说是一笔宝贵的财富，让我受益终身。在此我谨向尊敬的导师表达我最诚挚的谢意和最崇高的敬意！在论文的协作过程中，我所在的学院新疆财经大学数学与应用数学学院的领导和各位老师给予我大力的支持与热心的帮助。在此我向他们表示深切的谢意！最后再次感谢曾经给予我帮助和关心的善良的人们，让我顺利完成了我的毕业论文！最后我还要感谢数学院和我的母校新疆财经大学四年来对我的栽培。