Ancho de banda del gráfico

Problema de etiquetado de nodos en teoría de grafos

En teoría de grafos , el problema del ancho de banda del gráfico es etiquetar los n vértices vi _de un gráfico G con números enteros distintos para que la cantidad se minimice ( E es el conjunto de aristas de G ). ^[1] El problema puede visualizarse como colocar los vértices de un gráfico en distintos puntos enteros a lo largo del eje x de modo que se minimice la longitud del borde más largo. Esta ubicación se denomina disposición de gráficos lineales , diseño de gráficos lineales o ubicación de gráficos lineales . ^[2] ${\displaystyle f(v_{i})}$ ${\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$

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 . ${\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$

En términos de matrices, el ancho de banda del gráfico (no ponderado) es el ancho de banda mínimo de una matriz simétrica que es una matriz de adyacencia del gráfico. El ancho de banda también se puede definir como uno menos que el tamaño máximo de camarilla en un supergrafo de intervalo adecuado del gráfico dado, elegido para minimizar su tamaño de 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. ${\displaystyle \varphi (G)}$

El ancho de banda de un gráfico de ruta 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} , ${\displaystyle \varphi (K_{n})=n-1}$

${\displaystyle \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n}$, asumiendo ${\displaystyle m\geq n\geq 1,}$

lo cual fue demostrado 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 . ${\displaystyle S_{k}=K_{k,1}}$ ${\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}$

Para el gráfico de hipercubo en vértices, Harper (1966) determinó que el ancho de banda era ${\displaystyle Q_{n}}$ ${\displaystyle 2^{n}}$

${\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}$

Chvatálová demostró ^[4] que el ancho de banda del gráfico de cuadrícula cuadrada m  ×  n , es decir, el producto cartesiano de dos gráficos de trayectoria en y vértices, es igual a min{ m , n }. ${\displaystyle P_{m}\times P_{n}}$ ${\displaystyle m}$ ${\displaystyle 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 ,

${\displaystyle \varphi (G)\geq \chi (G)-1;}$

Si diam( G ) denota el diámetro de G , se cumplen las siguientes desigualdades: ^[5]

${\displaystyle \lceil (n-1)/\operatorname {diam} (G)\rceil \leq \varphi (G)\leq n-\operatorname {diam} (G),}$

¿Dónde está el número de vértices en ? ${\displaystyle n}$ ${\displaystyle G}$

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 la profundidad de su árbol es como máximo k  log ( n / k ) (Gruber 2012). Por el contrario, como se señaló en la sección anterior, el gráfico estelar S _k , un ejemplo estructuralmente muy simple de árbol , tiene un ancho de banda comparativamente grande. Observe que el ancho de ruta de S _k es 1 y la profundidad de su árbol es 2.

Algunas familias de gráficos de grado acotado tienen un ancho de banda sublineal: Chung (1988) demostró que si T es un árbol de grado máximo como máximo ∆, entonces

${\displaystyle \varphi (T)\leq {\frac {5n}{\log _{\Delta }n}}.}$

De manera más general, para gráficos planos de grado máximo acotado como máximo ∆ , se cumple un límite similar (cf. Böttcher et al. 2010):

${\displaystyle \varphi (G)\leq {\frac {20n}{\log _{\Delta }n}}.}$

Calcular el ancho de banda

Tanto la versión ponderada como la no ponderada son casos especiales del problema de asignación de cuellos de botella cuadráticos . El problema del ancho de banda es NP-duro , incluso en 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 se cumple incluso cuando los gráficos de entrada están restringidos a árboles de orugas con una longitud máxima de pelo de 2 (Dubey, Feige & Unger 2010). Para el caso de gráficos densos, Karpinski, Wirtgen y Zelikovsky (1997) diseñaron un algoritmo de 3 aproximaciones. Por otro lado, se conocen varios casos especiales que pueden resolverse polinómicamente. ^[2] Un algoritmo heurístico para obtener diseños de gráficos lineales de bajo ancho de banda es el algoritmo 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 matrices dispersas / matriz de bandas , y se pueden aplicar algoritmos generales de esta área, como el algoritmo Cuthill-McKee , 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 está dispuesta en varias filas. En este contexto, el problema del ancho de banda del gráfico modela el problema de colocación de un conjunto de celdas estándar en una sola fila con el objetivo de minimizar el retraso de propagación máximo (que se supone que es proporcional a la longitud del cable).

Ver también

• Cutwidth y pathwidth , diferentes problemas de optimización NP-completa que involucran diseños lineales de gráficos.

Referencias

1. (Chinn y otros 1982)
2. "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
3. Un comentario sobre un problema de Harary. V. Chvátal, Checoslovak Mathematical Journal 20 (1):109–111, 1970. http://dml.cz/dmlcz/100949
4. Etiquetado óptimo de un producto de dos caminos. J. Chvatálová, Matemáticas discretas 11 , 249–253, 1975.
5. Chinn y col. mil novecientos ochenta y dos
6. Garey-Johnson: GT40
7. Ilya Safro, Dorit Ron y Achi Brandt (2008). "Algoritmos multinivel para problemas de ordenamiento lineal". Revista ACM de algorítmica experimental . 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, Alaska ; 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), "Etiquetados 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 de Sistemas . 77 : 62–90. doi : 10.1016/j.jcss.2010.06.006 .
• Garey, señor ; Johnson, DS (1979). Computadoras e intratabilidad: una guía para la teoría de la integridad NP . Nueva York: WH Freeman. ISBN 0-7167-1045-5.
• Gruber, Hermann (2012), "Sobre separadores equilibrados, ancho de árbol y rango de ciclo", Journal of Combinatorics , 3 (4): 669–682, arXiv : 1012.1344 , doi :10.4310/joc.2012.v3.n4.a5
• Harper, L. (1966). "Numeración óptima y problemas isoperimétricos en gráficos". 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 intervalos adecuados con pequeñas camarillas", 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 del 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 de NP. Consultado el 26 de mayo de 2010.