Arboricidad

La arboricidad de un gráfico no dirigido es el número mínimo de bosques en los que se pueden dividir sus bordes. De manera equivalente, es el número mínimo de bosques de expansión necesarios para cubrir todos los bordes del gráfico. El teorema de Nash-Williams proporciona condiciones necesarias y suficientes para cuando un gráfico es k-arbórico.

Ejemplo

La figura muestra el grafo bipartito completo K_4,4, con los colores indicando una partición de sus aristas en tres bosques. K_4,4 no se puede dividir en menos bosques, porque cualquier bosque en sus ocho vértices tiene como máximo siete aristas, mientras que el gráfico general tiene dieciséis aristas, más del doble de la cantidad de aristas en un solo bosque. Por tanto, la arboricidad de K_4,4 es tres.

Arboricidad como medida de densidad

La arboricidad de un gráfico es una medida de cuán denso es el gráfico: los gráficos con muchos bordes tienen una arboricidad alta y los gráficos con una arboricidad alta deben tener un subgráfico denso.

Con más detalle, como cualquier bosque de $n$ vértices tiene como máximo $n-1$ aristas, la arboricidad de un gráfico con n vértices y m aristas es al menos $\lceil m/(n-1)\rceil$ . Además, los subgráficos de cualquier gráfico no pueden tener una arboricidad mayor que el propio gráfico o, de manera equivalente, la arboricidad de un gráfico debe ser al menos la arboricidad máxima de cualquiera de sus subgráficos. Nash-Williams demostró que estos dos hechos se pueden combinar para caracterizar la arboricidad: si n _S y m _S denotan el número de vértices y aristas, respectivamente, de cualquier subgrafo S del gráfico dado, entonces la arboricidad del gráfico es igual $\max _{S}\{\lceil m_{S}/(n_{S}-1)\rceil \}.$

Cualquier grafo plano con $n$ vértices tiene como máximo $3n-6$ aristas, de donde se sigue por la fórmula de Nash-Williams que los gráficos planos tienen arboricidad como máximo tres. Schnyder usó una descomposición especial de un gráfico plano en tres bosques llamado madera de Schnyder para encontrar una incrustación en línea recta de cualquier gráfico plano en una cuadrícula de área pequeña.

Algoritmos

La arboricidad de un grafo se puede expresar como un caso especial de un problema de partición matroide más general,^[1] en el que se desea expresar un conjunto de elementos de una matroide como la unión de un pequeño número de conjuntos independientes. Como consecuencia, la arboricidad se puede calcular mediante un algoritmo de tiempo polinomial (Gabow y Westermann, 1992). El mejor algoritmo exacto actual calcula la arboricidad en $O(m{\sqrt {m}})$ tiempo, donde $m$ es el número de aristas en el gráfico.

Las aproximaciones a la arboricidad de un gráfico se pueden calcular más rápido. Hay algoritmos de aproximación de tiempo lineal 2,^[2]^[3] y un algoritmo de tiempo casi lineal con un error aditivo de 2.^[4]

Conceptos relacionados

La anarboricidad de un gráfico es el número máximo de subgráficos no acíclicos disjuntos en los bordes en los que se pueden dividir los bordes del gráfico.

La arboricidad de la estrella de un gráfico es el tamaño del bosque mínimo, cada árbol del cual es una estrella (árbol con un máximo de un nodo sin hoja), en el que se pueden dividir los bordes del gráfico. Si un árbol no es una estrella en sí mismo, su arboricidad de estrellas es dos, como se puede ver dividiendo los bordes en dos subconjuntos a distancias pares e impares de la raíz del árbol, respectivamente. Por lo tanto, la arboricidad de la estrella de cualquier gráfico es al menos igual a la arboricidad, y como máximo igual al doble de la arboricidad.

La arboricidad lineal de un gráfico es el número mínimo de bosques lineales (una colección de caminos) en los que se pueden dividir los bordes del gráfico. La arboricidad lineal de un gráfico está estrechamente relacionada con su grado máximo y su número de pendiente.

