(definition)
Definition: A graph in which the number of edges is much less than the possible number of edges.
Generalization (I am a kind of ...)
graph.
See also dense graph, complete graph, adjacency-list representation.
Note: A directed graph can have at most n(n-1) edges, where n is the number of vertices. An undirected graph can have at most n(n-1)/2 edges.
There is no strict distinction between sparse and dense graphs. Typically, a sparse (connected) graph has about as many edges as vertices, and a dense graph has nearly the maximum number of edges.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 2 December 2019.
HTML page formatted Mon Dec 2 09:10:23 2019.
Cite this as:
Paul E. Black, "sparse graph", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 2 December 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/sparsegraph.html