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 (donde cada par de vértices está conectado por una arista). Lo contrario, un gráfico con sólo unas pocas aristas, es un gráfico disperso . La distinción entre lo que constituye un gráfico denso o disperso está mal definida y, a menudo, se representa mediante declaraciones "aproximadamente iguales a". Debido a esto, la forma en que se define la densidad a menudo depende del contexto del problema.
La densidad de gráficos de gráficos simples se define como la relación entre el número de aristas | mi | respecto a las máximas aristas posibles.
Para gráficos simples no dirigidos , la densidad del gráfico es:
Para gráficos simples dirigidos , los bordes máximos posibles son el doble que los de los gráficos no dirigidos (ya que hay dos direcciones para un borde), por lo que la densidad es:
donde E es el número de aristas y V es el número de vértices del 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).
Para familias de gráficos de tamaño creciente, a menudo se los llama dispersos si como . A veces, en informática , se utiliza una definición más restrictiva de escaso como o incluso .
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 gráfico 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 α tales que los subgrafos finitos de G con densidad α tienen un número acotado de vértices. Se puede demostrar utilizando el teorema de Erdős-Stone que la densidad superior sólo puede ser 1 o una de las relaciones superparticulares 0,1/2,2/3,3/4,4/5,…norte/norte + 1(ver, por ejemplo, Diestel, edición 5, p. 189).
Lee y Streinu (2008) y Streinu y Theran (2009) definen un gráfico como ( k , l ) -escaso 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 ) -escaso y tiene exactamente kn − l aristas. 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 gráficos dispersos ( k , k ) . Los pseudobosques 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) .
Otras familias de gráficos que no se caracterizan por su escasez también se pueden describir de esta manera. Por ejemplo, el hecho de que cualquier gráfico plano con n vértices tenga como máximo 3 n – 6 aristas (excepto los gráficos con menos de 3 vértices) y que cualquier subgrafo de un gráfico plano sea plano, en conjunto implican que los gráficos planos son (3 ,6) -escaso. Sin embargo, no todos los gráficos dispersos (3,6) son planos. De manera similar, los gráficos planos externos son (2,3) -dispersos y los gráficos bipartitos planos son (2,4) -dispersos.
Streinu y Theran muestran que la prueba de escasez ( k , l ) se puede realizar en tiempo polinómico cuando k y l son números enteros y 0 ≤ l < 2 k .
Para una familia de gráficos, la existencia de k y l tales que los gráficos de la familia sean todos ( k , l ) -escasos es equivalente a que los gráficos de la familia tengan degeneración limitada o arboricidad limitada . Más precisamente, de un resultado de Nash-Williams (1964) se deduce que las gráficas de arboricidad como máximo a son exactamente las gráficas ( a , a ) -dispersas. De manera similar, las gráficas de degeneración como máximo d son gráficas dispersas (Lick y White 1970).
Nešetřil & Ossona de Mendez (2010) consideraron que la dicotomía escasez/densidad hace necesario considerar infinitas clases de grafos en lugar de instancias de grafos únicos. Definieron clases de gráficos en algún lugar densos como aquellas clases de gráficos para las cuales existe un umbral t tal que cada gráfico completo aparece como una t -subdivisión en un subgrafo de un gráfico de la clase. Por el contrario, si tal umbral no existe, la clase no es densa en ninguna parte . Las propiedades de la dicotomía denso en ningún lugar versus denso en algún lugar se analizan en Nešetřil y Ossona de Mendez (2012).
Las clases de gráficos con degeneración acotada y de gráficos en ninguna parte densos se incluyen en los gráficos libres de bicliques , familias de gráficos que excluyen algún gráfico bipartito completo como subgrafo (Telle y Villanger 2012).
