FACTOID # 22: South Dakota has the highest employment ratio in America, but the lowest median earnings of full-time male employees.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Graph theory
A drawing of a graph.
A drawing of a graph.

In mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see graph (mathematics) for more detailed definitions and for other variations in the types of graphs that are commonly considered. The graphs studied in graph theory should not be confused with "graphs of functions" and other kinds of graphs. Image File history File links 6n-graf. ... Image File history File links 6n-graf. ... As a branch of graph theory, Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... This article just presents the basic definitions. ... This article presents the essential definitions. ... In mathematics, the graph of a function f is the collection of all ordered pairs (x,f(x)). In particular, graph means the graphical representation of this collection, in the form of a curve or surface, together with axes, etc. ... Look up Graph in Wiktionary, the free dictionary. ...


Please refer to Glossary of graph theory for some basic definitions in graph theory. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ...

Contents

History

The Königsberg Bridge problem.
The Königsberg Bridge problem.

The paper written by Leonhard Euler on the Seven Bridges of Königsberg and published in 1736 is regarded as the first paper in the history of graph theory.[1] 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[2] and L'Huillier,[3] and is at the origin of topology. Image File history File links The seven bridges of Konigsberg - old map with bridges highlighted Public Domain Image, modified by me, released under GPL. File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ... Image File history File links The seven bridges of Konigsberg - old map with bridges highlighted Public Domain Image, modified by me, released under GPL. File history Legend: (cur) = this is the current file, (del) = delete this old version, (rev) = revert to this old version. ... Euler redirects here. ... Map of Königsberg in Eulers time showing the actual layout of the seven bridges, highlighting the river Pregolya and the bridges. ... Events January 26 - Stanislaus I of Poland abdicates his throne. ... Alexandre-Théophile Vandermonde (28 February 1735 -1 January 1796) was a French musician and chemist who worked with Bezout and Lavoisier; his name is now principally associated with determinant theory in mathematics. ... An open knights tour of a chessboard The Knights tour as solved by The Turk, a chess-playing machine hoax. ... Leibniz redirects here. ... Augustin Louis Cauchy (August 21, 1789 – May 23, 1857) was a French mathematician. ... Simon Antoine Jean LHuillier(Geneva, 24 April 1750 - Geneva, 28 March 1840) was a Swiss mathematician of French Hugenot descent. ... A Möbius strip, an object with only one surface and one edge; such shapes are an object of study in topology. ...


More than one century after Euler's paper on the bridges of Königsberg and while Listing introduced topology, Cayley was led by the study of particular analytical forms arising from differential calculus to study a particular class of graphs, the trees. This study had many implications in theoretical chemistry. The involved techniques mainly concerned the enumeration of graphs having particular properties. Enumerative graph theory then rose from the results of Cayley and the fundamental results published by Pólya between 1935 and 1937 and the generalization of these by De Bruijn in 1959. Cayley linked his results on trees with the contemporary studies of chemical composition.[4] The fusion of the ideas coming from mathematics with those coming from chemistry is at the origin of a part of the standard terminology of graph theory. In particular, the term graph was introduced by Sylvester in a paper published in 1878 in Nature.[5] Former German name of the city of Kaliningrad. ... Johann Benedict Listing born July 25, 1808, died December 24, 1882 was a German mathematician, born in Frankfurt, Germany, and died in Göttingen, Germany. ... Arthur Cayley (August 16, 1821 - January 26, 1895) was a British mathematician. ... Differential calculus is the theory of and computations with differentials; see also derivative and calculus. ... A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... For other uses, see Chemistry (disambiguation). ... Graph enumeration is a subject of graph theory that deals with the problems of the following type: find how many non-isomorphic graphs have a given property. ... George Pólya (December 13, 1887 – September 7, 1985, in Hungarian Pólya György) was a Hungarian mathematician. ... 1935 (MCMXXXV) was a common year starting on Tuesday (link will display full calendar). ... Year 1937 (MCMXXXVII) was a common year starting on Friday (link will display the full calendar) of the Gregorian calendar. ... A Dutch mathematician, especially noted for the invention of the de Bruijn Sequence. External links About the de Bruijn sequence ... Year 1959 (MCMLIX) was a common year starting on Thursday (link will display full calendar) of the Gregorian calendar. ... James Joseph Sylvester James Joseph Sylvester (September 3, 1814 London - March 15, 1897 Oxford) was an English mathematician. ... 1878 (MDCCCLXXVIII) was a common year starting on Tuesday (see link for calendar). ... Nature is a prominent scientific journal, first published on 4 November 1869. ...


