Ancho de banda gráfico

---

En la teoría de grafos , el problema del ancho de banda del gráfico consiste en etiquetar los n vértices vi de un gráfico G con enteros distintos f (vi ) para _{que la} cantidad se minimice ( E es el conjunto de aristas de G ). ^[1] El problema se puede visualizar colocando 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. Tal ubicación se denomina disposición de gráficos lineales , disposición de gráficos lineales o ubicación de gráficos lineales .${\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\en E\,\}}$^[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 _wij y la función de costo a minimizar es .${\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\en 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 la camarilla en un supergráfico de intervalo adecuado del gráfico dado, elegido para minimizar el tamaño de la camarilla ( Kaplan & Shamir 1996 ).

Para varias familias de gráficos, el ancho de banda viene dado por una fórmula explícita.${\ estilo de visualización \ 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} ,${\ estilo de visualización \ varphi (K_ {n}) = n-1}$

lo cual fue probado por Chvátal. ^[3] Como caso especial de esta fórmula, el gráfico de estrellas en k  + 1 vértices tiene un ancho de banda .${\displaystyle S_{k}=K_{k,1}}$${\displaystyle \varphi (S_{k})=\lpiso (k-1)/2\rpiso +1}$

---