Dense Graph
A Dense Graph is a Graph with many Graph Edges relative to some expected Graph Edge dispersion metric.
- See: Sparse Graph.
References
2009
- http://en.wikipedia.org/wiki/Dense_graph
- 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 distinction between sparse and dense graphs is rather vague. One possibility is to choose a number [math]\displaystyle{ k }[/math] with [math]\displaystyle{ 1 \lt k \lt 2 }[/math] and to define sparse graph to be a graph with |E| = O(|V|k), where |E| denotes the number of edges, |V| the number of vertices, and the letter O refers to the Big O notation.
For undirected simple graphs, the graph density is defined as: [math]\displaystyle{ D = \frac{2|E|}{|V|\,(|V|-1)} }[/math]
The maximum number of edges is ½ |V| (|V|−1), so the maximal density is 1 (for complete graphs) and the minimal density is 0 .
- 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.