One of the most famous and productive problems of graph theory is the four color problem: "Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?". This problem remained unsolved for more than a century and the proof given by Kenneth Appel and Wolfgang Haken in 1976[6][7] (determination of 1936 types of configurations of which study is sufficient and checking of the properties of these configurations by computer) did not convince all the community. A simpler proof considering far fewer configurations was given twenty years later by Robertson, Seymour, Sanders and Thomas.[8] ... Kenneth Appel (born 1932) is a mathematician who, in 1976 with colleague Wolfgang Haken at the University of Illinois at Urbana-Champaign, solved one of the most famous problems in mathematics, the four-color theorem. ... Wolfgang Haken (born June 21, 1928) is a mathematician who specialized in topology, in particular 3-manifolds. ... Year 1976 Pick up sticks(MCMLXXVI) was a leap year starting on Thursday (link will display full calendar) of the Gregorian calendar. ... Neil Robertson is a mathematician working mainly in topological graph theory, currently teaching at the Ohio State University. ... This article is about the mathematician. ...


This problem was first posed by Francis Guthrie in 1852 and the first written record of this problem is a letter of De Morgan addressed to Hamilton the same year. Many incorrect proofs have been proposed, including those by Cayley, Kempe, and others. The study and the generalization of this problem by Tait, Heawood, Ramsey and Hadwiger has in particular led to the study of the colorings of the graphs embedded on surfaces with arbitrary genus. Tait's reformulation generated a new class of problems, the factorization problems, particularly studied by Petersen and Kőnig. The works of Ramsey on colorations and more specially the results obtained by Turán in 1941 is at the origin of another branch of graph theory, the extremal graph theory. Example of a four color map The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same colour. ... 1852 was a leap year starting on Thursday (see link for calendar). ... The tone or style of this article or section may not be appropriate for Wikipedia. ... For other persons named William Hamilton, see William Hamilton (disambiguation). ... Sir. ... Peter Tait Peter Guthrie Tait (April 28, 1831 - July 4, 1901) was a Scottish mathematical physicist. ... Percy John Heawood (1861-1955) was a British mathematician. ... Frank Plumpton Ramsey (February 22, 1903 – January 19, 1930) was a British mathematician who, in addition to mathematics, made significant contributions in philosophy and economics. ... Hugo Hadwiger (1908 - 1981) was a Swiss mathematician. ... In mathematics, the genus has few different meanings Topology The genus of a connected, oriented surface is an integer representing the maximum number of cuttings along closed simple curves without rendering the resultant manifold disconnected. ... Julius Peter Christian Petersen (June 16, 1839 - August 5, 1910) was a Danish mathematician. ... Dénes KÅ‘nig Dénes KÅ‘nig, (September 21, 1884 – October 19, 1944), was a Hungarian mathematician who worked in the field of graph theory. ... Paul (Pál) Turán (August 28, 1910–September 26, 1976) was a Hungarian mathematician who made contributions in number theory and group theory. ... For other uses, see 1941 (disambiguation). ... Extremal graph theory is a branch of mathematics. ...


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. The first example of such a use comes from the work of the physicist Gustav Kirchhoff, who published in 1845 his Kirchhoff's circuit laws for calculating the voltage and current in electric circuits. 1860 is the leap year starting on Sunday. ... Year 1930 (MCMXXX) was a common year starting on Wednesday (link will display 1930 calendar) of the Gregorian calendar. ... Kazimierz Kuratowski (born February 2, 1896, Warsaw, died June 18, 1980, Warsaw) was a Polish mathematician. ... Hassler Whitney (23 March 1907 – 10 May 1989) was an American mathematician who was one of the founders of singularity theory, PhB, Yale University, 1928; MusB, 1929; ScD (Honorary), 1947; PhD, Harvard University, under G.D. Birkhoff, 1932. ... Gustav Robert Kirchhof (March 12, 1824 – October 17, 1887) was a German physicist who contributed to the fundamental understanding of electrical circuits, spectroscopy, and the emission of black-body radiation by heated objects. ... 1845 was a common year starting on Wednesday (see link for calendar). ... Not to be confused with Kerckhoffs principle. ... International safety symbol Caution, risk of electric shock (ISO 3864), colloquially known as high voltage symbol. ... In electricity, current refers to electric current, which is the flow of electric charge. ... An electrical network or electrical circuit is an interconnection of analog electrical elements such as resistors, inductors, capacitors, diodes, switches and transistors. ...


