Grafo denso

En matemáticas , un grafo denso es aquel en el que el número de aristas se aproxima al número máximo (donde cada par de vértices está conectado por una arista). Lo opuesto, un grafo con pocas aristas, es un grafo disperso . La distinción entre un grafo denso y uno disperso no está bien definida y a menudo se representa mediante expresiones aproximadas. Por ello, la definición de densidad suele depender del contexto del problema.

Consideremos un gráfico simple.${\displaystyle (V,E)}$dónde${\displaystyle V}$es el conjunto de vértices y${\displaystyle E}$es el conjunto de aristas. Escribimos${\displaystyle |V|}$para denotar el número de vértices, y${\displaystyle |E|}$para denotar el número de aristas. La densidad del grafo simple${\displaystyle (V,E)}$se define como la relación entre el número de aristas | E | y el máximo número posible de aristas.

Para grafos simples no dirigidos , la densidad del grafo es:

${\displaystyle D={\frac {|E|}{\binom {|V|}{2}}}={\frac {2|E|}{|V|(|V|-1)}}}$

Para grafos simples dirigidos , el número máximo de aristas posibles es el doble que el de los grafos no dirigidos (ya que hay dos direcciones para una arista), por lo que la densidad es:

${\displaystyle D={\frac {|E|}{2{\binom {|V|}{2}}}}={\frac {|E|}{|V|(|V|-1)}}}$

El número máximo de aristas para un grafo no dirigido es${\displaystyle {\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}}$, por lo que la densidad máxima es 1 (para grafos completos ) y la densidad mínima es 0. ^{[ 1 ]}

Para familias de grafos de tamaño creciente, a menudo se les llama dispersos si${\displaystyle D\rightarrow 0}$como${\displaystyle |V|\rightarrow \infty }$A veces, en informática , se utiliza una definición más restrictiva de disperso, como por ejemplo:${\displaystyle |E|=O(|V|\log |V|)}$o incluso${\displaystyle |E|=O(|V|)}$. En este mismo contexto, un grafo denso puede definirse como cualquier grafo donde | E | está "cerca" de${\displaystyle |V|^{2}}$. ^{[ 2 ] [ 3 ]}

La densidad superior es una extensión del concepto de densidad de grafos definido anteriormente, desde 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 , … n / n + 1 [ 4 ]

Lee y Streinu (2008) y Streinu y Theran (2009) definen un grafo como ( k , l ) -disperso si todo subgrafo no vacío con n vértices tiene como máximo kn − l aristas, y ( k , l ) -apretado si es ( k , l ) -disperso y tiene exactamente kn − l aristas. Así, los árboles son exactamente los grafos (1,1) -apretados, 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) -apretados. ^{[ 5 ]}

Otras familias de grafos que no se caracterizan por su dispersión también pueden describirse de esta manera. Por ejemplo, el hecho de que cualquier grafo planar con n vértices tenga como máximo 3n – 6 aristas (excepto los grafos con menos de 3 vértices), y que cualquier subgrafo de un grafo planar sea planar, implica que los grafos planares son (3,6) -dispersos. Sin embargo, no todos los grafos (3,6) -dispersos son planares. De manera similar, los grafos exteriores planares son (2,3) -dispersos y los grafos bipartitos planares son (2,4) -dispersos.

Streinu y Theran muestran que la prueba de ( k , l ) -esparsidad se puede realizar en tiempo polinomial cuando k y l son enteros y 0 ≤ l < 2k . ^{[ 6 ]}

Para una familia de grafos, la existencia de k y l tales que los grafos de la familia sean todos ( k , l ) -dispersos es equivalente a que los grafos de la familia tengan degeneración acotada o arboricidad acotada . Más precisamente, se deduce de un resultado de Nash-Williams (1964) que los grafos de arboricidad como máximo a son exactamente los grafos ( a , a ) -dispersos. ^{[ 7 ]} De manera similar, los grafos de degeneración como máximo d son${\displaystyle \left(d,{\binom {d+1}{2}}\right)}$-grafos dispersos. ^{[ 8 ]}

Nešetřil y Ossona de Méndez (2010) consideraron que la dicotomía escasez/densidad hace necesario considerar clases de grafos infinitas en lugar de instancias de grafos individuales. Definieron las clases de grafos densas en algún lugar como aquellas clases de grafos para las cuales existe un umbral t tal que cada grafo completo aparece como una t -subdivisión en un subgrafo de un grafo de la clase. Por el contrario, si no existe tal umbral, la clase no es densa en ningún lugar . ^{[ 9 ]}

Las clases de grafos con degeneración acotada y de grafos densos en ninguna parte están incluidas en los grafos libres de bicliques , familias de grafos que excluyen algún grafo bipartito completo como subgrafo. ^{[ 10 ]}

• Expansión limitada
• Subgrafo denso

• Coleman, Thomas F.; Moré, Jorge J. (1983), "Estimación de matrices jacobianas dispersas y problemas de coloración de grafos", SIAM Journal on Numerical Analysis , 20 (1): 187–209 , Bibcode : 1983SJNA...20..187C , doi : 10.1137/0720013
• Diestel, Reinhard (2005), Teoría de grafos , Textos de posgrado en matemáticas , Springer-Verlag, ISBN 3-540-26183-4, OCLC 181535575 
• Lee, Audrey; Streinu, Ileana (2008), "Algoritmos del juego de guijarros y grafos dispersos", Matemáticas Discretas , 308 (8): 1425– 1437, arXiv : math/0702129 , doi : 10.1016/j.disc.2007.07.104 , MR 2392060 
• Nash-Williams, C. St. JA (1964), "Descomposición de grafos finitos en bosques", Journal of the London Mathematical Society , 39 (1): 12, doi : 10.1112/jlms/s1-39.1.12 , MR 0161333 
• Lick, Don R; White, Arthur T (1970), " k -Grafos degenerados" , Canadian Journal of Mathematics , 22 (5): 1082– 1096, doi : 10.4153/CJM-1970-125-1
• Preiss, primero (1998), Estructuras de datos y algoritmos con patrones de diseño orientados a objetos en C++ , John Wiley & Sons, ISBN 0-471-24134-2
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice ( 2010), "De grafos dispersos a estructuras densas en ninguna parte: descomposiciones, independencia, dualidades y límites", Congreso Europeo de Matemáticas , Sociedad Matemática Europea, pp. 135–165 
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol.  28, Heidelberg: Springer, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058 
• Streinu, I.; Theran, L. (2009), "Hipergrafos dispersos y algoritmos del juego de las piedras", European Journal of Combinatorics , 30 (8): 1944–1964 , arXiv : math/0703921 , doi : 10.1016/j.ejc.2008.12.018
• Telle, Jan Arne; Villanger, Yngve (2012), "Algoritmos FPT para la dominación en grafos libres de bicliques", en Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20.º Simposio Europeo Anual, Ljubljana, Eslovenia, 10-12 de septiembre de 2012, Actas , Lecture Notes in Computer Science , vol.  7501, Springer, pp. 802-812 , doi : 10.1007/978-3-642-33090-2_69 , ISBN  978-3-642-33089-6

• Black, Paul E., "Grafo disperso", Diccionario de algoritmos y estructuras de datos , NIST , consultado el 29 de septiembre de 2005.