目 录
1引言 ............................................................................................................................................ 1 2图的连通性 ............................................................................................................................ 1
2.1连通性的几个定义 ............................................................................................................... 1 2.2连通性的几个定理 ............................................................................................................... 4 2.3其他相关的几个概念及理论 ............................................................................................... 6
3图的连通性的几个应用 ................................................................................................. 7
3.1连通性在有线电视网络中的应用 ....................................................................................... 7 3.2连通性在学校的网络中的应用 ......................................................... 错误！未定义书签。 3.3连通性在数学问题中的应用 ............................................................................................. 12
4结论 .......................................................................................................................................... 14 5结束语 .................................................................................................................................... 14 参考文献 ................................................................................................................................... 15 致谢 .............................................................................................................................................. 16
i
图的连通性在实际生活中的应用
Xxxxxx系本xxxxx班 xxxxxx
指导教师： xxxxxxx
摘 要：在有线电视网络应用中，利用图的连通性理论构造了一个容量网络，结合邻接矩阵的相关知识对其点连通度进行求解，从而解决有线电视网络的相关问题，实际上，这是一个无向图点连通性的应用；在学校的网络应用中将测试数据的描述转化为有向图，观察其点的特征，结合实际，利用图论的遍历理论解决学校网络中出现的问题。
关键词：图的连通性，连通度，强连通分量，应用。
Figure connectivity in real life
Xxxxxxxxxxx
Class 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 combined 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 school's transformation in the web application test data for a directed graph, observable characteristics 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.
i
1引言
图论起源于18世纪东普鲁士的柯尼斯堡，距今已有200多年的历史。虽然促使图论产生和发展的是一些数学游戏问题，但如今不仅应用于自然科学，也应用于社会科学。例如其连通性理论广泛应用于电信网络、电力网络、运输能力、开关理论、随机过程、可靠性理论、计算机程序设计、故障诊断、人工智能、印刷电路板设计、情报检索。运筹学、计算机科学和编码理论中的很多问题也都可以转化为图论问题。
图论与数学的其他分支不同，不像群论、拓扑学等其他学科那样有一套完整的理论体系和解决问题的系统方法。如图的连通性所涉及的问题比较广泛，解决问题的方法也是多种多样的，常常是一种问题一种解法，而这些方法之间又缺乏必然联系。
2图的连通性
连通性是图论中很重要的一个概念，在讨论它的实际应用之前，先来介绍连通性的几个定义、定理，以及实际应用中会涉及到的其他几个概念和理论。 2.1连通性的几个定义
定义1 在无向图中，若从顶点?到?有路径，则称顶点?和?是连通（Connected）的。如果无向图G中任意一对顶点都是连通的，则称此图是连通图（Connected Graph）；相反，如果一个无向图不是连通图，则称为非连通图（Disconnected Graph）。
对于一个无向图不是连通的，其极大连通子图称为连通分量（Connected Component，连通分支），连通分支数记为?(G)。这里所谓的极大指的是子图中包含的顶点个数极大。
例如，下图2.11所示的无向图G1就是一个连通图。在图G1，如果去掉边
(2,6)，那么剩下的图就是非连通的了，并且包含两个连通分量，一个是由顶点
1、2、3、4、5组成的连通分量，另一个是由顶点6构成的连通分量。
1