The introduction of probabilistic methods in graph theory, especially in the study of Erdős and Rényi of the asymptotic probability of graph connectivity, gave rise to yet another branch, known as random graph theory, which has been a fruitful source of graph-theoretic results. Paul ErdÅ‘s (Hungarian: ErdÅ‘s Pál, in English occasionally Paul Erdos or Paul Erdös, March 26, 1913 – September 20, 1996), was an immensely prolific (and famously eccentric) Hungarian-born mathematician. ... Alfréd Rényi (March 20, 1921 – February 1, 1970) was a Hungarian mathematician who made contributions in combinatorics and graph theory but mostly in probability theory. ... In mathematics, a random graph is a graph that is generated by some random process. ...


Drawing graphs

Main article: Graph drawing

Graphs are represented graphically by drawing a dot for every vertex, and drawing an arc between two vertices if they are connected by an edge. If the graph is directed, the direction is indicated by drawing an arrow. As a branch of graph theory, Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. ...


A graph drawing should not be confused with the graph itself (the abstract, non-graphical structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout. In practice it is often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.


Graph-theoretic data structures

There are different ways to store graphs in a computer system. The data structure used depends on both the graph structure and the algorithm used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for sparse graphs as they have smaller memory requirements. Matrix structures on the other hand provide faster access for some applications but can consume huge amounts of memory . In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. ... A binary tree, a simple type of branching linked data structure. ... Flowcharts are often used to graphically represent algorithms. ... In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ...


List structures

Incidence list 
The edges are represented by an array containing pairs (ordered if directed) of vertices (that the edge connects) and possibly weight and other data.
Adjacency list 
Much like the incidence list, each vertex has a list of which vertices it is adjacent to. This causes redundancy in an undirected graph: for example, if vertices A and B are adjacent, A's adjacency list contains B, while B's list contains A. Adjacency queries are faster, at the cost of extra storage space.

Incidence list is a graph data structure which lists each vertex and its incident edges[1]. The term is also sometimes used in place of adjacency list (for example in [1] and [2]). Example References ^ http://www. ... For the microarray in genetics, see SNP array. ... In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ...

Matrix structures

Incidence matrix 
The graph is represented by a matrix of size |V| (number of vertices) by |E| (number of edges) where the entry [vertex, edge] contains the edge's endpoint data (simplest case: 1 - connected, 0 - not connected).
Adjacency matrix 
This is the n by n matrix A, where n is the number of vertices in the graph. If there is an edge from some vertex x to some vertex y, then the element ax,y is 1 (or in general the number of xy edges), otherwise it is 0. In computing, this matrix makes it easy to find subgraphs, and to reverse a directed graph.
Laplacian matrix or Kirchhoff matrix or Admittance matrix 
This is defined as DA, where D is the diagonal degree matrix. It explicitly contains both adjacency information and degree information.
Distance matrix 
A symmetric n by n matrix D whose element dx,y is the length of a shortest path between x and y; if there is no such path dx,y = infinity. It can be derived from powers of A: d_{x,y}=min{nmid A^n[x,y]ne 0}.

In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. ... In mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied. ... In mathematics and computer science, the adjacency matrix of a finite directed or undirected graph G on n vertices is the n × n matrix where the nondiagonal entry is the number of edges from vertex i to vertex j, and the diagonal entry is either twice the number of loops... In the mathematical field of graph theory the admittance matrix or Laplacian matrix is a matrix representation of a graph. ... In the mathematical field of graph theory the admittance matrix, Kirchhoff matrix, or Laplacian matrix is a matrix representation of a graph. ... In the mathematical field of graph theory the degree matrix is a diagonal matrix which contains information about the degree of each vertex. ... In mathematics, a distance matrix is a matrix (two-dimensional array) containing the distances, taken pairwise, of a set of points. ... In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ...

Problems in graph theory

Enumeration

There is a large literature on graphical enumeration: the problem of counting graphs meeting specified conditions. Some of this work is found in Harary and Palmer (1973). Graph enumeration is a subject of graph theory that deals with the problems of the following type: find how many non-isomorphic graphs have a given property. ...


Subgraphs, induced subgraphs, and minors

A common problem, called the subgraph isomorphism problem, is finding a fixed graph as a subgraph in a given graph. One reason to be interested in such a question is that many graph properties are hereditary for subgraphs, which means that a graph has the property if and only if all subgraphs, or all induced subgraphs, have it too. Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem. In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... In mathematics a graph invariant or graph property is one of the basic properties of graphs studied in graph theory. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

A similar problem is finding induced subgraphs in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example, In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. ... In computational complexity theory, the clique problem is a graph-theoretical NP-complete problem. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ...

Still another such problem, the minor containment problem, is to find a fixed graph as a minor of a given graph. A minor or subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. A famous example: In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ... In mathematics, the independent set problem (IS) is a well-known problem in graph theory and combinatorics. ... In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that results from a subgraph of G by zero or more edge contractions. ... In mathematics a graph invariant or graph property is one of the basic properties of graphs studied in graph theory. ...

Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their point-deleted subgraphs, for example: In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. ... The three cottage problem is a problem in mathematical graph theory: Suppose there are three cottages that each need to be connected to the gas, water, and electric companies. ... In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of distinct vertices. ...

Informally, the reconstruction problem of graph theory is about the following. ...

Graph coloring

Many problems have to do with various ways of coloring graphs, for example: Image:3-colouringEx. ...

Example of a four color map The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same colour. ... In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph. ... In graph theory, the Erdős-Faber-Lovász conjecture (1972) is a very deep problem about the coloring of graphs. ... Proper total coloring of Foster Cage with 6 colors. ... In mathematics, list edge-coloring is a type of graph coloring. ...

Route problems

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). ... The minimum spanning tree of a planar graph. ... Route inspection problem, Chinese postman problem: The Chinese postman problem is to find a shortest closed path (circuit) that goes through all edges of a (connected) undirected graph. ... Map of Königsberg in Eulers time showing the actual layout of the seven bridges, highlighting the river Pregolya and the bridges. ... In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ... The Steiner tree problem is a problem in combinatorial optimization. ... The three cottage problem is a problem in mathematical graph theory: Suppose there are three cottages that each need to be connected to the gas, water, and electric companies. ... The traveling salesman problem (TSP), is a problem in discrete or combinatorial optimization. ...

