|
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).
| ||||||||
|
| |||||||||
 |
|
| |