Conde Woodiness
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de octubre de 2021; la verificación requiere 1 edición .El treeness de un gráfico no dirigido es el número mínimo de bosques en los que se pueden descomponer los bordes . De manera equivalente, este es el número mínimo de árboles de expansión que se necesitan para cubrir los bordes del gráfico.
Ejemplo
La figura muestra un grafo bipartito completo K 4,4 con particiones del grafo en tres bosques coloreados en diferentes colores. K 4,4 no se puede dividir en menos bosques, ya que cualquier bosque en ocho vértices tiene un máximo de siete aristas, mientras que el gráfico completo tiene dieciséis aristas, que es más del doble de la cantidad de aristas en un solo bosque. Por lo tanto, la arborescencia del gráfico K 4,4 es igual a tres.
Leñosidad como medida de densidad
La arborescencia de un gráfico es una medida de la densidad de un gráfico: las gráficas con una gran cantidad de bordes tienen una gran arborescencia y las gráficas con una gran arborescencia deben tener subgráficos densos.
Más precisamente, dado que cualquier bosque de n vértices tiene como máximo n − 1 aristas, la arborescencia de un gráfico con n vértices y m aristas es al menos . Además, los subgrafos de cualquier gráfico no pueden tener una arborescencia mayor que la del propio gráfico o, de manera equivalente, la arborescencia del gráfico debe ser al menos tan grande como la arborescencia máxima de sus subgrafos. Nash-Williams demostró que estos dos hechos se pueden combinar para caracterizar la arborescencia: si n S y m S denotan, respectivamente, el número de vértices y aristas de un subgrafo arbitrario S de un gráfico dado, entonces la arborescencia del gráfico es igual a
Cualquier gráfico plano con vértices tiene un máximo de aristas, lo que implica la fórmula de Nash-Williams de que la arborescencia de un gráfico plano no excede de tres. Schneider usó una descomposición especial de un gráfico plano en tres bosques, llamado bosque de Schneider , para encontrar el segmento de línea incrustado de cualquier gráfico en una red de área pequeña.
Algoritmos
La arborescencia de un gráfico se puede expresar como un caso especial de un problema de descomposición matroide más general , en el que se requiere expresar el número de elementos de un matroide en términos de la unión de un número menor de conjuntos independientes . Como consecuencia, la arborescencia se puede calcular utilizando un algoritmo de tiempo polinomial [1] .
Conceptos relacionados
El árbol de estrellas de un gráfico es el tamaño del bosque mínimo, cada árbol del cual es una estrella (un árbol con como máximo un vértice que no es una hoja), en el que se pueden descomponer los bordes del gráfico. Si un árbol no es en sí mismo una estrella, su arborescencia de estrella es dos, lo que se puede ver si los bordes se dividen en dos subconjuntos, con una distancia par e impar desde la raíz. Así, la arboricidad estelar de un grafo no es menor que su arborescencia ni mayor que el doble de su arborescencia.
El árbol lineal de un gráfico es el tamaño del bosque lineal mínimo ( un bosque en el que todos los vértices inciden como máximo en dos bordes) en el que se pueden descomponer los bordes del gráfico. La arborescencia lineal de un gráfico está estrechamente relacionada con su grado máximo de vértices y su número de pendientes .
El pseudo-árbol de un gráfico es el número mínimo depseudo-bosquesen los que se pueden descomponer los bordes. De manera equivalente, este número es igual a la proporción máxima de aristas a vértices en cualquier subgráfico del gráfico. Al igual que con la arborescencia, la pseudo-arborescencia tiene una estructura matroide que permite la eficiencia computacional [1] .
El grosor de un gráfico es el número mínimo de subgráficos planos en los que se pueden dividir los bordes. Dado que cualquier gráfico plano tiene una arborescencia de tres, el grosor de cualquier gráfico es al menos un tercio de la arborescencia y, como máximo, de la arborrealidad.
La degeneración de un gráfico es el número máximo, sobre todos los subgráficos generados del gráfico, del grado mínimode los vértices del subgráfico. La degeneración de un gráfico de árbolno es ni menorni mayor que. El número de coloración del gráfico, también conocido como el número de Szekeres-Wilf [2] , siempre es igual a su degeneración más 1 [3] .
La potencia de un gráfico es un valor fraccionario, cuya parte entera da el número máximo de árboles de expansión no superpuestos que se pueden dibujar en el gráfico. Calcular este número es un problema de empaquetamiento, que es dual al problema de cobertura que surge del problema de los árboles.
La arborrealidad fraccionada es una arborescencia avanzada definida para un grafo como En otras palabras, la arborescencia de un grafo es el techo de la arborescencia fraccional.
(a, b) - La descomposición generaliza la arborescencia. Un grafo es descomponible si sus aristas se pueden descomponer enconjuntos, cada uno de los cuales da un bosque, excepto uno, que da un grafo con grado máximo. Un gráfico de árboles-descomponible.
Notas
- ↑ 1 2 Gabow, Westermann, 1992 .
- ↑ Székeres, Wilf, 1968 .
- ↑ Jensen, Toft, 1995 , pág. 77f.
Literatura
- N. Alon. La arboricidad lineal de los gráficos // Israel Journal of Mathematics . - 1988. - T. 62 , núm. 3 . — S. 311–325 . -doi : 10.1007/ BF02783300 .
- B. Chen, M. Matsumoto, J. Wang, Z. Zhang, J. Zhang. Una breve prueba del teorema de Nash-Williams para la arboricidad de un gráfico // Gráficos y combinatoria. - 1994. - T. 10 , núm. 1 . — P. 27–28 . -doi : 10.1007/ BF01202467 .
- P. Erdős, A. Hajnal. Sobre el número cromático de grafos y sistemas de conjuntos // Acta Mathematica Hungarica . - 1966. - T. 17 , núm. 1–2 . — S. 61–99 . -doi : 10.1007/ BF02020444 .
- HN Gabow, HH Westermann. Bosques, marcos y juegos: Algoritmos para sumas matroid y aplicaciones // Algorithmica . - 1992. - T. 7 , nº. 1 . — S. 465–497 . -doi : 10.1007/ BF01758774 .
- S. L. Hakimi, J. Mitchem, E. E. Schmeichel. Arboricidad estelar de grafos // Matemática Discreta . - 1996. - T. 149 . — S. 93–98 . - doi : 10.1016/0012-365X(94)00313-8 .
- TR Jensen, B. Toft. Problemas para colorear gráficos. - Nueva York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
- c.st. JA Nash-Williams. Árboles de expansión disjuntos de borde de grafos finitos // Revista de la Sociedad Matemática de Londres . - 1961. - T. 36 , núm. 1 . — S. 445–450 . -doi : 10.1112 / jlms/s1-36.1.445 .
- c.st. JA Nash-Williams. Descomposición de grafos finitos en bosques // Diario de la Sociedad Matemática de Londres . - 1964. - T. 39 , núm. 1 . - S. 12 . -doi : 10.1112 / jlms/s1-39.1.12 .
- W. Schnyder. proc. 1er Simposio ACM/SIAM sobre Algoritmos Discretos (SODA). - 1990. - S. 138-148.
- G. Szekeres, H. S. Wilf. Una desigualdad para el número cromático de un gráfico // Journal of Combinatorial Theory . - 1968. - doi : 10.1016/s0021-9800(68)80081-x .
- WT Tutte. Sobre el problema de descomponer un gráfico en n factores conexos // Journal of the London Mathematical Society . - 1961. - T. 36 , núm. 1 . — S. 221–230 . -doi : 10.1112 / jlms/s1-36.1.221 .