Network flow

There are numerous problems arising especially from applications that have to do with various notions of flows in networks, for example: In graph theory, a network flow is an assignment of flow to the edges of a directed graph where each edge has a capacity, such that the amount of flow along an edge does not exceed its capacity. ...

The max flow min cut theorem is a statement in optimization theory about maximal flows in flow networks. ...

Visibility graph problems

A visibility graph is a graph of intervisible locations. ...

Covering problems

Covering problems are specific instances of subgraph-finding problems, and they tend to be closely related to the clique problem or the independent set problem. In the mathematical discipline of graph theory a covering for a graph is a set of vertices (or edges) so that the elements of the set are close (adjacent) to all edges (or vertices) of the graph. ... In computational complexity theory, the clique problem is a graph-theoretical NP-complete problem. ... In mathematics, the independent set problem (IS) is a well-known problem in graph theory and combinatorics. ...

The set cover problem (also set covering) is a classical question in computer science and complexity theory. ... In computer science, the vertex cover problem or node cover problem is an NP-complete problem in complexity theory, and was one of Karps 21 NP-complete problems. ...

Applications

Applications of graph theory are primarily, but not exclusively, concerned with labeled graphs and various specializations of these.


Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be represented by graphs. The link structure of a website could be represented by a directed graph: the vertices are the web pages available at the website and a directed edge from page A to page B exists if and only if A contains a link to B. A similar approach can be taken to problems in travel, biology, computer chip design, and many other fields. The development of algorithms to handle graphs is therefore of major interest in computer science. A website (alternatively, Web site or web site) is a collection of Web pages, images, videos or other digital assets that is hosted on one or several Web server(s), usually accessible via the Internet, cell phone or a LAN. A Web page is a document, typically written in HTML... Flowcharts are often used to graphically represent algorithms. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...


