grafo denso

En teoría de grafos, la densidad de un grafo es una propiedad que determina la proporción de aristas que posee. Un grafo denso es un grafo en el que el número de aristas es cercano al número máximo de aristas posibles, es decir, a las que tendría si el grafo fuera completo. Al contrario, un grafo disperso es un grafo con un número de aristas muy bajo, es decir, cercano al que tendría si fuera un grafo vacío. La distinción entre grafos dispersos y densos es relativamente vaga. De acuerdo con Preiss,​ dado un grafo , este es denso si , para , y es disperso si la misma igualdad se cumple para , donde refiere a la cota superior asintótica.