Graph Theory In Algorithm Design

Graph theory is an ancient discipline, and its birth can be traced back to 1736. In the field of discrete mathematics, graph theory has a dominant position. Graph theory has intuitive, clear, problem-solving characteristics and more importantly, the practice of many practical problems can be classified into equivalent graph theory problems. So Graph theory has a wide range of applications, it can be a variety of complex engineering systems and management problems with the "map" to describe, and then mathematically obtain optimal results. Studied in graph theory, "map" is determined by a number of points (called vertices, Vertex) and a number of line segments linking the two vertices (called edges, Edge) form. Vertices are usually used to express things and edges used to indicate the relationship between these things. Vertex position, edge length is irrelevant, when the edges can be set different weights to indicate the strength of the relationship between vertices. Graph theory to solve many engineering problems in algorithm design an effective mathematical model to facilitate calculation and analysis, and computer storage.Algorithm is a series of steps problem-solving collections. Therefore, algorithm design and analysis for problem solving is crucial. As the Discrete Mathematics's important components, graph theory has become an important content of algorithm-designed. Because Graph Theory and algorithm issue has close relationship, "map" for some algorithms provided an intuitive mathematical platform, graph theory also provide a theoretical basis for these Algorithm. In fact, many algorithms problems directly or indirectly have something to do with figure related. For example, NP complete problem have a considerable graph theory issues or with "figure" relevant in part.Based on the above-mentioned advantages of graph theory, thus the related theories of graph theory can be a reference to the algorithm-designed. At the first, we introduce some graph theory, the theory and their applications as well, then analyzed and summarized their strengths and weaknesses, and propose some ways to improve finally to use in cluster.