A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example if a graph represents a road network, the weights could represent the length of each road. A digraph with weighted edges in the context of graph theory is called a network. One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ... In Graph theory, a digraph with weighted edges is called a network. ...


Networks have many uses in the practical side of graph theory, network analysis (for example, to model and analyze traffic networks). Within network analysis, the definition of the term "network" varies, and may often refer to a simple graph. Network analysis is the analysis of networks through network theory (or more generally graph theory). ...


Many applications of graph theory exist in the form of network analysis. These split broadly into two categories. Firstly, analysis to determine structural properties of a network, such as the distribution of vertex degrees and the diameter of the graph. A vast number of graph measures exist, and the production of useful ones for various domains remains an active area of research. Secondly, analysis to find a measurable quantity within the network, for example, for a transportation network, the level of vehicular flow within any portion of it. Network analysis is the analysis of networks through network theory (or more generally graph theory). ... In the mathematical subfield of graph theory we can define a notion of distance between two vertices in a graph. ... A transportation network is a type of directed, weighted graph or network. ...


Graph theory is also used to study molecules in chemistry and physics. In condensed matter physics, the three dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. For example, Franzblau's shortest-path (SP) rings. 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. For other uses, see Chemistry (disambiguation). ... A magnet levitating above a high-temperature superconductor demonstrates the Meissner effect. ... Condensed matter physics is the field of physics that deals with the macroscopic physical properties of matter. ... For other uses, see Atom (disambiguation). ... Look up bond in Wiktionary, the free dictionary. ... A molecule editor is a computer program for drawing and editing chemical structures. ...


Graph theory is also widely used in sociology as a way, for example, to measure actors' prestige or to explore diffusion mechanisms, notably through the use of social network analysis software. Sociology (from Latin: socius, companion; and the suffix -ology, the study of, from Greek λόγος, lógos, knowledge [1]) is the systematic and scientific study of society, including patterns of social relationships, social action, and culture[2]. Areas studied in sociology can range from the analysis of brief contacts between anonymous... diffusion (disambiguation). ... A social network is a map of the relationships between individuals, indicating the ways in which they are connected through various social familiarities ranging from casual acquaintance to close familial bonds. ...


References

  • Berge, Claude, Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001)
  • Pelle, Stéphane (1996), La Théorie des Graphes, Saint-Mandé: École Nationale des Sciences Géographiques, <http://www.ensg.ign.fr/~spelle/TheorieGraphes.pdf>
  • Chartrand, Gary, Introductory Graph Theory, Dover. ISBN 0-486-24775-9.
  • Biggs, N.; Lloyd, E. & Wilson, R. Graph Theory, 1736-1936 Oxford University Press, 1986
  • Harary, Frank, Graph Theory, Addison-Wesley, Reading, MA, 1969.
  • Harary, Frank, and Palmer, Edgar M., Graphical Enumeration (1973), Academic Press, New York, NY.

