Graf dens

De Viquipèdia
Dreceres ràpides: navegació, cerca

En matemàtiques, un graf dens és un graf en que el nombre d'arestes és pròxim al nombre d'arestes màxim que pot tindre el graf. Per contra, direm que un graf amb poques arestes és un graf dispers.

La distinció entre dispers i dens és una mica vaga. Una possibilitat és elegir un nombre k amb 1 < k < 2 i definir un graf dispers com aquell que |E| = O(|V|k), on |E| és el nombre d'arestes, |V| el nombre de vèrtexs i la lletra O es refereixi a la Cota superior asimptòtica (Preiss 1998, p. 534).

Per a grafs simples i no dirigits, la densitat és definida com:

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

El nombre màxim d'arestes és ½ |V| (|V|−1), per tant, la densitat màxima és 1 (per a grafs complerts, i la mínima és 0 (Coleman & Moré 1983).

Referències[modifica | modifica el codi]

  • 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.
  • Plantilla:Harvard reference.