La pseudoarboricidad de un gráfico es el número mínimo de pseudobosques en los que se pueden dividir sus bordes. De manera equivalente, es la relación máxima de aristas a vértices en cualquier subgrafo del gráfico, redondeado a un número entero. Al igual que con la arboricidad, la pseudoarboricidad tiene una estructura matroide que le permite ser computada eficientemente (Gabow y Westermann, 1992).

La densidad de subgráfico de un gráfico es la densidad de su subgráfico más denso.

El grosor de un gráfico es el número mínimo de subgráficos planos en los que se pueden dividir sus bordes. Como cualquier gráfico plano tiene arboricidad tres, el grosor de cualquier gráfico es al menos igual a un tercio de la arboricidad y como máximo igual a la arboricidad.

La degeneración de un gráfico es el máximo, sobre todos los subgráficos inducidos del gráfico, del grado mínimo de un vértice en el subgráfico. La degeneración de un gráfico con arboricidad $a$ es al menos igual a $a$ , y como máximo igual a $2a-1$ . El número de coloración de un gráfico, también conocido como número de Szekeres-Wilf (Szekeres y Wilf, 1968), siempre es igual a su degeneración más 1 (Jensen y Toft, 1995, p. 77f.)).

La fuerza de un gráfico es un valor fraccionario cuya parte entera da el número máximo de árboles de expansión disjuntos que se pueden dibujar en un gráfico. Es el problema de empaquetamiento que es dual al problema de cobertura planteado por la arboricidad. Los dos parámetros han sido estudiados juntos por Tutte y Nash-Williams.

La arboricidad fraccionaria es un refinamiento de la arboricidad, tal como se define para un gráfico $G$ como $\max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.$ En otros términos, la arboricidad de un gráfico es el techo de la arboricidad fraccionaria.

La (a,b)-descomponibilidad generaliza la arboricidad. Un gráfico es $(a,b)$ -descomponible si sus bordes se pueden dividir en $a+1$ conjuntos, cada uno de ellos induciendo un bosque, excepto uno que induce un grafo con grado máximo $b$ . Un gráfico con arboricidad $a$ es $(a,0)$ -descomponible.

El número de árbol es el número mínimo de árboles que cubren los bordes de un gráfico.

Apariciones especiales

La arboricidad aparece en la conjetura de Goldberg-Seymour.

Referencias

↑ Edmonds, Jack (1965), «Minimum partition of a matroid into independent subsets», Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 69B: 67, doi:10.6028/jres.069B.004 .
↑ Eppstein, David (1994), «Arboricity and bipartite subgraph listing algorithms», Inf. Process. Letters 51 (4): 207-211, doi:10.1016/0020-0190(94)90121-X .
↑ Arikati, Srinivasa Rao; Maheshwari, Anil; Zaroliagis, Christos D. (1997), «Efficient computation of implicit representations of sparse graphs», Discret. Appl. Math. 78 (1–3): 1-16, doi:10.1016/S0166-218X(97)00007-3 .
↑ Blumenstock, Markus; Fischer, Frank (2020), «A constructive arboricity approximation scheme», 46th International Conference on Current Trends in Theory and Practice of Informatics .

Datos: Q4784907

[1] Edmonds, Jack (1965), «Minimum partition of a matroid into independent subsets», Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 69B: 67, doi:10.6028/jres.069B.004 .

[2] Eppstein, David (1994), «Arboricity and bipartite subgraph listing algorithms», Inf. Process. Letters 51 (4): 207-211, doi:10.1016/0020-0190(94)90121-X .

[3] Arikati, Srinivasa Rao; Maheshwari, Anil; Zaroliagis, Christos D. (1997), «Efficient computation of implicit representations of sparse graphs», Discret. Appl. Math. 78 (1–3): 1-16, doi:10.1016/S0166-218X(97)00007-3 .

[4] Blumenstock, Markus; Fischer, Frank (2020), «A constructive arboricity approximation scheme», 46th International Conference on Current Trends in Theory and Practice of Informatics .

[1]

[2]

[3]

[4]