# Largura de banda de grafos

Em teoria dos grafos, o problema da Largura de Banda de Grafos é rotular os n vértices v$_i$ de um grafo G com inteiros distintos f(v$_i$), de modo que a quantidade $\max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}$ é minimizada (E é o conjunto de arestas de G). O problema pode ser visualizado como colocar os vértices de um grafo em pontos inteiros distintos ao longo de x-eixos, de modo que o comprimento da maior banda é minimizada. Tal atribuição é chamada arranjos de grafos lineares, esboço de grafos lineares ou atribuição de grafos lineares.
O problema da Largura de Banda de Grafos com peso é a generalização em que as arestas são pesos atribuídos w$_{ij}$ e a função de custo para ser minimizada é $\max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}$.
Em termos de matrizes, a Largura de Banda de Grafos (sem peso) é a largura de banda da matriz simétrica que é a matriz de adjacência do grafo. A largura de banda também pode ser definida como uma menor que o tamanho do clique em um supergrafo de intervalo adequado do grafo dado, escolhido para minimizar seu tamanho de clique (Kaplan & Shamir 1996).

## Fórmulas de largura de banda para alguns grafos

Para várias famílias de grafos, a largura de banda $\varphi (G)$ é dada por uma fórmula explícita.
A largura de banda de um caminho em um grafo $P_{n}$ sobre n vértices é $1$, e para um grafo completo $K_{m}$, temos $\varphi (K_{n})=n-1$. Para o Grafo bipartido completo $K_{m,n},$
    $\varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n$, assumindo $m\geq n\geq 1$, a qual foi provada por Chvátal. Como um caso especial dessa fórmula, o grafo estrela $S_{k}=K_{k,1}$ em k+1 vértices tem largura de banda $\varphi (S_{k})=\lfloor (k-1)/2\rfloor +1$.
Para o grafo hipercúbico $Q_{n}$ em $2^{n}$ vértices, a largura de banda foi determinada por Harper (1966) para ser :$\varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.$
Chvatálová mostrou que a largura de banda do $(m\times n)$ grafo de grade quadrada $P_{m}\times P_{n}$, isto é, o produto cartesiano de dois caminhos de grafo em $m$ e $n$ vértices, é igual à $\min\{m,n\}$.

## Limites

A largura de banda de um grafo pode ser limitada em termos de vários outros parâmetros de grafos. Por exemplo, deixando χ(G) denotar o número cromático de G,
    φ(G) ≥ χ(G)-1;
deixando diam(G) denotar o diâmetro de G, as desigualdades seguintes:
    $\lceil (n-1)/\mathrm {diam} (G)\rceil \leq \varphi (G)\leq n-\mathrm {diam} (G)$,
onde $n$ é o número de vértices em $G$.
Se um grafo $G$ tem largura de banda $k$, então sua largura do caminho é, no máximo, $k$ (Kaplan & Shamir 1996), e sua profundidade de árvore é, no máximo, $k\log(n/k)$ (Gruber 2012). Em contraste, como notado na seção anterior, o grafo estrela $S_{k}$, um exemplo estruturalmente muito simples de uma árvore tem largurra de banda grande, comparativamente. Observe que a largura do caminho de $S_{k}$ é 1, e sua árvore de profundidade é 2.
Algumas famílias de grafos de grau limitado tem largura de banda sublinear: Chung (1988) provado que se T é uma árvore de grau máximo no máximo ∆, então
    $\varphi (T)\leq 5n/\log _{\Delta }n$.
Geralmente, para grafos planares de grau máximo limitado no máximo ∆, um limite similar segue (cf. Böttcher et al. 2010):
    $\varphi (G)\leq 20n/\log _{\Delta }n$.

## Computando a largura de banda

Ambas as versões com e sem peso são casos especiais do problema da atribuição quadrática do gargalo. O problema da largura de banda é NP-difícil, mesmo para alguns casos especiais. A respeito da exxistência de algoritmos de aproximação eficientes, sabe-se que a largura de banda é NP-difícil para aproximar dentro de qualquer constante, e isso vale mesmo quando os grafos de entrada são restritos para árvores cartepillar (Dubey, Feige & Unger 2010). Por outro lado, um número de casos especiais solúveis polinomialmente são conhecidos. Um algoritmo de heurística para obter esboços de grafo linear de largura de banda baixa é o algoritmo de Cuthill–McKee. Um algoritmo de multinível rápido para computação de largura de banda de grafos foi proposto em .

## Aplicações

O interesse nesse problema vem de algumas áreas de aplicação.
Uma área é o tratamento de matriz esparsa/matriz de banda, e algoritmos gerais dessa área, tal como o algoritmo de Cuthill–McKee, pode ser aplicado para encontrar soluções aproximadas para o problema da largura de banda de grafo.
Outro domínio de aplicação é em automação de design eletrônico. Na metodologia do design de célula padrão, tipicamente células padrão têm a mesma altura, e sua atribuição é organizada em um número de linhas. Nesse contexto(modelos do problema de largura de banda de grafo), o problema da atribuição de um conjuntp de células padrão em uma única linha com o objetivo de minimizar o delay de propagação máximo (o qual é assumido ser proporcional ao comprimento do arame).

## Veja também

* Largura do caminho, um problema de otimização NP-completo diferente envolvendo esboços lineares de grafos.