En la teoría de grafos , el problema del ancho de banda del grafo es etiquetar los n vértices v i de un grafo G con enteros distintos f ( v i ) de modo que la cantidadse minimiza ( E es el conjunto de bordes de G ). [1] El problema se puede visualizar como colocar los vértices de una gráfica en puntos enteros distintos a lo largo del eje x de modo que la longitud del borde más largo se minimice. Esta ubicación se denomina disposición de gráfico lineal , diseño de gráfico lineal o ubicación de gráfico lineal . [2]
El problema del ancho de banda del gráfico ponderado es una generalización en la que a los bordes se les asignan pesos w ij y la función de costo a minimizar es.
En términos de matrices, el ancho de banda del gráfico (no ponderado) es el ancho de banda de la matriz simétrica que es la matriz de adyacencia del gráfico. El ancho de banda también puede definirse como uno menos que el tamaño máximo de la camarilla en un supergráfico de intervalo adecuado del gráfico dado, elegido para minimizar el tamaño de la camarilla ( Kaplan y Shamir 1996 ).
Fórmulas de ancho de banda para algunos gráficos
Para varias familias de gráficos, el ancho de banda viene dado por una fórmula explícita.
El ancho de banda de un gráfico de trayectoria P n en n vértices es 1, y para un gráfico completo K m tenemos. Para el gráfico bipartito completo K m , n ,
- , asumiendo
que fue probado por Chvátal. [3] Como caso especial de esta fórmula, el gráfico de estrellas en k + 1 vértices tiene ancho de banda.
Para el gráfico del hipercubo en vértices el ancho de banda fue determinado por Harper (1966) como
Chvatálová mostró [4] que el ancho de banda del gráfico de cuadrícula m × n , es decir, el producto cartesiano de dos grafos de trayectoria en y vértices, es igual a min { m , n }.
Límites
El ancho de banda de un gráfico se puede limitar en términos de varios otros parámetros del gráfico. Por ejemplo, dejando que χ ( G ) denote el número cromático de G ,
dejando que diam ( G ) denote el diámetro de G , se cumplen las siguientes desigualdades: [5]
dónde es el número de vértices en .
Si un gráfico G tiene un ancho de banda k , entonces su ancho de ruta es como máximo k ( Kaplan y Shamir 1996 ), y su profundidad de árbol es como máximo k log ( n / k ) ( Gruber 2012 ). En contraste, como se señaló en la sección anterior, el gráfico de estrella S k , un ejemplo estructuralmente muy simple de un árbol , tiene un ancho de banda comparativamente grande. Observe que el ancho de la ruta de S k es 1 y la profundidad de su árbol es 2.
Algunas familias de gráficos de grado acotado tienen ancho de banda sublineal: Chung (1988) demostró que si T es un árbol de grado máximo como máximo ∆, entonces
Más en general, para grafos planos de máximo grado limitado en la mayoría de Δ , una cota similar se mantiene (cf. Böttcher et al 2010. ):
Calcular el ancho de banda
Tanto la versión ponderada como la no ponderada son casos especiales del problema de asignación de cuello de botella cuadrático . El problema del ancho de banda es NP-hard , incluso para algunos casos especiales. [6] Con respecto a la existencia de algoritmos de aproximación eficientes , se sabe que el ancho de banda es NP-difícil de aproximar dentro de cualquier constante, y esto incluso se mantiene cuando los gráficos de entrada están restringidos a árboles de oruga con una longitud máxima de cabello 2 ( Dubey, Feige & Unger 2010 ). Para el caso de gráficos densos, Karpinski, Wirtgen & Zelikovsky (1997) diseñaron un algoritmo de 3 aproximaciones . Por otro lado, se conocen varios casos especiales con solución polinomial. [2] Un algoritmo heurístico para obtener diseños de gráficos lineales de ancho de banda bajo es el algoritmo de Cuthill-McKee . En [7] se propuso un algoritmo rápido multinivel para el cálculo del ancho de banda de gráficos.
Aplicaciones
El interés por este problema proviene de algunas áreas de aplicación.
Un área es el manejo de matriz dispersa / matriz de banda , y los algoritmos generales de esta área, como el algoritmo de Cuthill-McKee , pueden aplicarse para encontrar soluciones aproximadas para el problema del ancho de banda del gráfico.
Otro dominio de aplicación es la automatización del diseño electrónico . En la metodología de diseño de celdas estándar , normalmente las celdas estándar tienen la misma altura y su ubicación se organiza en varias filas. En este contexto, el problema del ancho de banda del gráfico modela el problema de la colocación de un conjunto de celdas estándar en una sola fila con el objetivo de minimizar el retardo de propagación máximo (que se supone que es proporcional a la longitud del cable).
Ver también
- Pathwidth , un problema de optimización NP-completo diferente que involucra diseños lineales de gráficos.
Referencias
- ^ ( Chinn et al. 1982 )
- ^ a b "Afrontar la dureza NP del problema del ancho de banda del gráfico", Uriel Feige, Lecture Notes in Computer Science , Volumen 1851, 2000, págs. 129-145, doi : 10.1007 / 3-540-44985-X_2
- ^ Un comentario sobre un problema de Harary. V. Chvátal, Checoslovaco Mathematical Journal 20 (1): 109-111, 1970. http://dml.cz/dmlcz/100949
- ^ Etiquetado óptimo de un producto de dos caminos. J. Chvatálová, Discrete Mathematics 11 , 249-253, 1975.
- ^ Chinn y col. mil novecientos ochenta y dos
- ^ Garey – Johnson: GT40
- ^ Ilya Safro y Dorit Ron y Achi Brandt (2008). "Algoritmos multinivel para problemas de ordenamiento lineal". Revista ACM de algoritmos experimentales . 13 : 1.4–1.20. doi : 10.1145 / 1412228.1412232 .
- Böttcher, J .; Pruessmann, KP; Taraz, A .; Würfl, A. (2010). "Ancho de banda, expansión, ancho de árbol, separadores y universalidad para gráficos de grados acotados". Revista europea de combinatoria . 31 (5): 1217-1227. arXiv : 0910.3014 . doi : 10.1016 / j.ejc.2009.10.010 .
- Chinn, PZ ; Chvátalová, J .; Dewdney, AK ; Gibbs, NE (1982). "El problema del ancho de banda para gráficos y matrices: una encuesta". Revista de teoría de grafos . 6 (3): 223-254. doi : 10.1002 / jgt.3190060302 .
- Chung, Fan RK (1988), "Etiquetado de gráficos", en Beineke, Lowell W .; Wilson, Robin J. (eds.), Temas seleccionados en teoría de grafos (PDF) , Academic Press, págs. 151-168, ISBN 978-0-12-086203-0
- Dubey, C .; Feige, U .; Unger, W. (2010). "Resultados de dureza para aproximar el ancho de banda". Revista de Ciencias de la Computación y Sistemas . 77 : 62–90. doi : 10.1016 / j.jcss.2010.06.006 .
- Garey, MR ; Johnson, DS (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . Nueva York: WH Freeman. ISBN 0-7167-1045-5.
- Gruber, Hermann (2012), "On Balanced Separators, Treewidth, and Cycle Rank", Journal of Combinatorics , 3 (4): 669–682, arXiv : 1012.1344 , doi : 10.4310 / joc.2012.v3.n4.a5
- Harper, L. (1966). "Numeraciones óptimas y problemas isoperimétricos en gráficas" . Revista de teoría combinatoria . 1 (3): 385–393. doi : 10.1016 / S0021-9800 (66) 80059-5 .
- Kaplan, Haim; Shamir, Ron (1996), "Problemas de ancho de ruta, ancho de banda y finalización para gráficos de intervalo adecuados con pequeños grupos", SIAM Journal on Computing , 25 (3): 540–561, doi : 10.1137 / s0097539793258143
- Karpinski, Marek; Wirtgen, Jürgen; Zelikovsky, Aleksandr (1997). "Un algoritmo de aproximación para el problema de ancho de banda en gráficos densos" . Coloquio electrónico sobre complejidad computacional . 4 (17).
enlaces externos
- Problema de ancho de banda mínimo , en: Pierluigi Crescenzi y Viggo Kann (eds.), Un compendio de problemas de optimización NP. Consultado el 26 de mayo de 2010.