图论在网络和信息提取中的若干应用

发布时间：2018-01-11 14:42

本文关键词：图论在网络和信息提取中的若干应用　出处：《河北大学》2017年硕士论文　论文类型：学位论文

【摘要】：图论在数学领域中以网络为研究对象。网络是由节点(也称研究对象,或简称对象)和连线构成,表示诸节点及其相互联系,可以用加权图将这些信息直观地表达出来。实际应用中,任何一个包含二元关系的网络都可以用图论来模拟。可以将多维的、复杂的信息变成二维的、有序的、直观的、清晰的两元矩阵。这样就可以将对象以及对象之间的关系进行规范化的、方便快捷的处理。事实上,图论在自然科学、社会科学、军事、交通运输等各个领域都有广泛的应用。图论在交通网络和信息提取中的处理过程,首先将需要处理的网络看作简单图,然后将其中的信息提取出来,构建一个0-1关联矩阵,探索研究发现拟阵中关于二元拟阵的矩阵表示正好对应着现实生活中的这类特殊形式背景。因为信息的储存也是用0-1,于是转化成0-1形式背景,建立概念格信息提取方法。基于用户的所需,借助概念格这种有效的数据挖掘和信息提取工具,对其建格和做出相应的Hasse示图形式,给予用户更加清楚和多方面的选择。本文利用图论有关理论应用于解决网络和信息提取中的若干问题,主要内容如下:1.图论在最短时间路径网络中和货物配送选址网络中的两个应用。一是,以乘坐交通工具所用时间最短,选择最优线路为所研究的问题,给出了出行者对于在多个属性条件限制下的最短路径第k条最短时间路径算法;二是,给出了快递员邮寄货物获得合理配送方案的基于改进的k-means聚类算法的解决方案。2.图论在交通网络中信息提取的应用。根据形式背景的特殊性,找出基于二元拟阵之K_n图的概念格算法。列举生活中的例子,验证了该算法的可行性。
[Abstract]:In the field of mathematics, graph theory takes the network as the research object. The network is composed of nodes (also known as research objects, or simply referred to as objects) and wires, which represent the nodes and their interrelation. In practical applications, any network containing binary relations can be simulated by graph theory. Multidimensional and complex information can be changed into two-dimensional and ordered. Intuitive, clear binary matrix. In this way, objects and their relationships can be standardized, easy to deal with. In fact, graph theory in natural science, social science, military. The processing process of graph theory in traffic network and information extraction takes the network which needs to be processed as a simple graph and then extracts the information from it. By constructing a 0-1 correlation matrix, we find out that the matrix representation of bivariate matroids in matroids corresponds to this kind of special background in real life, because the information is also stored in 0-1. The concept lattice information extraction method is established. Based on the needs of the user, the concept lattice is an effective tool for data mining and information extraction. This paper applies graph theory to solve some problems in network and information extraction. The main contents are as follows: 1. Two applications of graph theory in shortest time path network and cargo distribution location network. In this paper, the algorithm of the shortest path k of the shortest path with multiple attribute constraints is given. Two. This paper presents a solution based on improved k-means clustering algorithm. 2. The application of graph theory in information extraction in transportation network. According to the particularity of formal background. A concept lattice algorithm based on a bivariate matroid is found, and the feasibility of the algorithm is verified by an example in life.
【学位授予单位】：河北大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】