Grafo denso

Un grafo denso, en matemáticas, es un grafo en el que el número de aristas está cercano al número de máximo de aristas. Lo opuesto, un grafo con solo algunas aristas, es un grafo disperso.

La distinción entre grafos dispersos y densos es relativamente vaga. Una posibilidad es escoger un número k con 1 < k < 2 y definir grafo disperso un grafo con |E| = O(|V|^k), donde |E| denote el número de aristas, |V| el número de vértices, y la letra O se refiera a la Cota superior asintótica (Preiss, 1998, p. 534).

Para grafos simples no dirigidos se define la densidad de grafo de la siguiente forma:

$D = \frac{2|E|}{|V|\,(|V|-1)}$

El número máximo de aristas es ½ |V| |V−1|, de tal manera que la densidad máxima es 1 (para un grafo completo) y la densidad mínima es de 0 (Coleman y Moré, 1983).

Referencias

• Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Del 29 de septiembre de 2005.
• Coleman, Thomas F.; Moré, Jorge J. (1983), «Estimation of sparse Jacobian matrices and graph coloring Problems», SIAM Journal on Numerical Analysis 20 (1): 187–209 .
• Preiss, Bruno (1998), Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, ISBN 0-471-24134-2

.