Graph theory

comprising: To avoid ambiguity, this type of object may be called precisely an undirected simple graph.

comprising: To avoid ambiguity, this type of object may be called precisely a directed simple graph.

In one more general sense of the term allowing multiple edges,[5] a directed graph is an ordered triple

Graphs can be used to model many types of relations and processes in physical, biological,[7][8] social and information systems.

A similar approach can be taken to problems in social media,[10] travel, biology, computer chip design, mapping the progression of neuro-degenerative diseases,[11][12] and many other fields.

Graph-theoretic methods, in various forms, have proven particularly useful in linguistics, since natural language often lends itself well to discrete structure.

Indeed, the usefulness of this area of mathematics to linguistics has borne organizations such as TextGraphs, as well as various 'Net' projects, such as WordNet, VerbNet, and others.

Also, "the Feynman graphs and rules of calculation summarize quantum field theory in a form in close contact with the experimental numbers one wants to understand.

"[13] In chemistry a graph makes a natural model for a molecule, where vertices represent atoms and edges bonds.

This approach is especially used in computer processing of molecular structures, ranging from chemical editors to database searching.

Graphs and networks are excellent models to study and understand phase transitions and critical phenomena.

This information is important when looking at breeding patterns or tracking the spread of disease, parasites or how changes to the movement can affect other species.

Graphs are also commonly used in molecular biology and genomics to model and analyse datasets with complex relationships.

[18] Evolutionary trees, ecological networks, and hierarchical clustering of gene expression patterns are also represented as graph structures.

There may be several weights associated with each edge, including distance (as in the previous example), travel time, or monetary cost.

Such weighted graphs are commonly used to program GPS's, and travel-planning search engines that compare flight times and costs.

[20] This paper, as well as the one written by Vandermonde on the knight problem, carried on with the analysis situs initiated by Leibniz.

Euler's formula relating the number of edges, vertices, and faces of a convex polyhedron was studied and generalized by Cauchy[21] and L'Huilier,[22] and represents the beginning of the branch of mathematics known as topology.

More than one century after Euler's paper on the bridges of Königsberg and while Listing was introducing the concept of topology, Cayley was led by an interest in particular analytical forms arising from differential calculus to study a particular class of graphs, the trees.

[24] The fusion of ideas from mathematics with those from chemistry began what has become part of the standard terminology of graph theory.

[26] Another book by Frank Harary, published in 1969, was "considered the world over to be the definitive textbook on the subject",[27] and enabled mathematicians, chemists, electrical engineers and social scientists to talk to each other.

This problem was first posed by Francis Guthrie in 1852 and its first written record is in a letter of De Morgan addressed to Hamilton the same year.

[29] A computer-aided proof produced in 1976 by Kenneth Appel and Wolfgang Haken makes fundamental use of the notion of "discharging" developed by Heesch.

[30][31] The proof involved checking the properties of 1,936 configurations by computer, and was not fully accepted at the time due to its complexity.

[32] The autonomous development of topology from 1860 and 1930 fertilized graph theory back through the works of Jordan, Kuratowski and Whitney.

Another important factor of common development of graph theory and topology came from the use of the techniques of modern algebra.

Matrix structures on the other hand provide faster access for some applications but can consume huge amounts of memory.

Implementations of sparse matrix structures that are efficient on modern parallel computer architectures are an object of current investigation.

For constraint frameworks which are strictly compositional, graph unification is the sufficient satisfiability and combination function.

Well-known applications include automatic theorem proving and modeling the elaboration of linguistic structure.