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 con 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:

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

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.
Other Languages
català: Graf dens
English: Dense graph
فارسی: گراف چگال
magyar: Sűrű gráf
한국어: 밀집 그래프
русский: Плотный граф
українська: Щільний граф