(definition)
Definition: A graph in which the number of edges is close to the possible number of edges.
Generalization (I am a kind of ...)
graph.
Specialization (... is a kind of me.)
complete graph.
See also sparse graph, adjacency-matrix 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. Bruno Preiss' definition of sparse and dense graphs has problems, but may help. First, for one graph, one can always choose a k. Second a class of graphs might be considered sparse if |E| = O(|V|k) and 2 > k > 1. |E| is the number of edges, and |V| is the number of vertices.
Preiss reference from Andreas Leiser <andreas.leiser@bluewin.ch> 22 December 2003
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 12:27:58 2004.
HTML page formatted Mon Dec 19 14:07:47 2005.
Cite this as:
Paul E. Black, "dense graph", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/densegraph.html
