Na teoria dos grafos e na ciência da computação teórica , a largura da árvore ou largura da árvore de um gráfico ( largura da árvore ) é um número que mede intuitivamente se ele está próximo a uma árvore. Ele pode ser definido de várias maneiras , Em particular usando a decomposição em árvore .
Freqüentemente, um problema algorítmico fácil em árvores é realmente fácil em gráficos que se parecem com árvores. Assim, este parâmetro é frequentemente usado em algoritmos de gráfico, em particular para esquemas de aproximação polinomial e complexidade parametrizada . Em muitas aplicações, os gráficos têm pequenas larguras de árvore , como as redes sociais.
Informalmente, dado um grafo não direcionado , uma decomposição de árvore de é uma árvore cujos nós são anotados por subconjuntos de vértices de , que satisfazem as seguintes condições:
Formalmente, dado um gráfico não direcionado , uma decomposição em árvore é um par que é uma árvore e é uma função associada a cada nó de um subconjunto , que satisfaz as seguintes condições:
Qualquer gráfico tem pelo menos uma decomposição de árvore, por exemplo aquele em que a árvore tem um único vértice e onde . Nesse caso, todos os vértices e arestas do gráfico são cobertos e a condição nos caminhos é trivialmente satisfeita. No entanto, essa decomposição não é única. Mais geralmente, qualquer gráfico admite uma infinidade de decomposições de árvores: podemos, por exemplo, escolher qualquer árvore e definir por para qualquer nó .
Definição da largura da árvoreA largura da árvore de uma decomposição de árvore é o cardeal do maior rótulo menos um. Formalmente, é sobre . No exemplo da figura, todos os rótulos são do cardinal 3, portanto a largura da árvore desta decomposição da árvore é 2. A largura da árvore ( largura da árvore ) de um gráfico G é o mínimo da largura da árvore entre todas as decomposições da árvore deste gráfico.
Se considerarmos uma decomposição de árvore trivial onde os nós são rotulados pelo conjunto de todos os vértices do gráfico, vemos que qualquer gráfico com vértices tem uma largura de árvore de no máximo. Por outro lado, se for uma árvore, se construirmos seguindo a estrutura de , podemos obter uma decomposição em árvore de onde cada rótulo contém exatamente dois elementos, portanto de largura 1.
Para qualquer gráfico , denotamos a ordem do maior clique de . A largura da árvore de um gráfico é o menor valor obtido por , entre todas as triangulações de .
Árvores têm largura de árvore 1. O clique de tamanho n tem largura de árvore n-1 . A grade quadrada de tamanho n tem uma largura de eixo igual a n .
O cálculo da largura da árvore é NP-difícil . No entanto, se for fixo, existe um algoritmo linear para determinar se a largura da árvore de um gráfico é . A dependência do tempo de execução do algoritmo é, entretanto, exponencial. Para algumas classes particulares de gráficos, o cálculo da largura da árvore é feito em tempo polinomial (árvores, gráficos triangulados, etc.).
Muitos problemas de gráficos NP-difíceis no caso geral podem ser resolvidos em tempo polinomial se nos restringirmos a gráficos de largura de árvore limitada. É, portanto, um bom parâmetro para a complexidade parametrizada . Se o problema pode ser expresso em lógica monádica de segunda ordem , o teorema de Courcelle afirma que ele pode então ser resolvido em tempo linear (mas a constante é uma volta de exponenciais que torna o algoritmo inaplicável em geral).
Por exemplo, o problema de estabilidade máxima para gráficos planares pode ser resolvido em tempo polinomial para uma largura de árvore limitada (então tomamos essa largura como uma constante), o que torna possível obter um esquema de aproximação em tempo polinomial quando não restringimos o largura.
O conceito de decomposição de árvore tem uma ligação muito forte com gráficos triangulados . Primeiro, a largura da árvore de um gráfico triangulado H é igual ao tamanho de seu maior clique menos um. Em segundo lugar, o valor pode ser calculado usando um algoritmo linear se o gráfico H for triangulado. Na literatura de investigação operacional , algoritmos para calcular a árvore de largura de um gráfico G geralmente procuram determinar o gráfico triangulada H de valor menor que contém L .
A largura da árvore pode ser vinculada a outros parâmetros do gráfico, como degeneração ou amora .
Uma variante para gráficos direcionados foi definida, é zero em gráficos direcionados acíclicos .