Claude Berge (June 5, 1926 – June 30, 2002) was a French mathematician active in discrete mathematics and more specifically combinatorics and graph_theory. ... Frank Harary (March 11, 1921 - January 4, 2005) was a prolific American mathematician, who specialized in graph theory. ... Frank Harary (March 11, 1921 - January 4, 2005) was a prolific American mathematician, who specialized in graph theory. ...

See also

Some of the finite structures considered in graph theory have names, sometimes inspired by the graphs topology, and sometimes after their discoverer. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... This is a list of graph theory topics, by Wikipedia page. ... This is a list of important publications in mathematics, organized by field. ...

Related topics

Algebraic graph theory is a branch of mathematics. ... Elsie the cat is sitting on a mat John F. Sowas conceptual graphs (CGs) are a system of logic based on the existential graphs of Charles Sanders Peirce and the semantic networks of artificial intelligence. ... A binary tree, a simple type of branching linked data structure. ... Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping sets. ... An entitative graph is an element of the graphical syntax for logic that Charles Sanders Peirce developed under the name of qualitative logic in the 1880s, taking the coverage of the formalism only as far as the propositional or sentential aspects of logic are concerned. ... An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote his first paper on graphical logic in 1882 and continued to develop the method until his death in 1914. ... In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes and a set of edges that establish relationships (connections) between the nodes. ... Image:3-colouringEx. ... As a branch of graph theory, Graph drawing applies topology and geometry to derive two- and three-dimensional representations of graphs. ... A logical graph is a special type of graph-theoretic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. ... A graph with 6 vertices (nodes) and 7 edges. ... The null graph or the empty graph is the graph with no points and no lines. ... In mathematics and physics, a quantum graph is a differential or pseudo-differential operator acting on functions defined on a metric graph. ... In mathematics, spectral graph theory is the study of properties of a graph in relationship to the eigenvalues and eigenvectors of its adjacency matrix. ... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors. ... A simple example unordered tree In computer science, a tree is a widely-used data structure that emulates a tree structure with a set of linked nodes. ...

Algorithms

