Graph theory
The graph theory is a subsection of mathematics, which examines the characteristics of graphs and their relations to each other.
Because on the one hand many algorithmic problems can be attributed to graphs and on the other hand the solution more graph-theoreticallyProblems be based on algorithms often, is the graph theory also in computer science, in particular the complexity theory, of great importance. The investigation of graphs is also contents of the Netzwerktheorie.
At first sight the graph theory seems rather an abstractto be and discipline out of touch with reality of mathematics. However a great many everyday problems can actual be modelled by graphs.
Table of contents |
regarded article
in the graph theory is possible a graph a quantity of points (one calls knots or also corners these then), those by lines (so-called. Edges and/or. Elbows) are connected. ThoseForm of the points and lines does not play a role in the graph theory.
One differentiates thereby between:
- as well as finite graph, with those the quantity of the knots and edges is finite and infinite graph, on the this does not apply
- arranged graphs, with those the edges to be arranged know (represented by arrows instead of lines) and nondirectional graph.
More complex graph types are:
- Multi-graphs, with those contrary to simple graph edges between the knots several times to occur may do and
- hypergraphs,those contrary to simple graph edges more than only two knots to connect know.
Depending upon problem definition knots and edges can also with colors (formal with natural numbers) or weights (D. h. rational or real numbers) to be provided. One speaksthen of knot and/or. edge-colored or - graphs weighted.
One finds accurate definitions of the different graph types in the article types of graphs in the graph theory.
fundamental one of terms and problems
the graph theory defines a multiplicity of fundamental terms, of themKnowledge to understand of scientific papers absolutely necessary is. Fortunately the terms are very intuitively designated in the majority, so that one can learn these fast and only occasionally the exact definition must look up. Before the reading large graph-theoretical articletherefore in particular reading the following articles is recommended:
- One finds types of graphs in
- the graph theory neighbourhood and degree
- in graphs of ways, paths, cycles and circles
- in graphs of forests and trees in
the graph theory further one fundamental terms in:
- Representationfrom graphs in the computer
- isomorphism of graph
- operations on graph
- partial graph and Minoren
graph can have different characteristics. So a graph can be coherently , bipartit , planar , Eulerian or hamiltonisch. It can in demand for the existence of special partial graphsor certain parameters will be examined, like for example knot number, edge number, minimum degree, maximum degree, waist width, diameter, knot connection number, edge connection number, chromatic number, stability number or clique number.
The different characteristics can stand to each other in relationship.The relations to examine is a task of the graph theory. For example the knot connection number is ever smaller than the edge connection number, which is again ever smaller than the minimum degree of the regarded graph. In even graphs the colouring number is ever smaller than 5. ThisStatement is well-known also as the four-color set.
Some the enumerated graph characteristics are relatively easily algorithmically assignable, i.e., the appropriate algorithms need in dependence of the size of the graphs only little time, in order to compute the graph characteristic. Other characteristics are practicalalso with computer inseparably.
The most important problems and results of the graph theory are represented in the following articles:
- Mating in graph
- connection of graphs
- of rivers and cuts in networks
- colouring of graph
- run barness of graph
- knot covers,Cliques and stable quantities
of history
the beginnings of the graph theory decrease/go back into the year 1736 . At that time Leonhard Euler published a solution for the Königsberger bridge problem. The question was whether it a Rundgang by the cityKing mountain - today Kaliningrad - gives, each of the seven bridges to that over the river Pregel exactly once used. Euler could indicate a necessary condition for this problem, and answer so the existence in the negative of such Rundganges. A sufficient condition, as well as oneefficient algorithm, which can find such Rundgang in a graph, only 1873 were indicated by Hierholzer. The term graph was mentioned 1878 for the first time by the mathematician Sylvester in the literature and led themselves from the graphic notation of chemical structuresoff (Lit.: Bonchev/Rouvray, 1990) (see also: Cheminformatik).
applications
as described above can be modelled by graph many problems.
Almost classically the task a shortest route between two places is to be found.It can be solved with graphs, in which the road system is modelled suitably as edge-weighted graph and computed in this with the help of the algorithm of Dijkstra efficiently a shortest way.
Similarly, but the determination of a shortest is algorithmically clearly more difficultRound trip (see problem of the commercial traveller), with which all places of a network must be visited once. In graphs, to which between three knots always the triangle inequation applies (for example in Euclidean or rectilinearen graphs; these are in practice quitefrequent cases) can be worked here however with approximation algorithms, which find a round trip, which doubles at the most (MST heuristic) or 1,5-mal (Christofides heuristic) as the shortest round trip are as long.
Prominent also the problem is the countries of a mapto color with as few a colors as possible in such a way that adjacent countries do not receive the same color together. Here the map is likewise translated into a graph and then tried with an algorithm this problem to solve. Similarly as for the problem of theThis problem cannot commercial travellers be solved after today's knowledge conditions with computers starting from a certain size of the map in reasonable time accurately. The problem to color general graphs optimal is considered to that as one of the most difficult problems in the classNP-complete problems at all. Under the condition <math> P \ neq NP< /math> (see P/NP problem) even an approximate solution is not possible up to a constant factor.
visualization
within the range of the Computergrafik is the visualization of graph a challenge. Particularly complexNets become only clear by sophisticated autolayout algorithms. See graph drawing.
literature
magazines
- journal OF graph Theory . Wiley InterScience.
books
- D. Bonchev, I.E. Rouvray: Chemical graph Theory: Introduction and Fundamentals.Gordon and Breach Science Publishers, 1990, ISBN 0-85626-454-7.
- J. Sedlacek: Introduction to the graph theory. B. G. Teubner publishing house company Leipzig, 1968
- M. Nitz: Graph for a risers (round around the house of the Nikolaus). Friedrich Vieweg and. Son, 2004, ISBN 3-528-03215-4.
- R. Diestel: Graph theory. 2. Edition. Springer publishing house, Heidelberg 2000, ISBN 3-540-67656-2 (the book is on-line available and can be downloaded)
- Gritzmann, Peter; Breaking mountain, René: The secret of the shortest way. A mathematical adventure. Berlin, Heidelberg 2003:Springer publishing house. to 2.Auflage, ISBN 3-540-00045-3
see also
Web on the left of
- graph Theory Resources (in English) - a data base of persons and topics from the graph-theoretical research.
- GraphViz (in English) - open SOURCE software for the visualization ofGraph in the DOT format. Supports export after vrml, SVG, png and GIF.
- aiSee (on German) - software for the visualization of graphs in the GDL format. Supports export after SVG, png and HTML (image map).
- VCG (in English) - open SOURCE software for the visualization of graphsin the GDL format; Predecessor of aiSee.
- Further left to the topic „graph Theory “ in the open directory Project