Arboricidad

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 condiciones necesarias y suficientes para cuando un grafo es k-arbórico.

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 elgrafo 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 grafo es una medida de cuán denso es el grafo: los grafos con muchas aristas tienen una arboricidad alta y los grafos con una arboricidad alta deben tener un subgrafo denso.

Con 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 $\lceil m/(n-1)\rceil$ . Además, los subgrafo de cualquier grafo no pueden tener una arboricidad mayor que el propio grafo o, de manera equivalente, la arboricidad de un grafo debe ser al menos la arboricidad máxima de cualquiera de sus subgrafo. 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 grafo dado, entonces la arboricidad del grafo 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 grafos planos tienen arboricidad como máximo tres. Schnyder usó una descomposición especial de un grafo plano en tres bosques llamado madera de Schnyder para encontrar una incrustación en línea recta de cualquier grafo 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 grafo.

Las aproximaciones a la arboricidad de un grafo 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 grafo es el número máximo de subgrafo no acíclicos disjuntos en las aristas en los que se pueden dividir las aristas del grafo.

La arboricidad de la estrella de un grafo 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 las aristas del grafo. Si un árbol no es una estrella en sí mismo, su arboricidad de estrellas es dos, como se puede ver dividiendo las aristas 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 grafo es al menos igual a la arboricidad, y como máximo igual al doble de la arboricidad.

La arboricidad lineal de un grafo es el número mínimo de bosques lineales (una colección de caminos) en los que se pueden dividir las aristas del grafo. La arboricidad lineal de un grafo 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, 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 subgrafo de un grafo 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 gráfico 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 $a$ es al menos igual a $a$ , y como máximo igual a $2a-1$ . El número de coloración de un grafo, 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 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 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 grafo $G$ como $\max\{m_{S}/(n_{S}-1)\mid S\subseteq G\}.$ En otros términos, la arboricidad de un grafo es el techo de la arboricidad fraccionaria.

La (a,b)-descomponibilidad generaliza la arboricidad. Un grafo es $(a,b)$ -descomponible si sus aristas 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 grafo con arboricidad $a$ es $(a,0)$ -descomponible.

El número de árbol es el número mínimo de árboles que cubren las aristas de un grafo.

Arboricidad como medida de densidad

Algoritmos

Conceptos relacionados

Apariciones especiales

Referencias

Related Articles