Spanning tree - Spanning tree

Uma árvore de abrangência (bordas pesadas em azul) de um gráfico de grade

Na matemática campo da teoria dos grafos , uma árvore geradora T de um grafo não direcionado G é um subgrafo que é uma árvore que inclui todos os vértices de G . Em geral, um gráfico pode ter várias árvores de abrangência, mas um gráfico que não está conectado não conterá uma árvore de abrangência (consulte florestas abrangentes abaixo). Se todas as arestas de G também são arestas de uma árvore geradora T de G , então G é uma árvore e é idêntica a T (ou seja, uma árvore tem uma árvore geradora única e é ela mesma).

Formulários

Vários algoritmos de pathfinding , incluindo o algoritmo de Dijkstra e o algoritmo de pesquisa A * , constroem internamente uma árvore de abrangência como uma etapa intermediária na resolução do problema.

A fim de minimizar o custo de redes de energia, conexões de fiação, tubulação, reconhecimento automático de voz, etc., as pessoas costumam usar algoritmos que constroem gradualmente uma árvore de abrangência (ou muitas dessas árvores) como etapas intermediárias no processo de encontrar a árvore de abrangência mínima .

A Internet e muitas outras redes de telecomunicações têm links de transmissão que conectam nós em uma topologia de malha que inclui alguns loops. Para evitar loops de ponte e loops de roteamento , muitos protocolos de roteamento para essas redes, incluindo o protocolo Spanning Tree , Open Shortest Path First , protocolo de roteamento link-state , roteamento baseado em árvore Aumentada , etc., exigem cada roteador para se lembrar de um árvore geradora.

Um tipo especial de árvore geradora, a árvore Xuong , é usada na teoria dos grafos topológica para encontrar embeddings de grafos com gênero máximo . Uma árvore Xuong é uma árvore geradora de tal forma que, no gráfico restante, o número de componentes conectados com um número ímpar de arestas é o menor possível. Uma árvore Xuong e uma incorporação de gênero máxima associada podem ser encontrados em tempo polinomial .

Definições

Uma árvore é um ligado grafo não-dirigido sem ciclos . É uma árvore geradora de um grafo G se abrange G (ou seja, inclui todos os vértices de G ) e é um subgráfico de G (todas as arestas da árvore pertencem a G ). Uma árvore geradora de um grafo conectado G também pode ser definida como um conjunto máximo de arestas de G que não contém nenhum ciclo, ou como um conjunto mínimo de arestas que conectam todos os vértices.

Ciclos fundamentais

Adicionar apenas uma aresta a uma árvore estendida criará um ciclo; esse ciclo é chamado de ciclo fundamental . Há um ciclo fundamental distinto para cada aresta que não está na árvore de abrangência; assim, há uma correspondência um a um entre os ciclos fundamentais e as arestas que não estão na árvore de abrangência. Para um grafo conectado com V vértices, qualquer árvore geradora terá V  - 1 arestas e, portanto, um gráfico de E arestas e uma de suas árvores abrangentes terá E  -  V  + 1 ciclos fundamentais (O número de arestas subtraído pelo número de arestas incluídas em uma árvore de abrangência; fornecendo o número de arestas não incluídas na árvore de abrangência). Para qualquer árvore geradora dada, o conjunto de todos  os ciclos fundamentais E  -  V + 1 forma uma base de ciclo , uma base para o espaço do ciclo .

Conjuntos de cortes fundamentais

Dual à noção de um ciclo fundamental é a noção de um cutset fundamental . Excluindo apenas uma aresta da árvore estendida, os vértices são particionados em dois conjuntos separados. O cutset fundamental é definido como o conjunto de arestas que devem ser removidas do grafo G para realizar a mesma partição. Assim, cada árvore geradora define um conjunto de V  - 1 conjuntos de cortes fundamentais, um para cada aresta da árvore geradora.

A dualidade entre os conjuntos de cortes fundamentais e os ciclos fundamentais é estabelecida observando-se que as arestas do ciclo que não estão na árvore de abrangência só podem aparecer nos conjuntos de cortes das outras arestas do ciclo; e vice-versa : as arestas em um cutset só podem aparecer nos ciclos que contêm a aresta correspondente ao cutset. Essa dualidade também pode ser expressa usando a teoria das matróides , segundo a qual uma árvore geradora é uma base da matróide gráfica , um ciclo fundamental é o circuito único dentro do conjunto formado pela adição de um elemento à base, e conjuntos de cortes fundamentais são definidos da mesma forma da matróide dupla .

Abrangendo florestas

Em gráficos que não estão conectados, não pode haver árvore de abrangência e, em vez disso, deve-se considerar florestas abrangentes . Aqui, existem duas definições concorrentes:

• Alguns autores consideram uma floresta geradora como um subgrafo acíclico máximo do grafo dado, ou equivalentemente um grafo consistindo de uma árvore geradora em cada componente conectado do grafo.
• Para outros autores, uma floresta estendida é uma floresta que abrange todos os vértices, significando apenas que cada vértice do gráfico é um vértice na floresta. Para esta definição, mesmo um grafo conectado pode ter uma floresta geradora desconectada, como a floresta na qual cada vértice forma uma árvore de vértice único.

