ancho de corte

En teoría de grafos , el ancho de corte de un grafo no dirigido es el entero más pequeño${\displaystyle k}$con la siguiente propiedad: existe un ordenamiento de los vértices del grafo, tal que cada corte obtenido al particionar los vértices en subconjuntos anteriores y posteriores del ordenamiento es cruzado por como máximo${\displaystyle k}$aristas. Es decir, si los vértices están numerados${\displaystyle v_{1},v_{2},\dots v_{n}}$, entonces para cada${\displaystyle \ell =1,2,\dots n-1}$, el número de aristas${\displaystyle v_{i}v_{j}}$con${\displaystyle i\leq \ell }$y${\displaystyle j>\ell }$es como máximo${\displaystyle k}$. ^{[ 1 ]}

El ancho de corte de un grafo también se ha denominado su número de plegado . ^{[ 1 ]} Tanto el ordenamiento de vértices que produce el ancho de corte, como el problema de calcular este ordenamiento y el ancho de corte, se han denominado arreglo lineal de corte mínimo . ^{[ 2 ]}

El ancho de corte está relacionado con varios otros parámetros de ancho de los grafos. En particular, siempre es al menos tan grande como el ancho del árbol o el ancho del camino del mismo grafo. Sin embargo, es como máximo el ancho del camino multiplicado por${\displaystyle O(\Delta )}$o el ancho del árbol multiplicado por${\displaystyle O(\Delta \log n)}$dónde${\displaystyle \Delta }$es el grado máximo y${\displaystyle n}$es el número de vértices. ^{[ 3 ] [ 4 ]} Si una familia de grafos tiene grado máximo acotado y sus grafos no contienen subdivisiones de árboles binarios completos de tamaño ilimitado, entonces los grafos de la familia tienen ancho de corte acotado. ^{[ 4 ]} En grafos subcúbicos (grafos de grado máximo tres), el ancho de corte es igual al ancho de camino más uno. ^{[ 5 ]}

El ancho de corte es mayor o igual que el número mínimo de bisección de cualquier grafo. Este es el número mínimo posible de aristas de un lado a otro para una partición de los vértices en dos subconjuntos de igual tamaño (o lo más parecido posible). Cualquier disposición lineal de un grafo, que alcance su ancho de corte óptimo, también proporciona una bisección con el mismo número de aristas, obtenida al particionar la disposición en su primera y segunda mitad. El ancho de corte es menor o igual que el grado máximo multiplicado por el ancho de banda del grafo , el número máximo de pasos que separan los puntos finales de cualquier arista en una disposición lineal elegida para minimizar esta cantidad. ^{[ 6 ]} A diferencia del ancho de banda, el ancho de corte no cambia cuando las aristas se subdividen en caminos de más de una arista. Está estrechamente relacionado con el "ancho de banda topológico", el ancho de banda mínimo que se puede obtener al subdividir las aristas de un grafo dado. En particular, para cualquier árbol está intercalado entre el ancho de banda topológico.${\displaystyle b^{*}}$y un número ligeramente mayor,${\displaystyle b^{*}+\log _{2}b^{*}+2}$. ^{[ 1 ]}

Otro parámetro, definido de forma similar al ancho de corte en términos del número de aristas que abarcan cortes en un grafo, es el ancho de tallado . Sin embargo, en lugar de utilizar un ordenamiento lineal de vértices y una secuencia lineal de cortes, como en el caso del ancho de corte, el ancho de tallado utiliza cortes derivados de una agrupación jerárquica de vértices, lo que lo relaciona más estrechamente con el ancho de árbol o el ancho de rama y lo hace menos similar a otros parámetros de ancho que implican ordenamientos lineales como el ancho de ruta o el ancho de banda. ^{[ 7 ]}

El ancho de corte se puede utilizar para proporcionar una cota inferior para otro parámetro, el número de cruces , que surge en el estudio de los dibujos de grafos . El número de cruces de un grafo es el número mínimo de pares de aristas que se intersecan, en cualquier dibujo del grafo en el plano donde cada vértice toca solo las aristas para las que es un extremo. En grafos de grado acotado, el número de cruces es siempre al menos proporcional al cuadrado del ancho de corte. Una cota más precisa, aplicable a grafos donde los grados no están acotados, es: ^{[ 8 ]}$${\displaystyle \operatorname {crossings} (G)\geq {\frac {1}{1176}}\operatorname {cutwidth} (G)^{2}-\sum _{v\in V(G)}\left({\frac {\deg(v)}{4}}\right)^{2}.}$$ Aquí, el término de corrección, proporcional a la suma de los grados al cuadrado, es necesario para tener en cuenta la existencia de grafos planares cuyo ancho de corte al cuadrado es proporcional a esta cantidad, pero cuyo número de cruces es cero. ^{[ 8 ]} En otro estilo de dibujo de grafos, la incrustación de libro , los vértices se disponen en una línea y las aristas se disponen sin cruces en páginas de semiplano separadas que se encuentran en esta línea. El ancho de página de una incrustación de libro se ha definido como el mayor ancho de corte de cualquiera de las páginas, utilizando el mismo ordenamiento de vértices. ^{[ 9 ]}

