La arboricidad de un grafo no dirigido es el número mínimo de bosques en los que se pueden dividir sus aristas . De manera equivalente, es el número mínimo de bosques de expansión necesarios para cubrir todas las aristas del grafo. El teorema de Nash-Williams proporciona las condiciones necesarias y suficientes para que un grafo sea k -arbórico.
La figura muestra el grafo bipartito completo K 4,4 , con los colores que indican 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 grafo general tiene dieciséis aristas, más del doble de la cantidad de aristas en un solo bosque. Por lo tanto, la arboricidad de K 4,4 es tres.
La arboricidad de un gráfico es una medida de qué tan denso es el gráfico: los gráficos con muchas aristas tienen alta arboricidad y los gráficos con alta arboricidad deben tener un subgráfico denso.
En más detalle, como cualquier bosque de n vértices tiene como máximo n-1 aristas, la arboricidad de un grafo con n vértices y m aristas es al menos . Además, los subgrafos de cualquier grafo no pueden tener una arboricidad mayor que el grafo mismo, o equivalentemente la arboricidad de un grafo debe ser al menos la arboricidad máxima de cualquiera de sus subgrafos. Nash-Williams demostró que estos dos hechos se pueden combinar para caracterizar la arboricidad: si dejamos que n S y m S denoten el número de vértices y aristas, respectivamente, de cualquier subgrafo S del grafo dado, entonces la arboricidad del grafo es igual a
Cualquier grafo plano con vértices tiene como máximo tres aristas, de lo que se deduce, por la fórmula de Nash-Williams, que los grafos planos tienen como máximo tres arboricidades. Schnyder utilizó una descomposición especial de un grafo plano en tres bosques, llamada bosque de Schnyder, para encontrar una incrustación en línea recta de cualquier grafo plano en una cuadrícula de área pequeña.
La arboricidad de un grafo se puede expresar como un caso especial de un problema de partición de matroide más general , [1] en el que se desea expresar un conjunto de elementos de un matroide como una unión de un pequeño número de conjuntos independientes. En 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 el tiempo, donde es el número de aristas del grafo.
Las aproximaciones a la arboricidad de un grafo se pueden calcular más rápidamente. Existen algoritmos de aproximación de tiempo lineal de 2 bits [2] [3] y un algoritmo de tiempo casi lineal con un error aditivo de 2 bits [4].
La anarboricidad de un gráfico es el número máximo de subgráficos no acíclicos, disjuntos en sus aristas, en los que se pueden dividir las aristas del gráfico.
La arboricidad en estrella de un grafo es el tamaño del bosque mínimo, cada árbol del cual es una estrella (árbol con como máximo un nodo que no es una hoja), en el que se pueden dividir los bordes del grafo. Si un árbol no es una estrella en sí mismo, su arboricidad en estrella es dos, como se puede ver al dividir los bordes en dos subconjuntos a distancias pares e impares de la raíz del árbol respectivamente. Por lo tanto, la arboricidad en estrella de cualquier grafo 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 grafo es el número mínimo de pseudobosques en los que se pueden dividir sus aristas. De manera equivalente, es la relación máxima de aristas a vértices en cualquier subgrafo del grafo, redondeada a un número entero. Al igual que la arboricidad, la pseudoarboricidad tiene una estructura matroide que permite calcularla de manera eficiente (Gabow y Westermann 1992).
La densidad de subgrafos de un gráfico es la densidad de su subgrafo más denso.
El grosor de un grafo es el número mínimo de subgrafos planos en los que se pueden dividir sus aristas. Como cualquier grafo plano tiene arboricidad tres, el grosor de cualquier grafo es al menos igual a un tercio de la arboricidad y, como máximo, igual a la arboricidad.
La degeneración de un grafo es el máximo, sobre todos los subgrafos inducidos del grafo, del grado mínimo de un vértice en el subgrafo. La degeneración de un grafo con arboricidad es al menos igual a , y como máximo igual a . El número de coloración de un grafo, también conocido como su número de Szekeres-Wilf (Szekeres & Wilf 1968) es siempre igual a su degeneración más 1 (Jensen & Toft 1995, p. 77f.).
La fuerza de un grafo 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 grafo. Es el problema de empaquetamiento que es dual al problema de cubrimiento planteado por la arboricidad. Tutte y Nash-Williams han estudiado los dos parámetros juntos.
La arboricidad fraccional es un refinamiento de la arboricidad, tal como se define para un gráfico como En otros términos, la arboricidad de un gráfico es el techo de la arboricidad fraccional.
La descomponibilidad (a,b) generaliza la arboricidad. Un grafo es -descomponible si sus aristas pueden dividirse en conjuntos, cada uno de los cuales induce un bosque, excepto uno que induce un grafo con grado máximo . Un grafo con arboricidad es -descomponible.
El número de árboles es el número mínimo de árboles que cubren los bordes de un gráfico.
La arboricidad aparece en la conjetura de Goldberg-Seymour .
