 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.

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. ...

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. 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 and L'Huillier, 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. ...

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 (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. ... 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. ...

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.
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. The term is also sometimes used in place of adjacency list (for example in  and ). 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).
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 ) is the systematic and scientific study of society, including patterns of social relationships, social action, and culture. 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. ... 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 »

Share your thoughts, questions and commentary here
Press Releases | Feeds | Contact