Graf dens

En matemàtiques, un graf dens és un graf en què el nombre d'arestes és pròxim al nombre d'arestes màxim que pot tindre el graf. Per contra, 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 complets), i la mínima és 0 (Coleman & Moré 1983).

Referències

• 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. «Estimation of sparse Jacobian matrices and graph coloring Problems». SIAM Journal on Numerical Analysis, 20, 1983, p. 187–209..
• Plantilla:Harvard reference.