Dense Graph

From GM-RKB
Jump to navigation Jump to search

A Dense Graph is a Graph with many Graph Edges relative to some expected Graph Edge dispersion metric.



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 .