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 Predefinição:Harv.

Fórmulas de largura de banda para alguns grafos

Para várias famílias de grafos, a largura de banda $\phi (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 $\phi (K_n)=n-1$. Para o Grafo bipartido completo $K_{m,n},$

$\phi (K_{m,n})=\lfloor (m-1)/2\rfloor +n$, assumindo $m\ge n\ge 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 $\phi (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 Predefinição:Harvtxt para ser :$\phi (Q_n)=\sum _{m=0}^{n-1}(\genfrac{}{}{0ex}{}{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{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)\rceil \le \phi (G)\le n-\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(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$ Predefinição:Harv, e sua profundidade de árvore é, no máximo, $k\log (n/k)$ Predefinição:Harv. 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: Predefinição:Harvtxt provado que se T é uma árvore de grau máximo no máximo ∆, então

$\phi (T)\le 5n/{\log }_{\mathrm{\Delta }}n$.

Geralmente, para grafos planares de grau máximo limitado no máximo ∆, um limite similar segue (cf. Predefinição:Harvnb):

$\phi (G)\le 20n/{\log }_{\mathrm{\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 Predefinição:Harv. 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.

Referências

• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citation
• Predefinição:Citar periódico
• Predefinição:Citar livro
• Predefinição:Citation
• Predefinição:Citar periódico
• Predefinição:Citation

Ligações externas

• Minimum bandwidth problem, em: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems. Acessado em Maio 26, 2010.