Sparse Graph

A Sparse Graph is a Graph with few Graph Edges relative to some expected Graph Edge dispersion metric.

• See: Dense 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 Template:Preiss.
  • 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 .

---