Dense graph
From Wikipedia, the free encyclopedia
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph.
The graph density is defined as D = |E| / |V|2, where |E| denotes the number of edges and |V| the number of vertices (this definition only works if |V| > 0; we define D to be 0 if the graph has no vertices).
A directed graph can have at most |V| (|V| − 1) edges, so the maximal density is 1. An undirected graph can have at most |V| (|V| − 1) / 2 edges, and the maximal density is 1/2.
The distinction between sparse and dense graphs is rather vague. One possibility is to choose a number k with 1 < k < 2 and to define sparse graph to be a graph with |E| = O(|V|k) (Preiss, 1998, p. 534).
[edit] References
- Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
- Bruno Preiss, Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, 1998. ISBN 0-471-24134-2.
