Ancho de banda del gráfico

Problema de etiquetado de nodos en la teoría de grafos

En teoría de grafos , el problema del ancho de banda del grafo consiste en etiquetar los n vértices v _i de un grafo G con números enteros distintos de ${\displaystyle f(v_{i})}$ modo que la cantidad se minimice ( E es el conjunto de aristas de G ). ^[1] El problema puede visualizarse como la colocación de los vértices de un grafo en puntos enteros distintos a lo largo del eje x de modo que se minimice la longitud de la arista más larga. Tal colocación se denomina disposición de grafos lineales , diseño de grafos lineales o colocación de grafos lineales . ^[2] ${\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 (no ponderado) del grafo es el ancho de banda mínimo de una matriz simétrica que es una matriz de adyacencia del grafo. El ancho de banda también puede definirse como uno menos que el tamaño máximo de grupo en un supergrafo de intervalo adecuado del grafo dado, elegido para minimizar su tamaño de grupo (Kaplan y Shamir 1996).

Gráficas de intervalos cíclicos

Para definir de forma fija para cada conjunto . es el gráfico de intervalo correspondiente formado a partir de los intervalos . Estos son exactamente los gráficos de intervalo adecuados de los gráficos que tienen un ancho de banda . Estos gráficos se denominan gráficos de intervalo cíclicos porque los intervalos se pueden asignar a capas en orden cíclico, donde los intervalos de una capa no se cruzan. ${\displaystyle k}$ ${\displaystyle i}$ ${\displaystyle I_{k}(i):=[i,i+k+1)}$ ${\displaystyle G_{k}(n)}$ ${\displaystyle I_{k}(1),I_{k}(2),...I_{k}(n)}$ ${\displaystyle k}$ ${\displaystyle L_{1},L_{2},...L_{k+1}}$

Por lo tanto, se observa la relación con el ancho de ruta . Los grafos con ancho de ruta restringido son cerrados menores, pero el conjunto de subgrafos de grafos de intervalo cíclico no lo son. Esto se deduce del hecho de que reducir los vértices de grado 2 puede aumentar el ancho de banda.

La adición alternada de vértices en los bordes puede reducir el ancho de banda. Sugerencia: El último problema se conoce como ancho de banda topológico . Otra medida gráfica relacionada con el ancho de banda es el ancho de banda de bisección .

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 grafo de trayectoria P _n en n vértices es 1, y para un grafo completo K _m tenemos . Para el grafo 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 estrella 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 función de otros parámetros gráficos. Por ejemplo, si χ( G ) denota el número cromático de G ,

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

siendo diam( G ) 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 grafo 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). Por el contrario, como se señaló en la sección anterior, el grafo en estrella S _k , un ejemplo estructuralmente muy simple de un árbol , tiene un ancho de banda comparativamente grande. Observe que el ancho de ruta de S _k es 1, y su profundidad de á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

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

De manera más general, para gráficos planares 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}}.}$

Calculando el ancho de banda

Tanto las versiones no ponderadas como las ponderadas son casos especiales del problema de asignación de cuello de botella cuadrático . El problema del ancho de banda es NP-duro , 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-duro de aproximar dentro de cualquier constante, y esto incluso se cumple cuando los gráficos de entrada están restringidos a árboles de oruga con una longitud máxima de pelo de 2 (Dubey, Feige y 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 se pueden resolver polinomialmente. ^[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 multinivel rápido para el cálculo del ancho de banda de gráficos.

Aplicaciones

El interés en este problema proviene de algunas áreas de aplicación.

Un área es el manejo de matrices dispersas / matrices de banda , 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 campo 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 colocación se organiza en varias filas. En este contexto, el problema del ancho de banda de grafos 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).

Véase también

• Ancho de corte y ancho de ruta , diferentes problemas de optimización NP-completos que involucran diseños lineales de gráficos.

Referencias

1. (Chinn y otros, 1982)
2. "Cómo afrontar la NP-dureza del problema del ancho de banda del grafo", 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á, Discrete Mathematics 11 , 249–253, 1975.
5. Chinn y otros 1982
6. Garey–Johnson: GT40
7. Ilya Safro y Dorit Ron y Achi Brandt (2008). "Algoritmos multinivel para problemas de ordenamiento lineal". ACM Journal of Experimental Algorithmics . 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 grafos de grado acotado". 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 revisión". Journal of Graph Theory . 6 (3): 223–254. doi :10.1002/jgt.3190060302.
• Chung, Fan RK (1988), "Etiquetado de grafos", 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". Journal of Computer and System Sciences . 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 la NP-completitud . 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). "Numeraciones óptimas y problemas isoperimétricos en grafos". Journal of Combinatorial Theory . 1 (3): 385–393. doi : 10.1016/S0021-9800(66)80059-5 .
• Kaplan, Haim; Shamir, Ron (1996), "Problemas de ancho de banda, ancho de ruta y completitud para gráficos de intervalos adecuados con camarillas pequeñas", 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.), A compendium of NP optimized problems. Consultado el 26 de mayo de 2010.