En matemáticas , un grafo denso es un grafo en el que el número de aristas es cercano al número máximo de aristas (donde cada par de vértices está conectado por una arista). Lo opuesto, un grafo con solo unas pocas aristas, es un grafo disperso . La distinción entre lo que constituye un grafo denso y disperso está mal definida y, a menudo, se representa mediante declaraciones del tipo "aproximadamente igual a". Debido a esto, la forma en que se define la densidad a menudo depende del contexto del problema.
La densidad gráfica de gráficos simples se define como la relación entre el número de aristas | E | con respecto al máximo de aristas posibles.
Para gráficos simples no dirigidos , la densidad del gráfico es:
Para gráficos simples dirigidos , la cantidad máxima de aristas posibles es el doble que la de los gráficos no dirigidos (ya que hay dos direcciones para una arista), por lo que la densidad es:
donde E es el número de aristas y V es el número de vértices del grafo. El número máximo de aristas para un grafo no dirigido es , por lo que la densidad máxima es 1 (para grafos completos ) y la densidad mínima es 0 (Coleman y Moré 1983).
En el caso de familias de gráficos de tamaño creciente, a menudo se los denomina dispersos si como . A veces, en informática , se utiliza una definición más restrictiva de disperso como o incluso .
La densidad superior es una extensión del concepto de densidad de grafos definido anteriormente de grafos finitos a grafos 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 grafo G es el ínfimo 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 solo puede ser 1 o una de las razones superparticulares 0, 1/2 , 2/3 , 3/4 , 4/5 , … norte/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 ) -disperso si cada subgrafo no vacío con n vértices tiene como máximo kn − l aristas, y ( k , l ) -estrecho si es ( k , l ) -disperso y tiene exactamente kn − l aristas. Por lo tanto, los árboles son exactamente los grafos (1,1) -estrechos, los bosques son exactamente los grafos (1,1) -dispersos y los grafos con arboricidad k son exactamente los grafos ( k , k ) -dispersos. Los pseudobosques son exactamente los grafos (1,0) -dispersos y los grafos de Laman que surgen en la teoría de la rigidez son exactamente los grafos (2,3) -estrechos.
Otras familias de grafos que no se caracterizan por su escasez también pueden describirse de esta manera. Por ejemplo, los hechos de que cualquier grafo plano con n vértices tiene como máximo 3 n – 6 aristas (excepto los grafos con menos de 3 vértices), y que cualquier subgrafo de un grafo plano es plano, implican en conjunto que los grafos planos son (3,6) -escasos. Sin embargo, no todos los grafos (3,6) -escasos son planos. De manera similar, los grafos planos exteriores son (2,3) -escasos y los grafos bipartitos planos son (2,4) -escasos.
Streinu y Theran muestran que la prueba de ( k , l ) -esparcimiento se puede realizar en tiempo polinomial cuando k y l son números enteros y 0 ≤ l < 2 k .
Para una familia de grafos, la existencia de k y l tales que los grafos en la familia son todos ( k , l ) -dispersos es equivalente a que los grafos en la familia tengan degeneración acotada o arboricidad acotada . Más precisamente, se sigue de un resultado de Nash-Williams (1964) que los grafos de arboricidad como máximo a son exactamente los grafos ( a , a ) -dispersos. De manera similar, los grafos de degeneración como máximo d son grafos -dispersos (Lick & White 1970).
Nešetřil y Ossona de Méndez (2010) consideraron que la dicotomía escasez/densidad hace necesario considerar infinitas clases de grafos en lugar de instancias de grafos individuales. Definieron las clases de grafos densos en algún lugar como aquellas clases de grafos para las que existe un umbral t tal que cada grafo completo aparece como una t -subdivisión en un subgrafo de un grafo en la clase. Por el contrario, si dicho umbral no existe, la clase es densa en ningún lugar . Las propiedades de la dicotomía densa en ningún lugar vs. densa en algún lugar se discuten en Nešetřil y Ossona de Méndez (2012).
Las clases de grafos con degeneración acotada y de grafos densos en ninguna parte se incluyen en los grafos libres bicliques , familias de grafos que excluyen algún grafo bipartito completo como subgrafo (Telle y Villanger 2012).
