En la teoría de grafos, una zarza para un gráfico no dirigido G es una familia de subgrafías conectadas de G que se tocan entre sí: para cada par de subgrafías disjuntas, debe existir un borde en G que tenga un punto final en cada subgrafía. El orden de una zarza es el tamaño más pequeño de un conjunto de golpes , un conjunto de vértices de G que tiene una intersección no vacía con cada uno de los subgrafos. Brambles se pueden utilizar para caracterizar el treewidth de G .
Ancho de árbol y paraísos [ editar ]
Un paraíso de orden k en un gráfico G es una función β que asigna cada conjunto X de menos de k vértices a un componente conectado de G - X , de tal manera que cada dos subconjuntos β ( X ) y β ( Y ) se toquen El uno al otro. Por lo tanto, el conjunto de imágenes de β forma una zarza en G , con el orden k . Por el contrario, cada zarza puede usarse para determinar un refugio: para cada conjunto X de tamaño más pequeño que el orden de la zarza, hay un componente único conectadoβ ( X ) que contiene todos los subgraphs en la zarza que son disjunta de X .
Como mostraron Seymour y Thomas, el orden de una zarza (o equivalente, de un refugio) caracteriza el ancho del árbol : un gráfico tiene una zarza de orden k si y solo si tiene un ancho de árbol de al menos k - 1 . [1]
Tamaño de zarzas [ editar ]
Los gráficos expansores de grado acotado tienen un ancho de árbol proporcional a su número de vértices y, por lo tanto, también tienen zarzas de orden lineal. Sin embargo, como lo demostraron Martin Grohe y Dániel Marx, para estos gráficos, una zarza de tan alto orden debe incluir exponencialmente muchos conjuntos. Más fuertemente, para estos gráficos, incluso las zarzas cuyo orden es ligeramente mayor que la raíz cuadrada del ancho del árbol deben tener un tamaño exponencial. Sin embargo, Grohe y Marx también mostraron que cada gráfica de ancho de árbol k tiene una zarza de tamaño polinómico y de orden.. [2]
Complejidad computacional [ editar ]
Debido a que las zarzas pueden tener un tamaño exponencial, no siempre es posible construirlas en tiempo polinómico para gráficos de ancho de árbol ilimitado. Sin embargo, cuando el ancho del árbol está acotado, es posible una construcción de tiempo polinomial: es posible encontrar una zarza de orden k , cuando existe, en el tiempo O ( n k + 2 ) donde n es el número de vértices en el gráfico dado . Incluso son posibles algoritmos más rápidos para gráficos con pocos separadores mínimos. [3]
Bodlaender, Grigoriev y Koster [4] estudiaron la heurística para encontrar zarzas de alto orden. Sus métodos no siempre generan zarzas de orden cercanas al ancho del árbol del gráfico de entrada, pero para los gráficos planos dan una relación de aproximación constante . Kreutzer y Tazari [5] proporcionan algoritmos aleatorios que, en gráficos de ancho de árbol k , encuentran zarzas de tamaño polinómico y de ordendentro del tiempo polinomial, dentro de un factor logarítmico del orden mostrado por Grohe y Marx (2009) para las zarzas de tamaño polinómico.
Zarzas dirigidas [ editar ]
El concepto de zarza también se ha definido para gráficos dirigidos [6] [7] . En un gráfico dirigido D , una zarza es una colección de subgrafías de D fuertemente conectadas que se tocan entre sí: por cada par de elementos disjuntos X , Y de la zarza, debe existir un arco en D de X a Y y uno de Y a X . El orden de una zarza es el tamaño más pequeño de un conjunto de golpes , un conjunto de vértices de Dque tiene una intersección no vacía con cada uno de los elementos de la zarza. El número zarza de D es el orden máximo de una zarza en D . El número de zarza de un gráfico dirigido está dentro de un factor constante de su ancho de árbol dirigido.
En la teoría de grafos , una descomposición de ramas de un gráfico G no dirigido es una agrupación jerárquica de los bordes de G , representada por un árbol binario sin raíz T con los bordes de G como sus hojas. Al eliminar cualquier borde de T, se dividen los bordes de G en dos subgrafías, y el ancho de la descomposición es el número máximo de vértices compartidos de cualquier par de subgrafías formadas de esta manera. El branchwidth de G es la anchura mínima de cualquier rama-descomposición de G .
El ancho de rama está estrechamente relacionado con el ancho del árbol : para todos los gráficos, estos dos números están en un factor constante entre sí, y ambas cantidades pueden caracterizarse por menores prohibidos . Y al igual que con el ancho de árbol, muchos problemas de optimización de gráficos pueden resolverse eficientemente para gráficos de ancho de rama pequeño. Sin embargo, a diferencia del ancho de árbol, el ancho de rama de los gráficos planos puede calcularse exactamente, en tiempo polinómico . Las descomposiciones de rama y el ancho de rama también se pueden generalizar desde gráficos a matroides .
Definiciones [ editar ]
Un árbol binario sin raíz es un gráfico conectado no dirigido sin ciclos en el que cada nodo no hoja tiene exactamente tres vecinos. Una descomposición de rama puede representarse mediante un árbol binario T sin raíz , junto con una biyección entre las hojas de T y los bordes del gráfico dado G = ( V , E ). Si e es cualquier borde del árbol T , entonces quitando e de T lo divide en dos subárboles T 1 y T 2 . Esta partición de Ten subárboles induce una partición de los bordes asociados con las hojas de T en dos subgraphs G 1 y G 2 de G . Esta partición de G en dos subgrafos se llama separación electrónica .
El ancho de una separación electrónica es el número de vértices de G que inciden tanto en un borde de E 1 como en un borde de E 2 ; es decir, es el número de vértices que comparten los dos subgrafos G 1 y G 2 . El ancho de la descomposición de rama es el ancho máximo de cualquiera de sus separaciones electrónicas. El branchwidth de G es la anchura mínima de una rama-descomposición de G .
Relación con el ancho de árbol [ editar ]
Las descomposiciones de ramas de los gráficos están estrechamente relacionadas con las descomposiciones de los árboles , y el ancho de las ramas está estrechamente relacionado con el ancho de los árboles : las dos cantidades están siempre dentro de un factor constante entre sí. En particular, en el artículo en el que presentaron el ancho de rama, Neil Robertson y Paul Seymour [1] mostraron que para un gráfico G con ancho de árbol k y ancho de rama b > 1,
Ancho de talla [ editar ]
El ancho de talla es un concepto definido de manera similar al ancho de rama, excepto que los bordes se reemplazan por vértices y viceversa. Una descomposición de talla es un árbol binario no enraizado con cada hoja que representa un vértice en el gráfico original, y el ancho de un corte es el número (o peso total en un gráfico ponderado) de bordes que inciden en un vértice en ambos subárboles.
Los algoritmos de ancho de rama generalmente funcionan reduciendo a un problema de ancho de talla equivalente. En particular, el ancho de tallado del gráfico medial de un gráfico plano es exactamente el doble del ancho de la rama del gráfico original. [2]
Algoritmos y complejidad [ editar ]
Es NP-completo para determinar si una gráfica G tiene una rama-descomposición de anchura como máximo k , cuando G y K son ambos considerados como entradas al problema. [2] Sin embargo, los gráficos con ancho de rama máximo k forman una familia menor de gráficos cerrados , [3] de lo que se deduce que calcular el ancho de rama es manejable con parámetros fijos : existe un algoritmo para calcular descomposiciones de rama óptimas cuyo funcionamiento El tiempo, en gráficos de ancho de rama k para cualquier constante constante k , es lineal en el tamaño del gráfico de entrada. [4]
Para los gráficos planos , el ancho de rama puede calcularse exactamente en tiempo polinómico. Esto en contraste con el ancho de árbol para el cual la complejidad en los gráficos planos es un problema abierto bien conocido. [5] El algoritmo original para el ancho de rama plano, por Paul Seymour y Robin Thomas , tomó tiempo O ( n 2 ) en gráficos con n vértices, y su algoritmo para construir una descomposición de rama de este ancho tomó tiempo O ( n 4 ). [2] Esto luego se aceleró a O ( n 3 ). [6]
Al igual que con el ancho de árbol, el ancho de rama se puede usar como base de algoritmos de programación dinámica para muchos problemas de optimización de NP-hard, usando una cantidad de tiempo que es exponencial en el ancho del gráfico de entrada o matroide. [7] Por ejemplo, Cook y Seymour (2003) aplican la programación dinámica basada en el ancho de rama a un problema de fusionar múltiples soluciones parciales al problema del vendedor ambulante en una única solución global, formando un gráfico escaso a partir de la unión de las soluciones parciales, usando una heurística de agrupación espectral para encontrar una buena descomposición de ramas de este gráfico, y aplicando programación dinámica a la descomposición. Fomin y Thilikos (2006) argumentan que el ancho de rama funciona mejor que el ancho de árbol en el desarrollo de algoritmos manejables de parámetros fijos en gráficos planos, por múltiples razones: el ancho de rama puede estar más estrechamente limitado por una función del parámetro de interés que los límites de ancho de árbol, se puede calcular exactamente en tiempo polinómico en lugar de simplemente aproximado, y el algoritmo para calcularlo no tiene grandes constantes ocultas.
Generalización a matroides [ editar ]
También es posible definir una noción de descomposición de rama para matroides que generaliza la descomposición de rama de los gráficos. [8] Una descomposición de ramas de un matroide es una agrupación jerárquica de los elementos matroides, representada como un árbol binario sin raíz con los elementos del matroide en sus hojas. Un e-separación se puede definir de la misma manera que para los gráficos, y resulta en una partición del conjunto M de elementos matroid en dos subconjuntos A y B . Si ρ denota la función de rango del matroide, entonces el ancho de una separación electrónica se define como ρ ( A ) + ρ ( B ) - ρ ( M ) + 1, y el ancho de la descomposición y el ancho de rama del matroide se definen de manera análoga. El ancho de rama de un gráfico y el ancho de rama del matroide gráfico correspondiente pueden diferir: por ejemplo, el gráfico de ruta de tres bordes y la estrella de tres bordes tienen diferentes anchos de rama, 2 y 1 respectivamente, pero ambos inducen el mismo matroide gráfico con ancho de rama 1. [9] Sin embargo, para los gráficos que no son árboles, el ancho de rama del gráfico es igual al ancho de rama de su matroide gráfico asociado. [10] El ancho de rama de un matroide es igual al ancho de rama de su doble matroide, y en particular esto implica que el ancho de rama de cualquier gráfico plano que no sea un árbol es igual al de su dual. [9]
El ancho de rama es un componente importante de los intentos de extender la teoría de los gráficos menores a los matroides menores : aunque el ancho de árbol también puede generalizarse a los matroides, [11] y juega un papel más importante que el ancho de rama en la teoría de los gráficos menores, el ancho de rama tiene propiedades más convenientes en La configuración matroide. [12] Robertson y Seymour conjeturaron que los matroides representables sobre cualquier campo finito en particular están bien ordenados , de forma análoga al teorema de Robertson-Seymour para gráficos, pero hasta ahora esto se ha demostrado solo para los matroides de ancho de rama limitado. [13]Además, si una familia de matroides cerrados menores representables en un campo finito no incluye los matroides gráficos de todos los gráficos planos, entonces hay un límite constante en el ancho de rama de los matroides en la familia, generalizando resultados similares para el gráfico cerrado menor familias [14]
Para cualquier constante constante k , los matroides con ancho de rama máximo k pueden reconocerse en tiempo polinomial mediante un algoritmo que tiene acceso al matroide a través de un oráculo de independencia . [15]
Menores prohibidos [ editar ]
Según el teorema de Robertson-Seymour , las gráficas de ancho de rama k pueden caracterizarse por un conjunto finito de menores prohibidos . Las gráficas de branchwidth 0 son las coincidencias ; los menores prohibidos mínimos son un gráfico de ruta de dos bordes y un gráfico de triángulo (o el ciclo de dos bordes, si se consideran gráficos múltiples en lugar de gráficos simples). [16] Los gráficos del ancho de rama 1 son los gráficos en los que cada componente conectado es una estrella ; los menores prohibidos mínimos para el ancho de rama 1 son el gráfico de triángulo (o el ciclo de dos bordes, si se consideran gráficos múltiples en lugar de gráficos simples) y el gráfico de ruta de tres bordes. [dieciséis]Las gráficas de branchwidth 2 son las gráficas en las cuales cada componente conectado es una gráfica paralela en serie ; el único mínimo prohibido mínimo es el gráfico completo K 4 en cuatro vértices. [16] Un gráfico tiene un ancho de rama tres si y solo si tiene un ancho de árbol tres y no tiene el gráfico de cubo como menor; por lo tanto, los cuatro menores prohibidos mínimos son tres de los cuatro menores prohibidos para el ancho de árbol tres (el gráfico del octaedro , el gráfico completo K 5 y el gráfico de Wagner ) junto con el gráfico del cubo. [17]
Los menores prohibidos también se han estudiado para el ancho de rama matroide, a pesar de la falta de un análogo completo al teorema de Robertson-Seymour en este caso. Un matroide tiene un ancho de rama uno si y solo si cada elemento es un bucle o un coloop, por lo que el menor prohibido mínimo único es el matroide uniforme U (2,3), el matroide gráfico del gráfico triangular. Un matroide tiene un ancho de rama dos si y solo si es el matroide gráfico de un gráfico de ancho de rama dos, por lo que sus menores prohibidos mínimos son el matroide gráfico de K 4y el matroide no gráfico U (2,4). Los matroides de ancho de rama tres no están bien ordenados sin la suposición adicional de representabilidad sobre un campo finito, sin embargo, los matroides con cualquier límite finito en su ancho de rama tienen finitamente muchos menores prohibidos mínimos, todos los cuales tienen una serie de elementos que es como máximo exponencial en el ancho de rama.
No hay comentarios:
Publicar un comentario