The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). ... Dijkstras algorithm, named after its discoverer, Dutch computer scientist Edsger Dijkstra, is a greedy algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights. ... The Ford-Fulkerson algorithm (named for L. R. Ford, Jr. ... Kruskals algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ... The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. ... Prims algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ...

Subareas

Algebraic graph theory is a branch of mathematics. ... This page meets Wikipedias criteria for speedy deletion. ... Extremal graph theory is a branch of mathematics. ... In mathematics, a random graph is a graph that is generated by some random process. ... In mathematics topological graph theory is a branch of graph theory. ...

Related areas of mathematics

Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... Group theory is that branch of mathematics concerned with the study of groups. ... Trefoil knot, the simplest non-trivial knot. ... Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. ...

Prominent graph theorists

Claude Berge (June 5, 1926 – June 30, 2002) was a French mathematician active in discrete mathematics and more specifically combinatorics and graph_theory. ... Béla Bollobás (born August 3, 1943 in Budapest, Hungary) is a leading Hungarian mathematician who has worked in functional analysis, and now specializes in combinatorics and graph theory. ... Fan Rong K Chung Graham (金芳蓉, pinyin: Jīn Fāngróng) (born October 9, 1949 in Kaohsiung), known professionally as Fan Chung, is a mathematician who works mainly in the areas of spectral graph theory and extremal graph theory (see graph theory for the general article). ... Gabriel Andrew Dirac (1925–1984) was a mathematician. ... Paul Erdős (Hungarian: Erdős Pál, in English occasionally Paul Erdos or Paul Erdös, March 26, 1913 – September 20, 1996), was an immensely prolific (and famously eccentric) Hungarian-born mathematician. ... Euler redirects here. ... Ralph Faudree is a leading mathematician who specializes in combinatorics and graph theory. ... Ronald L. Graham (born October 31, 1935) is a mathematician credited by the American Mathematical Society with being one of the principle architects of the rapid development worldwide of discrete mathematics in recent years[1]. He has done important work in scheduling theory, computational geometry, Ramsey theory, and quasi-randomness. ... Frank Harary (March 11, 1921 - January 4, 2005) was a prolific American mathematician, who specialized in graph theory. ... Percy John Heawood (1861-1955) was a British mathematician. ... Denes König, (September 21, 1884--October 19, 1944), was a Hungarian mathematician who worked in the field of graph theory. ... László Lovász (1948-) is a Hungarian mathematician, known for work in combinatorics, for which he was in 1999 awarded a Wolf Prize. ... Jaroslav Nešetřil. ... Alfréd Rényi (March 20, 1921 – February 1, 1970) was a Hungarian mathematician who made contributions in combinatorics and graph theory but mostly in probability theory. ... This article or section does not adequately cite its references or sources. ... Neil Robertson is a mathematician working mainly in topological graph theory, currently teaching at the Ohio State University. ... This article is about the mathematician. ... Endre Szemerédi (born August 21, 1940) is a Hungarian mathematician, working in the field of combinatorics, currently professor at Rutgers University. ... Carsten Thomassen (b. ... Paul (Pál) Turán (August 28, 1910–September 26, 1976) was a Hungarian mathematician who made contributions in number theory and group theory. ... William Thomas Tutte (May 14, 1917–May 2, 2002) was a British, later Canadian, codebreaker and mathematician. ... Regina Iosifovna Tyshkevich (Russian: ) (b. ...

Notes

  1. ^ Biggs, N.; Lloyd, E. and Wilson, R. (1986). Graph Theory, 1736-1936. Oxford University Press. 
  2. ^ Cauchy, A.L. (1813). "Recherche sur les polyèdres - premier mémoire". Journal de l'Ecole Polytechnique 9 (Cahier 16): 66–86. 
  3. ^ L'Huillier, S.-A.-J. (1861). "Mémoire sur la polyèdrométrie". Annales de Mathématiques 3: 169–189. 
  4. ^ Cayley, A. (1875). "?". Berichte der deutschen Chemischen Gesellschaft 8: 1056–1059. 
  5. ^ Sylvester, J.J. (1878). "Chemistry and Algebra". Nature 17: 284. 
  6. ^ Appel, K. and Haken, W. (1977). "Every planar map is four colorable. Part I. Discharging". Illinois J. Math. 21: 429-490. 
  7. ^ Appel, K. and Haken, W. (1977). "Every planar map is four colorable. Part II. Reducibility". Illinois J. Math. 21: 491-567. 
  8. ^ Robertson, N.; Sanders, D.; Seymour, P. and Thomas, R. (1997). "The four color theorem". Journal of Combinatorial Theory Series B 70: 2-44. 

External links

Online textbooks

Other resources

  • More people and publications at: Graph Theory Resources
  • Graph theory tutorial
  • Image gallery: graphs
  • GraphViz open source software to produce graph images from a description of the graph
  • [1] GUESS Graph Exploration System( Open Source GPL )
  • JGraphT an open source Java graph theory library
  • Boost an open source C++ graph theory library
  • Eric W. Weisstein, Graph Theory at MathWorld.

Visual rendering by Graphviz. ... Dr. Eric W. Weisstein Encyclopedist Dr. Eric W. Weisstein (born March 18, 1969, in Bloomington, Indiana) is a noted encyclopedist in several technical areas of science and mathematics. ... MathWorld is an online mathematics reference work, sponsored by Wolfram Research Inc. ...


  Results from FactBites:
 
Graph Theory (1165 words)
Graph Theory was born to study problems of this type.
These pages are not intended to replace the standard texts in Graph Theory, rather to give a place on the web where some of the basic definitions can be found.
In an undirected graph, this is obviously a metric.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m