(data structure)

**Definition:**
A set of items connected by *edges*. Each item is called a *vertex* or *node*. Formally, a graph is a *set* of vertices and a *binary relation* between vertices, adjacency.

**Formal Definition:** A graph G can be defined as a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {(u,v) | u, v ∈ V}. If the graph is undirected, the adjacency relation defined by the edges is *symmetric*, or E ⊆ {{u,v} | u, v ∈ V} (sets of vertices rather than ordered pairs). If the graph does not allow *self-loops*, adjacency is *irreflexive*.

**Specialization** (... is a kind of me.)

*directed graph*, *undirected graph*, *acyclic graph*, *directed acyclic graph*, *planar graph*, *connected graph*, *biconnected graph*, *bipartite graph*, *complete graph*, *dense graph*, *sparse graph*, *hypergraph*, *multigraph*, *labeled graph*, *weighted graph*, *tree*.

**Aggregate child** (... is a part of or used in me.)

*vertex*, *edge*, Implementations: *adjacency-list representation*, *adjacency-matrix representation*.

**See also**
Relations between vertices: *adjacent*, *self-loop*, Relations between graphs: *isomorphic*, *homeomorphic*, *dual*, *subgraph*, Properties: *diameter*, *degree*, Other: *graph drawing*, *graph partition*.

*Note:
Graphs are so general that many other data structures, such as trees, are just special kinds of graphs. *

A graph is like a road map. Cities are vertices. Roads from city to city are edges. (How about junctions or branches in a road? You could consider junctions to be vertices, too. If you don't want to count them as vertices, a road may connect more than two cities. So strictly speaking you have *hyperedges* in a *hypergraph*. If you want to allow more than one road between each pair of cities, you have a *multigraph*, instead. It all depends on how you want to define it.)

* Another way to think of a graph is as a bunch of dots connected by lines. Because mathematicians stopped talking to regular people long ago, the dots in a graph are called vertices, and the lines that connect the dots are called edges. The important things are edges and the vertices: the dots and the connections between them. The actual position of a given dot or the length or straightness of a given line isn't at issue. Thus the dots can be anywhere, and the lines that join them are infinitely stretchy. Moreover, a mathematical graph is not a comparison chart, nor a diagram with an x- and y-axis, nor a squiggly line on a stock report. A graph is simply dots and lines between them---pardon me, vertices and edges. Michael Bolton <mb@michaelbolton.net> 22 February 2000*

Journal of Combinatorics dynamic surveys DS8 and DS9 are a bibliography and glossary of graphs. **Deepayan Chakrabarti** and **Christos Faloutsos**, *Graph Mining: Laws, Generators, and Algorithms*, ACM Computing Surveys, Vol. 38, March 2006, Article 2.

A great list of graph generators and their strengths and weaknesses.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 16 July 2012.

HTML page formatted Mon Jul 16 09:56:13 2012.

Cite this as:

Paul E. Black and Paul J. Tanenbaum, "graph", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 16 July 2012. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/graph.html