El ancho de corte se puede encontrar y construir un diseño lineal de ancho óptimo, en el tiempo${\displaystyle O(n\log n)}$para un árbol de${\displaystyle n}$vértices. ^{[ 10 ]} Para grafos más generales, es NP-difícil . Sigue siendo NP-difícil incluso para grafos planares de grado máximo tres, y una versión ponderada del problema (minimizar el peso de las aristas a través de cualquier corte de una disposición lineal) es NP-difícil incluso cuando la entrada es un árbol. ^{[ 11 ]}

El ancho de corte es uno de los muchos problemas de disposición lineal óptima que se pueden resolver exactamente en tiempo${\displaystyle O(n2^{n})}$mediante el algoritmo de Held-Karp , utilizando programación dinámica . ^{[ 12 ]} Un algoritmo cuántico más rápido con tiempo${\displaystyle O(1.817^{n})}$También se sabe. ^{[ 13 ]} Además, es tratable con parámetros fijos : para cualquier valor fijo de${\displaystyle c}$, es posible comprobar si un gráfico tiene un ancho de corte como máximo${\displaystyle c}$y, de ser así, encontrar un ordenamiento óptimo de vértices para ello, en tiempo lineal . ^{[ 2 ]} Más precisamente, en términos de ambos${\displaystyle n}$y${\displaystyle c}$, el tiempo de ejecución de este algoritmo es${\textstyle 2^{O(c^{2})}n}$. ^{[ 14 ]} Un algoritmo parametrizado alternativo, más adecuado para grafos en los que un pequeño número de vértices tienen un grado alto (lo que hace que el ancho de corte sea grande), resuelve el problema en tiempo polinomial en${\displaystyle n}$Cuando el grafo tiene una cobertura de vértices de tamaño limitado, se transforma en un problema de programación entera con pocas variables y límites polinomiales en los valores de las variables. Queda por resolver si el problema puede resolverse eficientemente para grafos de ancho de árbol limitado, lo que englobaría ambas parametrizaciones por ancho de corte y número de cobertura de vértices. ^{[ 15 ]}

Cutwidth tiene un esquema de aproximación de tiempo polinomial para grafos densos , ^{[ 16 ]} pero para grafos que podrían no ser densos, la mejor razón de aproximación conocida es${\textstyle O{\bigl (}(\log n)^{3/2}{\bigr )}}$. ^{[ 17 ]} Esto proviene de un método de Tom Leighton y Satish Rao para reducir el ancho de corte aproximado al número mínimo de bisección, perdiendo un factor de${\displaystyle \log _{2}n}$en la razón de aproximación, usando bisección recursiva para ordenar los vértices. ^{[ 18 ]} Combinando este método de bisección recursiva con otro método de Sanjeev Arora , Rao y Umesh Vazirani para aproximar el número mínimo de bisección, ^{[ 19 ]} da la razón de aproximación indicada. ^{[ 17 ]} Bajo la hipótesis de expansión de conjuntos pequeños , no es posible lograr una razón de aproximación constante. ^{[ 17 ]}

Un problema de enrutamiento de canales, en el que pares de pines numerados deben conectarse a lo largo de "canales" horizontales en un área rectangular.

Solución que utiliza cinco canales

Una de las primeras aplicaciones que impulsaron el uso del ancho de corte fue el enrutamiento de canales en el diseño VLSI , donde los componentes dispuestos en la parte superior e inferior de una región rectangular de un circuito integrado deben conectarse mediante conductores que unen pares de pines unidos a los componentes. Si los componentes pueden ordenarse libremente de izquierda a derecha, pero los pines de cada componente deben permanecer contiguos, esto se traduce en un problema de elección de una disposición lineal de un grafo con un vértice para cada componente y una arista para cada conexión pin a pin. El ancho de corte del grafo controla la cantidad de canales necesarios para enrutar el circuito. ^{[ 5 ]}

En ingeniería de proteínas , se ha utilizado la suposición de que un grafo asociado tiene un ancho de corte limitado para acelerar la búsqueda de secuencias de ARNm que codifiquen simultáneamente una secuencia de proteína dada y se plieguen en una estructura secundaria dada . ^{[ 20 ]}

Una variante ponderada del problema, aplicada a grafos dirigidos acíclicos y que solo permite ordenaciones lineales consistentes con la orientación de las aristas del grafo, se ha aplicado para programar una secuencia de tareas computacionales de manera que se minimice la cantidad máxima de memoria requerida en la programación, tanto para las tareas en sí como para mantener los datos utilizados para la comunicación entre tareas. ^{[ 21 ]} En la teoría de bases de datos , la NP-dificultad del problema del ancho de corte se ha utilizado para demostrar que también es NP-difícil programar la transferencia de bloques de datos entre un disco y la memoria principal al realizar una unión , con el fin de evitar transferencias repetidas del mismo bloque mientras se ajusta el cálculo a una cantidad limitada de memoria principal. ^{[ 22 ]}

En el dibujo de grafos , además de aplicarse en la cota inferior para el número de cruces, ^{[ 8 ]} el ancho de corte se ha aplicado en el estudio de un tipo específico de dibujo de grafos tridimensionales, en el que las aristas se representan como cadenas poligonales disjuntas con como máximo una curvatura, los vértices se colocan en una línea y todos los vértices y puntos de curvatura deben tener coordenadas enteras. Para dibujos de este tipo, el volumen mínimo de una caja delimitadora del dibujo debe ser al menos proporcional al ancho de corte multiplicado por el número de vértices. Siempre existe un dibujo con este volumen, con los vértices colocados en una línea paralela a los ejes. ^{[ 23 ]}