《毕业论文--图的连通性在实际生活中的应用》由会员分享，可在线阅读，更多相关《毕业论文--图的连通性在实际生活中的应用（18页珍藏版）》请在金锄头文库上搜索。
1、目 录1引言12图的连通性12.1连通性的几个定义12.2连通性的几个定理42.3其他相关的几个概念及理论63图的连通性的几个应用73.1连通性在有线电视网络中的应用73.2连通性在学校的网络中的应用103.3连通性在数学问题中的应用124结论145结束语14参考文献15致谢1616图的连通性在实际生活中的应用Xxxxxx系本xxxxx班 xxxxxx指导教师： xxxxxxx 摘 要：在有线电视网络应用中，利用图的连通性理论构造了一个容量网络，结合邻接矩阵的相关知识对其点连通度进行求解，从而解决有线电视网络的相关问题，实际上，这是一个无向图点连通性的应用；在学校的网络应用中将测试数据的描述转
2、化为有向图，观察其点的特征，结合实际，利用图论的遍历理论解决学校网络中出现的问题。关键词：图的连通性，连通度，强连通分量，应用。Figure connectivity in real lifeXxxxxxxxxxxClass xxxx,Department of Mathematics Tutor:xxxxxxxxxx Abstract: In the cable network applications, use graph theory to construct a connectivity capacity of the network, adjacency matrix combine
3、d knowledge to solve their point connectivity, thereby solving issues related to cable television networks, in fact, this is an undirected graph point connectivity applications; In the description of the schools transformation in the web application test data for a directed graph, observable charact
4、eristics of its points, with reality, school networks to solve the problems in graph theory of ergodic theory. Key words: figure connectivity, connectivity, strongly connected components.1引言图论起源于18世纪东普鲁士的柯尼斯堡，距今已有200多年的历史。虽然促使图论产生和发展的是一些数学游戏问题，但如今不仅应用于自然科学，也应用于社会科学。例如其连通性理论广泛应用于电信网络、电力网络、运输能力、开关理论、随
5、机过程、可靠性理论、计算机程序设计、故障诊断、人工智能、印刷电路板设计、情报检索。运筹学、计算机科学和编码理论中的很多问题也都可以转化为图论问题。图论与数学的其他分支不同，不像群论、拓扑学等其他学科那样有一套完整的理论体系和解决问题的系统方法。如图的连通性所涉及的问题比较广泛，解决问题的方法也是多种多样的，常常是一种问题一种解法，而这些方法之间又缺乏必然联系。2图的连通性连通性是图论中很重要的一个概念，在讨论它的实际应用之前，先来介绍连通性的几个定义、定理，以及实际应用中会涉及到的其他几个概念和理论。2.1连通性的几个定义定义1 在无向图中，若从顶点到有路径，则称顶点和是连通（Connecte
6、d）的。如果无向图中任意一对顶点都是连通的，则称此图是连通图（Connected Graph）；相反，如果一个无向图不是连通图，则称为非连通图（Disconnected Graph）。对于一个无向图不是连通的，其极大连通子图称为连通分量（Connected Component，连通分支），连通分支数记为。这里所谓的极大指的是子图中包含的顶点个数极大。例如，下图所示的无向图就是一个连通图。在图，如果去掉边，那么剩下的图就是非连通的了，并且包含两个连通分量，一个是由顶点组成的连通分量，另一个是由顶点构成的连通分量。 尽管有些无向图都属于连通图，其中会有某些图看起来比其他图“更为连通”，相反某些连通
7、图的连通性会相对“脆弱”，以至于移去某个顶点或某条边就导致图不连通。这时也就需要一些能反映无向连通图连通程度的量，即顶点连通度与边连通度。下面就来介绍这几个定义。定义2 无向图的点连通性：所谓点连通性（Vertex Connectivity），就是与顶点有关的连通性。研究无向图的点连通性，通常是通过删除无向图中的顶点（及与其所关联的每条边）后，观察和分析剩下的无向图连通与否。设连通图的阶数为，去掉的任意个顶点（及相关联的边）后，所得到的子图仍然连通，而去掉某个顶点（及所关联的边）后的子图不连通，则称是-连通图，称作图的顶点连通度，记做.如果割顶集中只有一个顶点，则该顶点可以称为割点（Cut-V
8、ertex）或关节点。规定，对阶完全图，；对非连通图和平凡图，.定义3 点双连通图：如果一个无向连通图没有关节点，或者说点连通度，则称为点双连通图，或者称为重连通图。定义4 点双连通分量：一个连通图如果不是点双连通图，那么它可以包括几个点双连通分量，也称为重连通分量（或块）。一个连通图的重连通分量是该图的极大重连通子图，在重连通分量中不存在关节点。定义5 无向图的边连通性：所谓边连通性（Edge Connectivity），就是与边有关的连通性。研究无向图的边连通性，通常是通过删除无向图中的若干条边后，观察和分析剩下的无向图连通与否。设连通图的边数为，去掉的任意条边后，所得到的子图仍然连通，而
9、去掉某条边后得到的子图不连通，则称是-边连通图，称作图的边连通度，记作.如果割边集中只有一条边，则该边可以称为割边（Bridge）或桥。定义6 边双连通图：如果一个无向连通图没有割边，或者说边连通度，则称为边双连通图。定义7 边双连通分量：一个连通图如果不是边双连通图，那么它可以包括几个边双连通分量。一个连通图的边双连通分量是该图的极大重连通子图，在边双连通分量中不存在割边。在连通图中，把割边删除，则连通图变成了多个连通分量，每个连通分量就是一个边双连通分量。上述几个定义都是无向图的重要内容，在实际应用中不会再专门提到定义的相关内容，但应用中解决问题的算法与定义息息相关。下面再介绍几个有向图的
10、相关定义。定义8 强连通（Strongly Connected）：若是有向图，如果对图中任意两个顶点和，既存在从到的路径，也存在从到的路径，则称该有向图为强连通有向图，即强连通图（Strongly Connected Digraph）。 例如，图所示的有向图就是一个强连通图。 对于非强连通图，其极大强连通子图称为其强连通分量（Strongly Connected Component）。例如，图所示的有向图就是一个非强连通图，它包含个强连通分量，在图可以看出来。其中，顶点构成一个 有向图的强连通分量强连通分量，在这个子图中，每一对顶点和，既存在从到的路径，也存在从到的路径；顶点也构成一个强连通分
11、量，顶点则自成一个强连通分量。 定义9 单连通（Simply Connected）：若是有向图，如果对图中任意两个顶点和，存在从到的路径或从到的路径，则称该有向图为单连通有向图。定义10 弱连通（Weak Connected）：若是有向图，如果忽略图中每条有向边的方向，得到的无向图（即有向图的基图）连通，则称该有向图为弱连通有向图。2.2连通性的几个定理 连通性的相关定理并不是很多，每个定理都涉及到连通性应用中算术求解的问题，如下面这个Menger定理，涉及到的就是无向图顶点连通度的求解。定理1 （Menger定理）无向图的顶点连通度和顶点间最大独立轨数目之间存在如下关系式： 这个定理中涉及到
12、最大独立轨，下面来介绍一下独立轨的概念。 无向图中的独立轨设是无向图的两个顶点，从到的两条没有公共内部顶点的路径，互称为独立轨。到独立轨的最大条数，记作.例如，在图中所示的无向图中，和之间有条独立轨，图中用粗线标出来了。 定理2 （顶点连通度、边连通度与图的最小度的关系） 设为无向连通图，则存在关系式：.其中，.这个无向图形式是由Whitney（1932）首次发现，因此在文献中通常称为Whitney不等式。定理3 对任何简单平面图均有.如下图所示的图有，和.事实上，对任何个正整数均存在无向图使，且.这里要注意，考虑的对称有向图，即知也存在满足上述条件的有向图。 定理4（Whitney，1932
13、） 设并且设是阶有向图，则（i） （ii） .定理5 设是强连通有向图，则（i） ， ；（ii） .上述的几个定理并没有涵盖连通性的所有定理，只是再接下来的应用中会用到的定理，解决实际问题的过程中不会再次强调定理的内容，但是过程中的求解计算以及得出结论都是基于以上的定义和定理的。另外，在解决实际问题时还会用到几个其他的概念和理论，下面简单介绍一下。2.3其他相关的几个概念及理论在下文的应用中会用到遍历这个概念。所谓图的遍历（Graph Traversal）,也称为搜索（Search），就是从图中某个顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次。遍历可以采取两种方法进行：深度
14、优先搜索和广度优先搜索。两种搜索需要计算机来实现，本文暂不涉及。遍历是很多图论算法的基础，下文中连通性在学校的网络的应用会涉及遍历理论。在解决实际问题中会常用矩阵，矩阵式研究图论的一种有力工具，特别是利用计算机来研究有关图的算法时，首先遇到的问题就是如何让计算机能够识别？利用矩阵识别就是一种很好的方法。我们所讨论的图都假定两顶点之间不存在自环和平行的两条边。如不特别说明，一般是指无向图。这视为一种约定。对于图，构造一矩阵，其中 则称矩阵是图的邻接矩阵。如果给出了图的邻接矩阵，就等于给出了图的全部信息。图的性质就可以从矩阵通过运算而获得。邻接矩阵在连通性的实际应用中的非常重要，很多实际问题都需要转化为图模型，然后再用邻接矩阵表示和计算。3图的连通性的几个应用 图论是六、七十年代发展比较迅速的数学分支，那时在电路网络的研究方面的应用非常成功。特别是随着科学技术的发展，实际应用的问题越来越复杂，其计算更多依赖于计算机，图的连通性在其中扮演着重要的角色。下面介绍的几个简单应用是图的连通性结合时代气息解决实际问题的例子。3.1连通性在有线电视网络中的应用有线电视网络中，中继器的连接是双向的。如果网络中任何两个中继器之间至少有一条路，则中继器网络称为是连通的，否则