Para evitar confusão entre essas duas definições, Gross e Yellen (2005) sugerem o termo "floresta de abrangência total" para uma floresta de abrangência com a mesma conectividade do gráfico fornecido, enquanto Bondy & Murty (2008) chamam esse tipo de floresta de " floresta de extensão máxima ".

Contando árvores extensas

A fórmula de Cayley conta o número de árvores abrangentes em um gráfico completo. Há árvores dentro , árvores dentro e árvores dentro .${\ displaystyle 2 ^ {2-2} = 1}$${\ displaystyle K_ {2}}$${\ displaystyle 3 ^ {3-2} = 3}$${\ displaystyle K_ {3}}$${\ displaystyle 4 ^ {4-2} = 16}$${\ displaystyle K_ {4}}$

O número t ( G ) de árvores geradoras de um grafo conectado é um invariante bem estudado .

Em gráficos específicos

Em alguns casos, é fácil calcular t ( G ) diretamente:

• Se G for uma árvore, então t ( G ) = 1 .
• Quando G é o gráfico do ciclo C _n com n vértices, então t ( G ) =  n .
• Para um gráfico completo com n vértices, a fórmula de Cayley fornece o número de árvores abrangentes como n ^{n  - 2} .
• Se G for o grafo bipartido completo , então .${\ displaystyle K_ {p, q}}$${\ displaystyle t (G) = p ^ {q-1} q ^ {p-1}}$
• Para o gráfico de hipercubo n- dimensional , o número de árvores geradoras é . ${\ displaystyle Q_ {n}}$${\ displaystyle t (G) = 2 ^ {2 ^ {n} -n-1} \ prod _ {k = 2} ^ {n} k ^ {n \ escolha k}}$

Em gráficos arbitrários

De maneira mais geral, para qualquer gráfico G , o número t ( G ) pode ser calculado em tempo polinomial como o determinante de uma matriz derivada do gráfico, usando o teorema da árvore-matriz de Kirchhoff .

Especificamente, para computar t ( L ), um construções a matriz Laplaciano do gráfico, uma matriz quadrada, em que as linhas e colunas são ambos indexadas pelos vértices de L . A entrada na linha i e coluna j é um de três valores:

• O grau do vértice i , se i  =  j ,
• -1, se os vértices i e j são adjacentes, ou
• 0, se os vértices i e j forem diferentes um do outro, mas não adjacentes.

A matriz resultante é singular , então seu determinante é zero. No entanto, deletar a linha e a coluna de um vértice escolhido arbitrariamente leva a uma matriz menor cujo determinante é exatamente  t ( G ).

Deleção-contração

Se G é um gráfico ou multigrafo e e é uma aresta arbitrária de G , então o número t ( G ) de árvores geradoras de G satisfaz a recorrência de deleção-contração t ( G ) =  t ( G  -  e ) +  t ( G / e ), onde G  -  e é o multigrafo obtido pela exclusão de e e G / e é a contração de G por e . O termo t ( G  -  e ) nesta fórmula conta as árvores geradoras de  G que não usam a aresta  e , e o termo t ( G / e ) conta as árvores geradoras de  G que usam  e .

Nesta fórmula, se o grafo G dado for um multigrafo , ou se uma contração fizer com que dois vértices sejam conectados entre si por arestas múltiplas, então as arestas redundantes não devem ser removidas, pois isso levaria ao total errado. Por exemplo, um grafo de ligação conectando dois vértices por k arestas tem k árvores geradoras diferentes, cada uma consistindo em uma única dessas arestas.

Polinômio de Tutte

O polinômio Tutte de um gráfico pode ser definido como uma soma, sobre as árvores abrangentes do gráfico, de termos calculados a partir da "atividade interna" e da "atividade externa" da árvore. Seu valor nos argumentos (1,1) é o número de árvores geradoras ou, em um gráfico desconectado, o número de florestas abrangentes máximas.

O polinômio Tutte também pode ser calculado usando uma recorrência de deleção-contração, mas sua complexidade computacional é alta: para muitos valores de seus argumentos, calculá-lo exatamente é # P-completo e também é difícil aproximar com uma razão de aproximação garantida . O ponto (1,1), no qual pode ser avaliado usando o teorema de Kirchhoff, é uma das poucas exceções.

Algoritmos

Construção

Uma única árvore de abrangência de um gráfico pode ser encontrada no tempo linear por pesquisa de profundidade ou pesquisa de largura . Ambos os algoritmos exploram o grafo dado, partindo de um vértice v arbitrário , percorrendo os vizinhos dos vértices que descobrem e adicionando cada vizinho inexplorado a uma estrutura de dados a ser explorada posteriormente. Eles diferem em se esta estrutura de dados é uma pilha (no caso de pesquisa em profundidade) ou uma fila (no caso de pesquisa em largura). Em ambos os casos, pode-se formar uma árvore geradora conectando cada vértice, exceto o vértice raiz v , ao vértice de onde foi descoberto. Esta árvore é conhecida como árvore de pesquisa em profundidade ou árvore de pesquisa em largura, de acordo com o algoritmo de exploração de gráfico usado para construí-la. As árvores de busca em profundidade são um caso especial de uma classe de árvores extensas chamadas árvores Trémaux , em homenagem ao descobridor da busca em profundidade no século 19.

