En teoría de grafos , una descomposición en rama de un grafo no dirigido G es una agrupación jerárquica de las aristas de G , representada por un árbol binario sin raíz T con las aristas de G como sus hojas. Al eliminar cualquier arista de T, se dividen las aristas de G en dos subgrafos, y el ancho de la descomposición es el número máximo de vértices compartidos de cualquier par de subgrafos formados de esta manera. El ancho de rama de G es el ancho mínimo de cualquier descomposición en rama de G.
El ancho de rama está estrechamente relacionado con el ancho de árbol : para todos los grafos, ambos números están dentro de 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 grafos pueden resolverse de manera eficiente para grafos de ancho de rama pequeño. Sin embargo, a diferencia del ancho de árbol, el ancho de rama de grafos planares puede calcularse con exactitud, en tiempo polinomial . Las descomposiciones de rama y el ancho de rama también pueden generalizarse de grafos a matroides .
Un árbol binario sin raíz es un grafo conectado no dirigido sin ciclos en el que cada nodo que no es una hoja tiene exactamente tres vecinos. Una descomposición en ramas puede representarse mediante un árbol binario sin raíz T , junto con una biyección entre las hojas de T y las aristas del grafo dado G = ( V , E ). Si e es cualquier arista del árbol T , entonces al eliminar e de T se lo divide en dos subárboles T 1 y T 2 . Esta partición de T en subárboles induce una partición de las aristas asociadas con las hojas de T en dos subgrafos G 1 y G 2 de G . Esta partición de G en dos subgrafos se denomina e-separación .
El ancho de una e-separación es el número de vértices de G que inciden tanto en una arista de E 1 como en una arista 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 en rama es el ancho máximo de cualquiera de sus e-separaciones. El ancho de rama de G es el ancho mínimo de una descomposición en rama de G .
Las descomposiciones de ramas de grafos están estrechamente relacionadas con las descomposiciones de árboles , y el ancho de rama está estrechamente relacionado con el ancho de árbol : las dos cantidades están siempre dentro de un factor constante entre sí. En particular, en el artículo en el que introdujeron el ancho de rama, Neil Robertson y Paul Seymour [1] demostraron que para un grafo G con ancho de árbol k y ancho de rama b > 1,
El ancho de tallado es un concepto que se define de manera similar al ancho de rama, excepto que las aristas se reemplazan por vértices y viceversa. Una descomposición de tallado es un árbol binario sin raíz en el que cada hoja representa un vértice en el gráfico original, y el ancho de un corte es la cantidad (o el peso total en un gráfico ponderado) de aristas que inciden en un vértice en ambos subárboles.
Los algoritmos de ancho de rama generalmente funcionan reduciendo el problema a un ancho de tallado equivalente. En particular, el ancho de tallado del gráfico medial de un gráfico plano es exactamente el doble del ancho de rama del gráfico original. [2]
Es NP-completo determinar si un grafo G tiene una descomposición en ramas con un ancho de como máximo k , cuando G y k se consideran como entradas del problema. [2] Sin embargo, los grafos con un ancho de rama de como máximo k forman una familia de grafos menor-cerrada , [3] de lo que se deduce que el cálculo del ancho de rama es manejable con parámetros fijos : hay un algoritmo para calcular descomposiciones en ramas óptimas cuyo tiempo de ejecución, en grafos con un ancho de rama k para cualquier constante fija k , es lineal en el tamaño del grafo de entrada. [4]
Para los grafos planares , el ancho de rama se puede calcular exactamente en tiempo polinomial. Esto contrasta con el ancho de árbol para el cual la complejidad en grafos planares es un problema abierto bien conocido. [5] El algoritmo original para el ancho de rama plana, de Paul Seymour y Robin Thomas , tomó tiempo O( n 2 ) en grafos con n vértices, y su algoritmo para construir una descomposición de rama de este ancho tomó tiempo O( n 4 ). [2] Esto se aceleró más tarde a O( n 3 ). [6]
Al igual que con el ancho de árbol, el ancho de rama se puede utilizar como base de algoritmos de programación dinámica para muchos problemas de optimización NP-hard, utilizando una cantidad de tiempo que es exponencial en el ancho del gráfico o matroide de entrada. [7] Por ejemplo, Cook y Seymour (2003) aplican la programación dinámica basada en el ancho de rama a un problema de fusión de múltiples soluciones parciales al problema del viajante de comercio en una única solución global, formando un gráfico disperso a partir de la unión de las soluciones parciales, utilizando una heurística de agrupamiento espectral para encontrar una buena descomposición de rama de este gráfico y aplicando programación dinámica a la descomposición. Fomin y Thilikos (2006) sostienen que el ancho de rama funciona mejor que el ancho de árbol en el desarrollo de algoritmos manejables con parámetros fijos en gráficos planares, 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 del ancho de árbol, se puede calcular exactamente en tiempo polinomial en lugar de simplemente aproximarlo, y el algoritmo para calcularlo no tiene grandes constantes ocultas.
También es posible definir una noción de descomposición en ramas para matroides que generaliza las descomposiciones en ramas de grafos. [8] Una descomposición en ramas de un matroide es una agrupación jerárquica de los elementos del matroide, representada como un árbol binario sin raíz con los elementos del matroide en sus hojas. Una e-separación puede definirse de la misma manera que para los grafos, y da como resultado una partición del conjunto M de elementos del matroide en dos subconjuntos A y B . Si ρ denota la función de rango del matroide, entonces el ancho de una e-separación 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 grafo y el ancho de rama del matroide gráfico correspondiente pueden diferir: por ejemplo, el grafo de ruta de tres aristas y la estrella de tres aristas 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 grafos que no son árboles, el ancho de rama del grafo 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 matroide dual , y en particular esto implica que el ancho de rama de cualquier grafo planar 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 menores de grafos a los menores de matroides : aunque el ancho de árbol también se puede generalizar a los matroides, [11] y juega un papel más importante que el ancho de rama en la teoría de los menores de grafos, el ancho de rama tiene propiedades más convenientes en el entorno de los matroides. [12] Robertson y Seymour conjeturaron que los matroides representables sobre cualquier cuerpo finito particular están bien cuasi ordenados , análogamente al teorema de Robertson-Seymour para grafos, pero hasta ahora esto se ha demostrado solo para los matroides de ancho de rama acotado. [13] Además, si una familia de matroides menor-cerrada representables sobre un cuerpo finito no incluye los matroides gráficos de todos los grafos planares, entonces hay un límite constante en el ancho de rama de los matroides en la familia, generalizando resultados similares para familias de grafos menor-cerrados. [14]
Para cualquier constante fija k , los matroides con ancho de rama como máximo k pueden ser reconocidos en tiempo polinomial por un algoritmo que tiene acceso al matroide a través de un oráculo de independencia . [15]
Por el teorema de Robertson-Seymour , los grafos de ancho de rama k pueden caracterizarse por un conjunto finito de menores prohibidos . Los grafos de ancho de rama 0 son los emparejamientos ; los menores prohibidos mínimos son un grafo de trayectoria de dos aristas y un grafo triangular (o el ciclo de dos aristas, si se consideran multigrafos en lugar de grafos simples). [16] Los grafos de ancho de rama 1 son los grafos en los que cada componente conexo es una estrella ; los menores prohibidos mínimos para el ancho de rama 1 son el grafo triangular (o el ciclo de dos aristas, si se consideran multigrafos en lugar de grafos simples) y el grafo de trayectoria de tres aristas. [16] Los grafos de ancho de rama 2 son los grafos en los que cada componente biconectado es un grafo serie-paralelo ; el único menor prohibido mínimo es el grafo completo K 4 en cuatro vértices. [16] Un grafo tiene ancho de rama tres si y solo si tiene ancho de árbol tres y no tiene el grafo cúbico 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 grafo del octaedro , el grafo completo K 5 y el grafo de Wagner ) junto con el grafo cúbico. [17]
También se han estudiado menores prohibidos para el ancho de rama de los matroides, a pesar de la falta de un análogo completo del 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 único menor prohibido mínimo es el matroide uniforme U(2,3), el matroide gráfico del grafo triangular. Un matroide tiene un ancho de rama dos si y solo si es el matroide gráfico de un grafo de ancho de rama dos, por lo que sus menores prohibidos mínimos son el matroide gráfico de K 4 y el matroide no gráfico U(2,4). Los matroides de ancho de rama tres no están bien ordenados cuasi sin el supuesto adicional de representabilidad sobre un cuerpo finito, pero sin embargo los matroides con cualquier límite finito en su ancho de rama tienen un número finito de menores prohibidos mínimos, todos los cuales tienen un número de elementos que es como máximo exponencial en el ancho de rama. [18]
problema abierto desde hace mucho tiempo es si existe un algoritmo de tiempo polinomial para calcular el ancho de árbol de los gráficos planares.
{{citation}}: CS1 maint: DOI inactivo a partir de noviembre de 2024 ( enlace )