Gráfico denso - Dense graph

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áficos de gráficos simples se define como la relación entre el número de bordes con respecto al máximo de bordes posibles. ${\ Displaystyle | E |}$

Para gráficos simples no dirigidos , la densidad del gráfico es:

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

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:

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

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 ). ${\ Displaystyle {\ binom {| V |} {2}} = {\ frac {| V | (| V | -1)} {2}}}$

Densidad superior

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-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).

Gráficos escasos y ajustados

Lee & Streinu (2008) y Streinu & 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 las gráficas ajustadas (1,1), los bosques son exactamente las gráficas esparcidas (1,1) y las gráficas con arboricidad k son exactamente las gráficas esparcidas ( k , k ). 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).

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 grafo plano con n vértices tiene como máximo 3 n - 6 aristas (excepto para grafos con menos de 3 vértices), y que cualquier subgrafo de un grafo plano es plano, juntos implican que los grafos planos son (3 , 6) -espacio. Sin embargo, no todos los gráficos dispersos (3,6) son planos. De manera similar, los gráficos planos exteriores son (2,3) -espacios y los gráficos planos bipartitos son (2,4) -espacios.

Streinu y Theran muestran que las pruebas de $(k, l)$ -esparsidad se pueden realizar en tiempo polinomial cuando $k$ y $l$ son números enteros y $0 \leq l <2 k$ .

Para una familia de grafos, la existencia de k y l tales que los grafos de la familia sean todos $(k, l)$ -espacios es equivalente a que los grafos de la familia tengan degeneración limitada o arboricidad limitada . Más precisamente, se desprende del resultado de Nash-Williams (1964) que los gráficos de arboricity a lo sumo unos son exactamente los ( un , una ) gráficos opción -sparse. De manera similar, las gráficas de degeneración como máximo d son exactamente las gráficas $((d + 1) / 2, 1)$ dispersas.

Clases de gráficos escasos y densos

Nešetřil y Ossona de Mendez (2010) consideraron que la dicotomía dispersión / densidad hace necesario considerar clases de grafos infinitos en lugar de instancias de grafos únicos. Definieron clases de gráficos densos en algún lugar como aquellas clases de gráficos para los que existe un umbral t tal que cada gráfico completo aparece como una subdivisión t en un subgráfico 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 ninguna parte vs en algún lugar denso se discuten en Nešetřil y Ossona de Mendez (2012) .

Las clases de gráficos con degeneración limitada y de gráficos densos en ninguna parte se incluyen en los gráficos sin biclices , familias de gráficos que excluyen algún gráfico bipartito completo como un subgráfico ( Telle y Villanger 2012 ).

Ver también

Referencias

Paul E. Black, Gráfico disperso , del Diccionario de algoritmos y estructuras de datos, Paul E. Black (ed.), NIST . Consultado el 29 de septiembre de 2005.
Coleman, Thomas F .; Moré, Jorge J. (1983), "Estimación de matrices jacobianas dispersas y problemas de coloración de gráficos", SIAM Journal on Numerical Analysis , 20 (1): 187-209, 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 de juegos de guijarros y gráficos 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 gráficos finitos en bosques", Revista de la Sociedad Matemática de Londres , 39 (1): 12, doi : 10.1112 / jlms / s1-39.1.12 , MR 0161333
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 Mendez, Patrice (2010), "From Sparse Graph to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits", Congreso Europeo de Matemáticas , Sociedad Matemática Europea, págs. 135-165
Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 28 , Heidelberg: Springer, doi : 10.1007 / 978-3-642-27875-4 , hdl : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR 2920058.
Streinu, I .; Theran, L. (2009), "Hipergrafos dispersos y algoritmos de juegos de guijarros", 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 dominación en grafos libres de biclices", en Epstein, Leah; Ferragina, Paolo (eds.), Algorithms - ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, 10-12 de septiembre de 2012, Proceedings , Lecture Notes in Computer Science , 7501 , Springer, pp. 802-812, doi : 10.1007 / 978-3-642-33090-2_69.

Languages

In other projects