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.

Referências

• Böttcher, Julia; Klaas P. (1 de julho de 2010). «Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs». European Journal of Combinatorics. 31 (5): 1217-1227. doi:10.1016/j.ejc.2009.10.010 
• Chinn, P. Z.; J. (1 de setembro de 1982). «The bandwidth problem for graphs and matrices—a survey». Journal of Graph Theory (em inglês). 6 (3): 223-254. ISSN 1097-0118. doi:10.1002/jgt.3190060302 
• Chung, Fan R. K. (1988), «Labelings of Graphs», in: Beineke, Lowell W., Selected Topics in Graph Theory (PDF), ISBN 978-0-12-086203-0, Academic Press, pp. 151–168 
• Dubey, Chandan; Uriel (1 de janeiro de 2011). «Hardness results for approximating the bandwidth». Journal of Computer and System Sciences. 77 (1): 62-90. doi:10.1016/j.jcss.2010.06.006 
• Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5 
• Gruber, Hermann (2012), «On Balanced Separators, Treewidth, and Cycle Rank», Journal of Combinatorics, 3 (4): 669–682, doi:10.4310/joc.2012.v3.n4.a5 
• Harper, L.H. «Optimal numberings and isoperimetric problems on graphs». Journal of Combinatorial Theory. 1 (3): 385-393. doi:10.1016/s0021-9800(66)80059-5 
• Kaplan, Haim; Shamir, Ron (1996), «Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques», SIAM Journal on Computing, 25: 540–561, doi:10.1137/s0097539793258143 

Ligações externas

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