(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 (DS8) and glossary (DS9) 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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 13 April 2015.
HTML page formatted Mon Apr 13 11:42:33 2015.
Cite this as:
Paul E. Black and Paul J. Tanenbaum, "graph", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 13 April 2015. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/graph.html