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 una gráfica es k -arbórica.
Ejemplo
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 como medida de densidad
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 se pueden combinar para caracterizar la arboricidad: si dejamos que 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 de la gráfica es igual a
Cualquier grafo plano con vértices tiene como máximo bordes, de lo que se sigue por la fórmula de Nash-Williams que las gráficas planas 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.
Algoritmos
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 ).
Conceptos relacionados
La anarboricidad de un gráfico es el número máximo de subgráficos no cíclicos con bordes disjuntos en los que se pueden dividir los bordes del gráfico.
La arboricidad en estrella de un gráfico es el tamaño del bosque mínimo, cada árbol del cual es una estrella (árbol con como máximo un nodo no foliar), en el que se pueden dividir los bordes del gráfico. Si un árbol no es una estrella en sí mismo, su arboricidad estelar 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 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 una gráfica 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 pseudoforestales en los que se pueden dividir sus bordes. De manera equivalente, es la proporción máxima de aristas a vértices en cualquier subgráfico del gráfico, redondeada a un número entero. Al igual que con la arboricidad, la pseudoarboricidad tiene una estructura matroide que permite calcularla de manera eficiente ( Gabow & Westermann 1992 ).
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 subgrafos inducidos del gráfico, del grado mínimo de un vértice en el subgrafo. La degeneración de un gráfico con arboricidad. es al menos igual a , y como mucho igual a . El número de coloración de un gráfico, también conocido como su número de Szekeres-Wilf ( Szekeres y Wilf 1968 ) es siempre igual a su degeneración más 1 ( Jensen y Toft 1995 , p. 77 y sig.).
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 la empaquetadura que es dual con el problema de la cubierta que plantea la arboricidad. Los dos parámetros han sido estudiados juntos por Tutte y Nash-Williams.
La arboricidad fraccional es un refinamiento de la arboricidad, 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 gráfico es-descomponible si sus bordes se pueden dividir en conjuntos, cada uno de ellos induciendo un bosque, excepto uno que induce un grafo con grado máximo . Un gráfico con arboricidad es -descomponible.
El número de árbol es el número mínimo de árboles que cubre los bordes de un gráfico.
Apariciones especiales
La arboricidad aparece en la conjetura de Goldberg-Seymour .
Referencias
- Alon, N. (1988). "La arboricidad lineal de los gráficos". Revista de Matemáticas de Israel . 62 (3): 311–325. doi : 10.1007 / BF02783300 . Señor 0955135 .
- Chen, B .; Matsumoto, M .; Wang, J .; Zhang, Z .; Zhang, J. (1994). "Una breve prueba del teorema de Nash-Williams para la arboricidad de un gráfico". Gráficos y Combinatoria . 10 (1): 27-28. doi : 10.1007 / BF01202467 . Señor 1273008 .
- Erdős, P .; Hajnal, A. (1966). "Sobre el número cromático de gráficos y sistemas de conjuntos" (PDF) . Acta Mathematica Hungarica . 17 (1–2): 61–99. doi : 10.1007 / BF02020444 . Señor 0193025 . Archivado desde el original (PDF) el 24 de mayo de 2013 . Consultado el 30 de mayo de 2011 .
- Gabow, HN; Westermann, HH (1992). "Bosques, marcos y juegos: algoritmos para sumas y aplicaciones de matroides". Algoritmica . 7 (1): 465–497. doi : 10.1007 / BF01758774 . Señor 1154585 .
- Hakimi, SL ; Mitchem, J .; Schmeichel, EE (1996). "Estrella arboricidad de gráficos". Matemáticas discretas . 149 : 93–98. doi : 10.1016 / 0012-365X (94) 00313-8 . Señor 1375101 .
- Jensen, TR; Toft, B. (1995). Problemas de coloración de gráficos . Nueva York: Wiley-Interscience. ISBN 0-471-02865-7. Señor 1304254 .
- C. St. JA Nash-Williams (1961). "Árboles de expansión de bordes disjuntos de gráficos finitos". Revista de la Sociedad Matemática de Londres . 36 (1): 445–450. doi : 10.1112 / jlms / s1-36.1.445 . Señor 0133253 .
- C. St. JA Nash-Williams (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 . Señor 0161333 .
- W. Schnyder (1990). "Incrustación de gráficos planos en la cuadrícula" . Proc. 1er Simposio ACM / SIAM sobre Algoritmos Discretos (SODA) . págs. 138-148.
- Szekeres, G .; Wilf, HS (1968). "Una desigualdad para el número cromático de un gráfico" . Revista de teoría combinatoria . doi : 10.1016 / s0021-9800 (68) 80081-x . Señor 0218269 .
- Tutte, WT (1961). "Sobre el problema de descomponer una gráfica en n factores conectados". Revista de la Sociedad Matemática de Londres . 36 (1): 221–230. doi : 10.1112 / jlms / s1-36.1.221 . Señor 0140438 .