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 las condiciones necesarias y suficientes para cuando una gráfica es k -arbórica.
La figura muestra el gráfico bipartito completo K 4,4 , con los colores que indican una partición de sus bordes 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 bordes, mientras que el gráfico general tiene dieciséis bordes, más del doble del número de bordes en un solo bosque. Por lo tanto, la arboricidad de K 4,4 es tres.
La arboricidad de una gráfica es una medida de cuán densa es la gráfica: las gráficas con muchos bordes tienen alta arboricidad y las gráficas con alta arboricidad deben tener un subgrafo denso.
Más detalladamente, como cualquier bosque de n vértices tiene como máximo n-1 aristas, la arboricidad de un gráfico con n vértices ym aristas es al menos . Además, los subgrafos de cualquier gráfico no pueden tener arboricidad mayor que el gráfico en sí, o de manera equivalente, la arboricidad de un gráfico debe ser al menos la arboricidad máxima de cualquiera de sus subgrafos. Nash-Williams demostró que estos dos hechos pueden combinarse para caracterizar la arboricidad: si dejamos que n S ym S denoten el número de vértices y aristas, respectivamente, de cualquier subgrafo S de la gráfica dada, entonces la arboricidad de la gráfica es igual a
Cualquier gráfico plano con vértices tiene como máximo aristas, de lo que 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 llamados 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.
La arboricidad de una gráfica se puede expresar como un caso especial de un problema de partición de matroides más general , en el que se desea expresar un conjunto de elementos de una matroide como una 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 & Westermann 1992 ).