Spanning trees são importantes na computação paralela e distribuída, como forma de manter a comunicação entre um conjunto de processadores; veja, por exemplo, o Spanning Tree Protocol usado por dispositivos de camada de link OSI ou o Shout (protocolo) para computação distribuída. No entanto, os métodos de profundidade e largura primeiro para construir árvores extensas em computadores sequenciais não são adequados para computadores paralelos e distribuídos. Em vez disso, os pesquisadores desenvolveram vários algoritmos mais especializados para encontrar árvores geradoras nesses modelos de computação.

Otimização

Em certos campos da teoria dos grafos, muitas vezes é útil encontrar uma árvore geradora mínima de um gráfico ponderado . Outros problemas de otimização em árvores geradoras também foram estudados, incluindo a árvore geradora máxima, a árvore mínima que abrange pelo menos k vértices, a árvore geradora com o menor número de arestas por vértice , a árvore geradora com o maior número de folhas , a árvore geradora com o menor número de folhas (intimamente relacionado ao problema do caminho hamiltoniano ), a árvore geradora de diâmetro mínimo e a árvore geradora de dilatação mínima.

Problemas de árvore geradora ótima também têm sido estudados para conjuntos finitos de pontos em um espaço geométrico, como o plano euclidiano . Para tal entrada, uma árvore geradora é novamente uma árvore que tem como vértices os pontos dados. A qualidade da árvore é medida da mesma forma que em um gráfico, usando a distância euclidiana entre pares de pontos como o peso de cada aresta. Assim, por exemplo, uma árvore geradora mínima euclidiana é igual a uma árvore geradora mínima de gráfico em um gráfico completo com pesos de aresta euclidianos. Porém, não é necessário construir este gráfico para resolver o problema de otimização; o problema da árvore geradora mínima euclidiana, por exemplo, pode ser resolvido mais eficientemente em tempo O ( n  log  n ) construindo a triangulação de Delaunay e então aplicando um algoritmo de árvore geradora mínima de gráfico planar de tempo linear à triangulação resultante.

Randomization

Uma árvore geradora escolhida aleatoriamente entre todas as árvores geradoras com igual probabilidade é chamada de árvore geradora uniforme . O algoritmo de Wilson pode ser usado para gerar árvores geradoras uniformes em tempo polinomial por um processo de dar um passeio aleatório no gráfico dado e apagar os ciclos criados por esse passeio.

Um modelo alternativo para gerar árvores de abrangência aleatoriamente, mas não uniformemente, é a árvore de abrangência mínima aleatória . Nesse modelo, as arestas do gráfico recebem pesos aleatórios e, em seguida, a árvore de abrangência mínima do gráfico ponderado é construída.

Enumeração

Como um gráfico pode ter exponencialmente muitas árvores estendidas, não é possível listar todas em tempo polinomial . No entanto, os algoritmos são conhecidos por listar todas as árvores abrangentes em tempo polinomial por árvore.

Em gráficos infinitos

Cada grafo finito conectado possui uma árvore de abrangência. No entanto, para infinitos grafos conectados, a existência de árvores geradoras é equivalente ao axioma de escolha . Um gráfico infinito é conectado se cada par de seus vértices formar o par de pontos finais de um caminho finito. Tal como acontece com os grafos finitos, uma árvore é um grafo conectado sem ciclos finitos, e uma árvore geradora pode ser definida como um conjunto acíclico máximo de arestas ou como uma árvore que contém todos os vértices.

As árvores dentro de um gráfico podem ser parcialmente ordenadas por sua relação de subgráfico, e qualquer cadeia infinita nesta ordem parcial tem um limite superior (a união das árvores na cadeia). O lema de Zorn , uma das muitas afirmações equivalentes ao axioma da escolha, requer que uma ordem parcial em que todas as cadeias tenham um limite superior tenha um elemento máximo; na ordem parcial das árvores do gráfico, esse elemento máximo deve ser uma árvore geradora. Portanto, se o lema de Zorn for assumido, todo grafo infinito conectado tem uma árvore geradora.

Na outra direção, dada uma família de conjuntos , é possível construir um grafo infinito de forma que cada árvore geradora do gráfico corresponda a uma função de escolha da família de conjuntos. Portanto, se cada grafo infinito conectado possui uma árvore de abrangência, o axioma da escolha é verdadeiro.

Em multigrafos dirigidos

A ideia de uma árvore geradora pode ser generalizada para multigrafos direcionados. Dado um vértice v em um multigrafo direcionado G , uma árvore geradora orientada T enraizada em v é um subgrafo acíclico de G em que todo vértice diferente de v tem o grau superior a 1. Esta definição só é satisfeita quando os "ramos" de T apontam para v .

Veja também

• Algoritmo de inundação
• Good spanning tree - Spanning tree para grafo planar embutido

Referências