Gráfico denso
En matemáticas , un gráfico denso es un gráfico en el que el número de aristas está cerca del número máximo de aristas. Lo contrario, un gráfico con solo unos pocos bordes, es un gráfico disperso . La distinción entre gráficos dispersos y densos es bastante vaga y depende del contexto.
La densidad de gráfico de gráficos simples se define como la relación entre el número de bordes con respecto al máximo de bordes posibles.
Para gráficos simples dirigidos , los bordes máximos posibles son el doble que los gráficos no dirigidos para tener en cuenta la dirección, por lo que la densidad es:
donde E es el número de aristas y V es el número de vértices en el gráfico. El número máximo de aristas para un gráfico no dirigido es , por lo que la densidad máxima es 1 (para gráficos completos ) y la densidad mínima es 0 ( Coleman y Moré 1983 ).
La densidad superior es una extensión del concepto de densidad de gráficos definido anteriormente desde gráficos finitos hasta gráficos infinitos. Intuitivamente, un grafo infinito tiene subgrafos finitos arbitrariamente grandes con cualquier densidad menor que su densidad superior, y no tiene subgrafos finitos arbitrariamente grandes con densidad mayor que su densidad superior. Formalmente, la densidad superior de un gráfico G es el mínimo de los valores α de modo que los subgráficos finitos de G con densidad α tienen un número limitado de vértices. Se puede demostrar usando el teorema de Erdős de Piedra que la densidad superior sólo puede ser 1 o una de las relaciones de superparticular 0, 1 / 2 , 2 /3 , 3/4 , 4/5 , ... n / n + 1 , ... (ver, por ejemplo, Diestel, edición 5 , p. 189).
Lee y Streinu (2008) y Streinu y Theran (2009) definen un grafo como ( k , l ) -espacio si cada subgrafo no vacío con n vértices tiene como máximo kn - l aristas, y ( k , l ) - apretado si es ( k , l ) -sparse y tiene exactamente kn - l bordes. Por lo tanto, los árboles son exactamente los gráficos ajustados (1,1), los bosques son exactamente los gráficos dispersos (1,1) y los gráficos con arboricidad k son exactamente los ( k, k ) -Gráficos dispersos. Los pseudoforestales son exactamente los gráficos dispersos (1,0), y los gráficos de Laman que surgen en la teoría de la rigidez son exactamente los gráficos ajustados (2,3).