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 Plantilla:Harv.

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 Plantilla:Harv.

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