Largura de banda de grafos

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Em teoria dos grafos, o problema da Largura de Banda de Grafos é rotular os n vértices vi de um grafo G com inteiros distintos f(vi), de modo que a quantidade é minimizada (E é o conjunto de arestas de G).[1] 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.[2]

O problema da Largura de Banda de Grafos com peso é a generalização em que as arestas são pesos atribuídos wij e a função de custo para ser minimizada é .

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[editar | editar código-fonte]

Para várias famílias de grafos, a largura de banda é dada por uma fórmula explícita.

A largura de banda de um caminho em um grafo sobre n vértices é , e para um grafo completo , temos . Para o Grafo bipartido completo

, assumindo , a qual foi provada por Chvátal.[3] Como um caso especial dessa fórmula, o grafo estrela em k+1 vértices tem largura de banda .

Para o grafo hipercúbico em vértices, a largura de banda foi determinada por Harper (1966) para ser :

Chvatálová mostrou[4] que a largura de banda do grafo de grade quadrada , isto é, o produto cartesiano de dois caminhos de grafo em e vértices, é igual à .

Limites[editar | editar código-fonte]

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:[5]

,

onde é o número de vértices em .

Se um grafo tem largura de banda , então sua largura do caminho é, no máximo, (Kaplan & Shamir 1996), e sua profundidade de árvore é, no máximo, (Gruber 2012). Em contraste, como notado na seção anterior, o grafo estrela , um exemplo estruturalmente muito simples de uma árvore tem largurra de banda grande, comparativamente. Observe que a largura do caminho de é 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

.

Geralmente, para grafos planares de grau máximo limitado no máximo , um limite similar segue (cf. Böttcher et al. 2010):

.


Computando a largura de banda[editar | editar código-fonte]

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.[6] 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.[2] 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 .[7]


Aplicações[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Referências[editar | editar código-fonte]

  1. (Chinn et al. 1982)
  2. a b "Coping with the NP-Hardness of the Graph Bandwidth Problem", Uriel Feige, Lecture Notes in Computer Science, Volume 1851, 2000, pp. 129-145, doi:10.1007/3-540-44985-X_2
  3. A remark on a problem of Harary. V. Chvátal, Czechoslovak Mathematical Journal 20(1):109–111, 1970. http://dml.cz/dmlcz/100949
  4. Optimal Labelling of a product of two paths. J. Chvatálová, Discrete Mathematics 11, 249–253, 1975.
  5. Chinn et al. 1982
  6. Garey–Johnson: GT40
  7. Ilya Safro and Dorit Ron and Achi Brandt (2008). «Multilevel Algorithms for Linear Ordering Problems». ACM Journal of Experimental Algorithmics. 13: 1.4–1.20. doi:10.1145/1412228.1412232 

Ligações externas[editar | editar código-fonte]

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