Directed acyclic graph

A graph with 6 vertices and 7 edges.

Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs). Typically, a graph is depicted as a set of dots (i.e., vertices) connected by lines (i.e., edges).

For more and formal definitions, see Glossary of graph theory and Graph (mathematics).

Depending on the applications, edges may or may not have a direction; edges joining a vertex to itself may or may not be allowed, and vertices and/or edges may be assigned weights, that is, numbers. If the edges have a direction associated with them (indicated by an arrow in the graphical representation) then it is a directed graph, or digraph.

A graph with only one vertex and no edges is the trivial graph or "the dot".

Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be formulated as questions about certain graphs. Various networks are conveniently described by means of graphs. For example, the link structure of Wikipedia could be represented by a directed graph: the vertices are the articles in Wikipedia and there's a directed edge from article A to article B if and only if A contains a link to B. Directed graphs are also used to represent finite state machines. The development of algorithms to handle graphs is therefore of major interest in computer science.

History

Graph problems

• Graph coloring: the four color theorem

• Route problems:
  • Seven bridges of Königsberg
  • Minimum spanning tree
  • Shortest path problem
  • Route inspection problem (also called the "Chinese Postman Problem")
  • Traveling salesman problem

• Network flows:
  • Max flow min cut theorem
• Reconstruction conjecture

• Graph isomorphism problems (Graph matching)
  • Canonical Labeling
  • Subgraph isomorphism and monomorphisms
  • Maximal common subgraph

Important algorithms

• Dijkstra's algorithm
• Kruskal's algorithm
• Nearest neighbour algorithm
• Prim's algorithm

Generalizations

In a hypergraph, an edge can connect more than two vertices.

An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices.

Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs.

In model theory, a graph is just a structure. But in that case, there is no limitation on the number of edges: it can be any cardinal number.

Related areas of mathematics

• Ramsey theory
• Combinatorics

See also

• Ordered tree data structure - DAGs, binary trees and other special forms of graph.
• List of graph theory topics

External links

• Graph theory tutorial
• Graph theory algorithm presentation
• Some graph theory algorithm animations
  • Step through the algorithm to understand it.
• The compendium of algorithm visualisation sites
• A search site for finding algorithm implementations, explanations and animations

Referenced By