Ancho de banda del gráfico

En teoría de grafos , el problema del ancho de banda de un grafo puede visualizarse como la colocación de los vértices de un grafo dado en posiciones enteras distintas a lo largo de la recta numérica de manera que se minimice la longitud de la arista más larga. Dicha colocación se denomina disposición lineal de grafos , disposición lineal de grafos o colocación lineal de grafos . ^{[ 1 ]} Puede formalizarse como el etiquetado de los vértices.${\displaystyle n}$vértices${\displaystyle v_{i}}$de un gráfico${\displaystyle G}$con números enteros distintos${\displaystyle f(v_{i})}$para que la cantidad${\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}}$se minimiza, donde${\displaystyle E}$es el conjunto de aristas de${\displaystyle G}$. ^{[ 2 ]}

El problema del ancho de banda de grafos ponderados es una generalización en la que se asignan pesos a las aristas.${\displaystyle w_{ij}}$y la función de coste que se debe minimizar es el producto del peso por la longitud,${\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 grafo (sin ponderación) 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 la camarilla en un supergrafo de intervalo propio del grafo dado, elegido para minimizar su tamaño de camarilla. ^{[ 3 ]}

Para varias familias de gráficos, el ancho de banda${\displaystyle \varphi (G)}$se da mediante una fórmula explícita.

El ancho de banda de un grafo de ruta${\displaystyle P_{n}}$en${\displaystyle n}$vértices es  1, y el ancho de banda de un grafo completo${\displaystyle K_{m}}$es${\displaystyle \varphi (K_{n})=n-1}$Para el grafo bipartito completo${\displaystyle K_{m,n}}$, $${\displaystyle \varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n,}$$arrogante${\displaystyle m\geq n\geq 1}$Como caso especial de esta fórmula, el gráfico de estrellas${\displaystyle S_{k}=K_{k,1}}$en${\displaystyle k+1}$vértices tiene ancho de banda${\displaystyle \varphi (S_{k})=\lfloor (k-1)/2\rfloor +1}$. ^{[ 4 ]}

Para el grafo hipercubo${\displaystyle Q_{n}}$en${\displaystyle 2^{n}}$vértices el ancho de banda es ^{[ 5 ]}$${\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}$$

El ancho de banda del${\displaystyle m\times n}$gráfico de cuadrícula cuadrada${\displaystyle P_{m}\times P_{n}}$, es decir, el producto cartesiano de dos grafos de caminos en${\displaystyle m}$y${\displaystyle n}$vértices, es igual a${\displaystyle \min\{m,n\}}$. ^{[ 6 ]}

El ancho de banda de un grafo puede estar acotado en términos de varios otros parámetros del grafo. Por ejemplo, sea χ( G ) el número cromático de G ,

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

Sea diam( G ) el diámetro de G , se cumplen las siguientes desigualdades: ^{[ 2 ]}

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

dónde${\displaystyle n}$es el número de vértices en${\displaystyle G}$.

Si un grafo G tiene un ancho de banda k , entonces su ancho de camino es como máximo k , ^{[ 3 ]} y su profundidad de árbol es como máximo k  log( n / k ). ^{[ 7 ]} En contraste, como se señaló en la sección anterior, el grafo estrella S _k , un ejemplo estructuralmente muy simple de un árbol , tiene un ancho de banda comparativamente grande. Nótese que el ancho de camino de S _k es  1 y su profundidad de árbol es  2.

Algunas familias de grafos de grado acotado tienen ancho de banda sublineal: si T es un árbol de grado máximo como máximo ∆, entonces ^{[ 8 ]}

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

De manera más general, para grafos planares de grado máximo acotado como máximo ∆ , se cumple una cota similar: ^{[ 9 ]}

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

Tanto la versión sin ponderar como la ponderada son casos especiales del problema de asignación de cuello de botella cuadrático . El problema del ancho de banda es NP-difícil , incluso para algunos casos especiales. ^{[ 10 ]} 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 grafos de entrada están restringidos a árboles oruga con una longitud máxima de pelo de 2. ^{[ 11 ]} Para grafos arbitrarios con${\displaystyle n}$vértices, la mejor relación de aproximación conocida es${\displaystyle O(\log ^{3}n{\sqrt {\log \log n}})}$, utilizando programación semidefinida . ^{[ 12 ]} Para el caso de grafos densos, se conoce un algoritmo de aproximación 3. ^{[ 13 ]} Por otro lado, se conocen varios casos especiales resolubles polinomialmente. ^{[ 1 ]} Un algoritmo heurístico para obtener diseños de grafos lineales de bajo ancho de banda es el algoritmo de Cuthill-McKee . En ^{[ 14 ]} se propuso un algoritmo multinivel rápido para el cálculo del ancho de banda de grafos.

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

Un área de aplicación es el manejo de matrices dispersas / matrices de banda , y se pueden aplicar algoritmos generales de esta área, como el algoritmo de Cuthill-McKee , para encontrar soluciones aproximadas para el problema del ancho de banda de grafos.

Otro ámbito de aplicación se encuentra en la automatización del diseño electrónico . En la metodología de diseño de celdas estándar , estas suelen tener la misma altura y se disponen en varias filas. En este contexto, el problema del ancho de banda de grafos modela la colocación de un conjunto de celdas estándar en una sola fila con el objetivo de minimizar el retardo máximo de propagación (que se supone proporcional a la longitud del cable).

• Cutwidth y pathwidth son problemas de optimización NP-completos diferentes que involucran diseños lineales de grafos.

• Problema de ancho de banda mínimo , en: Pierluigi Crescenzi y Viggo Kann (eds.), Compendio de problemas de optimización NP. Consultado el 26 de mayo de 2010.