4 - ÁRVORES


Última revisão: 02/05/2001


Conteúdo

Definição
Propriedades das árvores
Distância
Árvore enraizada
Árvore geradora
Circuitos fundamentais
Árvore geradora em grafo valorado

Algoritmos gulosos
Algoritmo de Kruskal
Algoritmo de Prim
Exercícios


Definição

Nessa parte do curso vamos estudar um caso particular da teoria dos grafos que são as árvores. Primeiro, vamos definir o conceito de árvore.

Simplesmente, uma árvore é um grafo conexo sem circuito. Note que como um grafo precisa conter no mínimo um vértice, uma árvore contém no mínimo um vértice. Também temos que uma árvore é um grafo simples, pois laços e arestas paralelas formam circuitos. Um grafo não conexo que não contém circuitos será denomeado floresta. Nesse caso temos um grafo onde cada componente é uma árvore.

Propriedades das árvores

Antes de apresentar o primeiro teorema que concerne as árvores, vamos provar o seguinte lema:

Lema 4-1: Seja C1 e C2 dois caminhos simples distintos entre dois vértices vj e vk de um grafo. A união C1 U C2 contém no mínimo um circuito.

Prova: Como os dois caminhos começam em vj e terminam em vk, e que eles são distintos, existe no mínimo um vértice onde eles se separam e um vértice onde eles se juntam. Seja vm o primeiro vértice onde eles se separam e vn o primeiro vértice onde eles se juntam. Necessariamente, fora vm e vn, não existe nenhum vértice comum entre esse dois caminhos. Podemos então formar um circuito, saindo de vm, indo até vn por um caminho, e voltar a vm pelo outro caminho.

Teorema 4-1: Existe exatamente um caminho simples entre cada par de vértices de uma árvore T.

Prova: Como T é conexo, existe um caminho entre cada par de vértices. Suponhamos agora que existem dois caminhos distintos entre dois vértices vj e vk. Pelo lema 4-1, já sabemos que isso implica a existência de um circuito, o que é impossível em uma árvore.

Teorema 4-2: Se existe exatamente um caminho simples entre cada par de vértices de um grafo G, G é uma árvore.

Prova: Se existe um caminho simples entre cada par de vértice de G, G é conexo. Suponhamos agora que o grafo não é uma árvore. Então, existe no mínimo um circuito. Já sabemos que entre qualquer par de vértices de um circuito, existem dois caminhos distintos, o que contradiz a hipótese.

Teorema 4-3: Uma árvore que contém n vértices contém exatamente n-1 arestas.

Prova: A prova é por indução. O caso n = 1 é trivial. Consideramos agora uma árvore T de n vértices. Seja ak uma aresta que liga dois vértices vi e vj. Segundo o teorema 4-1, o único caminho entre vi e vj é a aresta ak. Portanto, tirando essa aresta, o grafo fica desconexo. Seja G1 e G2 os dois componentes obtidos com a remoção de ak. Eles contêm, respectivamente, u e v vértices, onde u + v = n. Necessariamente, se T é uma árvore, G1 e G2 são também árvores. Ambos G1 e G2 têm menos vértices que T, então por indução G1 e G2 têm u-1 e v-1 arestas. Portanto, o número de arestas no grafo T, que é composto de G1 e G2 mais a aresta ak, é (u-1)+(v-1)+1 = u+v-1 = n-1.

Eis um lema que vai ser útil para provar o próximo teorema:

Lema 4-2: Um grafo conexo simples que contém n vértices (com n 2) e exatamente n-1 arestas contém no mínimo um vértice de grau 1.

Prova: Seja um grafo conexo simples que contém n vértices (com n 2) e exatamente n-1 arestas. Suponhamos agora que neste grafo não tem nenhum vértice de grau 1. Como o grafo é conexo, necessariamente para cada vértice vi temos d(vi) 2. A soma dos graus é maior ou igual a 2n. Portanto, o número de arestas é maior ou igual a n, o que contradiz a hipótese.

Teorema 4-4: Um grafo conexo simples que contém n vértices e exatamente n-1 arestas é uma árvore.

Prova: A prova é por indução. A base é um grafo de um vértice. Ele não contém nenhuma aresta e é trivial verificar que ele é uma árvore. Suponhamos agora um grafo de n vértices, onde n 2. Pelo lema 4-2, sabemos que esse grafo contém no mínimo 1 vértice de grau 1. Seja ai a aresta que liga um desses vértices. Tirando ai, obtemos um grafo de n-1 vértices e n-2 arestas de um lado, e um vértice isolado do outro lado. Por indução, sabemos que o grafo de n-1 vértices é uma arvore. Consideramos agora o vértice isolado. Não existe nenhum caminho entre ele e o resto do grafo. Colocando de novo a aresta ai, obtemos um caminho só entre ele e o resto. Portanto, o grafo é uma árvore.

Teorema 4-5 : Um grafo é uma árvore se e somente se ele é minimamente conexo (isto é, a remoção de qualquer aresta torna o grafo desconexo).

Prova:

Ida: Não existe circuito em uma árvore. Seja vi e vj dois vértices distintos. Tirando a aresta que liga esses dois vértices, o grafo necessariamente se torna desconexo, pois não existe caminho alternativo entre esses dois vértices. Se tivesse, esse caminho junto com a aresta retirada formaria um circuito, o que é impossível por definição.

Volta: Um grafo minimamente conexo não pode ter circuito, pois nesse caso se tirarmos um aresta do circuito, o grafo continua conexo. Portanto, esse grafo é uma árvore.

Se acrescentamos uma aresta entre quaisquer dois vértices de uma árvore, o resultado é um grafo que contém exatamente um circuito. Isso porque já existe um caminho entre esse dois vértices (veja teorema 4-1). A nova aresta acrescenta mais um caminho, criando assim um circuito. Suponhamos agora que o acréscimo de uma aresta em um grafo produz exatamente um circuito. Isso significa que antes de acrescentar essa aresta, digamos entre vi e vj, existia exatamente um caminho entre vi e vj. Pelo teorema 4-2, podemos deduzir que esse grafo era uma árvore. Portanto, podemos afirmar o seguinte teorema:

Teorema 4-6: Um grafo conexo é uma árvore se e somente se o acréscimo de uma aresta entre quaisquer dois vértices cria exatamente um circuito.

Em resumo, uma árvore é um grafo que pode ser definido por qualquer um desses enunciados (todos equivalentes):

  1. Um grafo conexo sem circuito.
  2. Um grafo onde existe exatamente um caminho simples entre qualquer par de vértices distintos.
  3. Um grafo conexo de n vértices e n-1 arestas.
  4. Um grafo minimamente conxeo.
  5. Um grafo conexo que contém exatamente um circuito depois do acréscimo de uma aresta.

Distância

Em um grafo conexo, a distância entre dois vértices é o comprimento do caminho mais curto. Se não tiver peso atribuido às arestas, o comprimento será o número de arestas no caminho. Se tiver pesos, o comprimento será a soma dos pesos. Se um grafo é uma árvore, a identificação da distância é uma tarefa simples, pois existe somente um caminho entre cada par de vértices.

Uma métrica é uma função f(x,y) que respeita as seguintes condições:

  1. f(x,y) 0 e f(x,y) = 0 se e somente se x = y.
  2. f(x,y) = f(y,x)
  3. f(x,y) f(x,z) + f(z,y) para qualquer z.

É fácil ver que a definição de distância dada em cima respeita essas condições. Então, é uma métrica.

Outra noção interessante é o centro de um grafo G. Seja primeiro a excentricidade definida assim: a excentricidade E(v) de um vértice v é a distância de v até o vértice mais longe de v. O centro de um grafo é o vértice (pode existir mais de um) que tem o menor valor de excentricidade. En geral, um grafo pode ter mais de um centro. Mas no caso de uma árvore, temos uma propriedade interessante cuja prova sugere (mais uma vez) um algoritmo para buscar o centro:

Teorema 4-7: Toda árvore contém um ou dois centros.

Prova: No exercício 4-5, prova-se que a distância máxima entre um vértice v e qualquer outro vértice vi acontece quando vi é um vértice pendente (isto é, um vértice de grau 1). Nos casos triviais de um ou dois vértices, temos um e dois centros, respectivamente. Suponhamos agora uma árvore A de n vértices, onde n 3. Pelo teorema do exercício 4-2, sabemos que esse grafo contém pelo menos dois vértices pendentes. Se tiramos todos os vértices pendentes, o grafo A' resultante ainda é uma árvore. Além disso, podemos ver que a excentricidade de todo vértice do grafo resultante foi diminuída de um valor 1. Então, qualquer vértice que era centro de A também é centro de A'. Continuando assim, necessariamente chegamos ao caso de uma ávore de um ou dois vértices, que são os centros de A.

Eis um exemplo de execução do algoritmo de busca do centro de uma árvore:

Figura 0

Árvore enraizada

Uma árvore T = (V,E) é denominado enraizada quando algum vértice v é distinguído dos outros. Esse vértice v é a raiz da árvore. Uma árvore não enraizada é denominada árvore livre. Na figura 1 são ilustradas duas árvores obtidas a partir do mesmo grafo. No primeiro caso, o vértice a é escolhido como raiz. No segundo caso a raiz é o vértice c.

Figura 1

Note que nessa definição, os filhos de um nodo não são ordenados.

As árvores enraizadas possuem várias características interessantes, que não seráo discutidas aqui. Somente notaremos que a implementação mais natural é como grafo direcionado, onde cada nodo contém apontador nos filhos. O acesso à estrutura se faz pela raiz.

Em resumo, uma árvore enraizada direcionada é um grafo que respeita as seguintes condições (todas equivalentes):

Árvore geradora

Uma árvore T é denominada árvore geradora de um grafo conexo G se T é um sub-grafo de G e contém todos os vértices de G. Por exemplo, na figura 2, o sub-grafo indicado em linhas grossas é uma árvore geradora do grafo representado.

Figura 2

Se um grafo é desconexo, não podemos identificar nenhuma árvore geradora. Mas podemos identificar no mínimo uma floresta de árvores geradoras, uma para cada componente do grafo.

O algoritmo para achar uma árvore geradora de um grafo G é muito simples. Se G não contém nenhum cirtuito ele já é a sua própria árvore geradora. Suponhamos agora que ele contém um circuito. Tirando uma aresta desse circuito resulta em um grafo aindo conexo. Continuando assim até que não tenha nenhum circuito, o grafo obtido é um grafo conexo que é uma árvore. Portanto:

Teorema 4-8: Todo grafo conexo contém no mínimo uma árvore geradora.

Seja G = (V,E) um grafo conexo e T = (V,F) uma árvore geradora de G. Uma aresta que pertence a E e não a F é chamada um elo de T. Seja n o número de vértices em G, m o número de arestas em E . O número total de elos em G é igual a m - n + 1. Note que um elo é definido em relação a uma árvore geradora específica de G.

Seja T uma árvore geradora de G. Se chamamos T' o complemento de T em G (isto é, todos os elos), podemos escrever G = T U T'.

Exemplo de aplicação de árvore geradora: A figura 3 ilustra um conjunto de terras separadas por muros. Supondo que todas são cheias de água, como podemos esvaziar todas, furando um número mínimo de buracos nos muros?

Figura 3

Se cada terra e a área exterior formam o conjuntos de vértices, e se cada muro separando duas áreas é representado por uma aresta, obtemos o grafo ilustrado na figura 4a. A solução a esse problema é evidentemente uma árvore geradora. Uma das árvores geradora do grafo é ilustrada em 4b.

Figura 4

Circuitos fundamentais e busca de todas as árvores geradoras

Vamos agora considerar uma árvore geradora T de um grafo G. Acrescentar um dos elos de T resulta em um circuito. Tal circuito é denomeado circuito fundamental. E muito importante notar que um circuito fundamental é definido somente em relação a uma árvore geradora específica.

Usando o conceito de circuito fundamental, temos um algoritmo relativamente simples para identificar todas as árvores geradoras de um grafo. Começamos com uma árvore geradora qualquer. Pegamos um dos elos do grafo e acrescentamos essa aresta. Como temos agora um circuito, tiramos uma aresta desse circuito, obtendo assim uma nova árvore geradora. Fazemos assim com todas as arestas desse circuito fundamental e todos os outros elos. Obtemos assim um conjunto de árvores geradoras. Repetimos o processo todo com todas as árvores obtidas. Evidentemente, o algoritmo tem que eliminar as redundâncias. Usando esse algoritmo podemos obter todas as árvores começando com qualquer árvore. A resposta é sim. A figura 6 ilustra a aplicação desse algoritmo a o grafo da figura 5.

Figura 5

Figura 6

Árvore geradora em grafo valorado

Supondo um grafo valorado, isto é, onde a cada aresta é atribuído um peso, podemos distinguir as árvores geradoras desse grafo em relação à soma total dos pesos. Temos aqui um problema interessante: como identificar a árvore que minimiza essa soma? Vamos chamar árvore geradora mínima tal árvore.

Para identificar a árvore geradora mínima de um grafo, existem dois algoritmos famosos, que vamos apresentar agora. Esses dois algoritmos são algoritmos gulosos. Então, antes de apresentá-los, é bom ver o que é um algoritmo guloso.

Algoritmos gulosos

Um algoritmo guloso se usa normalmente em problemas de otimização. O objetivo é de achar um conjunto de candidatos que otimizam o valor de uma função objetiva. O algoritmo procede passo a passo. Inicialmente, o conjunto é vazio. A cada passo, o algoritmo seleciona um candidato a ser acrescentado no conjunto. Ele tenta selecionar o melhor elemento do conjunto de candidatos. Se o acréscimo desse elemento no conjunto solução é viável, ele sera colocado no conjunto, senão ele sera rejeitado e nunca mais será considerado. Se ele é viável, o algoritmo testa se esse conjunto é uma solução. Se é, o algoritmo pára e retorna essa solução. Senão, ele continua:

função guloso(C: conjunto) : conjunto
{C é o conjunto de todos os candidatos}
S := {} (Conjunto que constitui a solução, inicialmente vazio)
Enquanto S não é uma solução e C não vazio
x := Melhor elemento de C
C := C - {x}
Se x é viável então S := S U {x}
Se S é uma solução
retornar S
Senão retornar Não encontrei uma solução

Esse tipo de algoritmo é dito guloso porque ele sempre tenta pegar o melhor pedaço, sem considerar as consequências no futuro. Uma vez um candidato incluído no conjunto de solução, ele fica sempre. Isso significa que, para retornar uma solução ótima, a função de seleção do próximo candidato é crucial.

Eis um exemplo de algoritmo guloso para dar o troco de 90 centavos.

função TROCO(C: conjunto de moedas) : conjunto de moedas
{C é o conjunto de todos os candidatos}
S := {}
Enquanto (Soma das moedas em S < 90) e (C não vazio)
x := Moeda de maior valor em C
C := C - {x}
Se (Soma dos valores em S + x 90) então S := S U {x}
Se Soma dos valores em S = 90
retornar S
Senão retornar Não encontrei uma solução

Note que neste caso, o algoritmo pode retornar uma solução que não é ótima:

TROCO({50, 50, 25, 25, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1})
Retorna: {50,25,10,1,1,1,1,1}

Pior, pode terminar sem retornar uma solução quando na verdade existe uma:

TROCO({50, 50, 25, 25, 10, 10, 10, 10, 1, 1, 1, 1})
Retorna: Não encontrei uma solução

Algoritmo de Kruskal

Seja G = (V,E) um grafo conexo não direcionado e valorado. O problema consiste em achar um sub-conjunto T de E, tal que T forme uma árvore e a soma dos pesos é o menor possível. Aplicando o algoritmo guloso nesse caso, teremos as seguintes definições:

Eis um lema importante que vai ser utilizado para provar que o algoritmo de Kruskal apresentado abaixo funciona corretamente:

Lema 4-3: Seja G = (V,E) um grafo conexo não direcionado e valorado. Seja B V um sub-conjunto próprio do conjunto de vértices de G. Seja também T E um conjunto promissor de arestas tal que nenhuma aresta de T toca B. Seja a a aresta de menor valor que toca B. Então T U { a } é promissor.

Prova: Seja U uma árvore geradora mínima, T um conjunto de arestas tal que T U (existe tal U pois existe um T promissor por hipótese) e um conjunto de vértices B V tal que nenhuma aresta de T toca B.. Veja na figura 6' um exemplo:

Figura 6'

Nesse exemplo o conjunto T, representado pelas arestas em linhas grossas, contém três arestas. O conjunto B contém os vértices que se encontram dentro da linha pontilhada. Podemos conferir facilmente que todas as arestas de T ligam dois vértices que são ambos fora ou dentro do conjunto B. Portanto nenhuma aresta de T toca B.

Seja agora a a aresta de menor valor que toca B. Se a pertence a U, não temos nada a provar. Suponhamos agora que a não faz parte de U. Acrescentando essa aresta a U, obtemos um circuito. Visto que a toca B, necessariamente existe uma outra aresta a' do circuito que toca B. Isso porque se a é uma aresta que sai de B e faz parte de um cicruito, deve existir uma outra arestas que entra em B:

Figura 6''

Se agora retiramos a', obtemos uma outra árvore geradora U'. Por definição, o peso de a não é maior que o peso de a'. A soma dos pesos de U' não pode ser maior que a soma dos pesos de U. Portanto U' também é uma árvore geradora mínima. Para completar a prova, notamos que T U'. Por hipótese T é um sub-conjunto de U. Para obter U' retiramos a aresta a' de U. Como a' toca B, ela não pertencer a T. Portanto, retirando essa aresta de U não elimina do conjunto nenuma aresta que já estáva em T.

Vamos ver agora como funciona o algoritmo de Kruskal. Seja G = (V,E) um grafo de n vértices. No início, T é vazio, e supomos um grafo nulo composto dos n vértices (isto é, um grafo de n vértices isolados). O conjunto B é o conjunto das arestas de G. Selecionamos a aresta de B que tem o menor valor. Se ela conecta dois componentes diferentes, colocamo-la no conjunto T e juntamos os dois componentes para formar um novo componente. Se ela liga dois vértices de um mesmo componente, ele é rejeitada, pois isso formaria um circuito. Continuamos assim até a obtenção de um componente só. Nesse caso, o conjunto T constitui uma solução.

Figura 7

Para entender melhor, considera o grafo ilustrado na figura 7. A primeira aresta a ser considerada é a que liga o vértice a com o vértice b. O resultado é um grafo que contém o seguintes componentes. {a,b},{c},{d},{e},{f} e {g}. Eis a sequência total:

Passo Aresta considerada Componentes
Início - {a} {b} {c} {d} {e} {f} {g}
1 (a,b) {a,b} {c} {d} {e} {f} {g}
2 (b,c) {a,b,c} {d} {e} {f} {g}
3 (d,e) {a,b,c} {d,e} {f} {g}
4 (f,g) {a,b,c} {d,e} {f,g}
5 (a,d) {a,b,c,d,e} {f,g}
6 (b,e) Rejeitada
7 (d,g) {a,b,c,d,e,f,g}

A figura 8 ilustra a progressão na composição da árvore geradora.

Figura 8

O mais complicado no algoritmo de Kruskal é o teste que verifique se a nova aresta considerada liga dois vértices de um mesmo componente. Uma solução seria a criação de uma lista para cada componente. Mas isso não seria muito eficiente, pois deveriamos percorrer potencialmente todas as listas para saber se uma aresta liga dois vértices de um mesmo componente. Obtemos uma solução melhor se, para cada componente do grafo, escolhemos um de seus vértices para identificá-lo. No início temos n conjuntos de um elemento só. Para representar isso, fazemos com que cada elemento aponta para si mesmo. Par juntar dois conjuntos, pegamos o "representante" de um deles e fazemos ele apontar no "representante" do outro conjunto. Utilizaremos a notação [vi] para representar um componente representado pelo vértice vi. Assim um conjunto é representado por uma árvore direcionada onde todos os caminhos chegam a um nodo que é o representante. Vamos chamar índice esse representante.

No nosso caso podemos utilizar uma tabela onde cada elemento representa um vértice do grafo. No início, todo mundo aponta para si mesmo:

a b c d e f g
1 2 3 4 5 6 7
1 2 3 4 5 6 7

Depois do primeiro passo, os vértices a e b devem fazer parte do mesmo componente. Para representar isso, o b vai apontar no a:

a b c d e f g
1 2 3 4 5 6 7
1 1 3 4 5 6 7

Depois dos dois próximos passos, o componente [c] se junta ao componente [a] e [d] se junta com [e]:

a b c d e f g
1 2 3 4 5 6 7
1 1 1 4 4 6 7

Depois do quinto passo o componente [d] tem que ser fusionado com o componente [a]. Agora o elemento d vai apontar no a:

a b c d e f g
1 2 3 4 5 6 7
1 1 1 1 4 6 7

Para saber se dois vértices são no mesmo componente, é muito fácil. Percorremos a partir do índice de cada um até chegar a um vértice que apontar para si mesmo. Se nos dois casos chegamos ao mesmo vértice, eles são no mesmo componente.

Agora, temos tudo para dar em detalhes o algoritmo. Nesse caso, é fácil ver que a melhor representação do grafo é a que utiliza um conjunto de arestas. Isso porque queremos visitar todas as arestas uma vez só. Supomos uma representação dos componentes que utiliza o método explicado acima e duas funções find(u), que retorna o índice que representa um componente, e merge(u,v), que efetua a fusão de dois componentes. Eis o algoritmo:

função Kruskal(G = (N,A): grafo): conjunto de arestas
Ordenar A pelos valores de peso
n := número de vértices em N,
T := {}
Inicializar o conjunto de componentes (cada vértice de G é um componente)
Enquanto T contém menos de n-1 arestas e A não vazio
(u,v) :=   aresta de menor peso de A
A :=   A - (u,v)
comp_u :=   find(u)
comp_v :=   find(v)
Se comp_u comp_v
merge(comp_u,comp_v)
T :=   T U {(u,v)}
Retornar T

Análise do algoritmo: O tempo de execução do algoritmo depende muito das chamadas a merge e find. Existe uma implementação que permite definir essas duas funções de tal maneira que elas sejam na ordem de log n. Supondo isso, podemos analizar o tempo da seguinte maneira (para um grafo de n vértices e a arestas):

A partir dessa análise, podemos concluir que o algoritmo é em O(a lg n).

Para terminar, devemos agora provar o seguinte teorema:

Teorema 4-9: O algoritmo de Kruskal é correto, isto é, ele retorna sempre uma árvore geradora mínima.

Prova: Vamos provar por indução. Seja G = (V,E) o grafo conexo processado pelo algoritmo. Base: No início o conjunto T é vazio. Como G é conexo, pelo teorema 4-8 sabemos que necessariamente ele contém uma árvore geradora. Então por definição T vazio é promissor.
Hipótese de indução: Suponhamos que T é promissor para 0 r k arestas.

Passo indutivo: Tendo T de k arestas, o algoritmo seleciona a aresta de menor peso no conjunto de arestas não visitadas. Seja ak+1 essa aresta. Há quatro casos:

  1. T já contém n-1 arestas. Nesse caso, a solução T que por indução é uma árvore mínima, é retornada.
  2. A aresta ak+1 liga dois vértices de T que são no mesmo componente. Nesse caso, ak+1 é rejeitada e T não muda.
  3. Um dos dois vértices ligados por ak+1 não pertence a T. Seja B o conjunto que contém somente esse vértice. É fácil verificar que T não toca esse conjunto e pelo lema 4-3, podemos concluir que T U {ak+1} é promissor.
  4. A aresta ak+1 liga dos vértices de T. Nesse caso, são dois vértices de componentes diferentes. Seja C1 e C2 esses dois componentes. Seja B os vértices de um desses dois componentes. Podemos ver facilemente que T não toca B, pois toda aresta de T ou não contém nenhum vértice de B ou contém dois. Portanto, pelo lema 4-3, T U {ak+1} é promissor.

Como a cada passo do algoritmo obtemos um conjunto promissor, necessariamente ele retorna uma solução.

Algoritmo de Prim

A característica principal do algoritmo de Kruskal é que ele seleciona a melhor arestas sem se preocupar da conexão com as arestas selecionadas antes. O resultado é uma proliferação de árvores que eventualmente se juntam para formar uma árvore.

Já que sabemos que no final temos que produzir uma árvore só, por que não tentar fazer com que uma árvore cresca naturalmente até a obtenção da árvore geradora mínima? Assim, a próxima aresta selecionada seria sempre uma que se conecta à arvore que já existe. Isso é a idéia do algoritmo de Prim:

No início o conjunto B contém um vértice arbitrário. A cada passo, o algoritmo considere todas as arestas que tocam B e seleciona a de menor peso. Depois, o algoritmo acrescenta em B o vértice ligada por essa aresta que não estava em B. O processo continua até que B contenha todos os vértices de G. Eis uma descrição do algoritmo:

função Prim(G = (N,A): grafo): conjunto de arestas T := {}
B := Um vértice de G
Enquanto B não contém todos os vértices
(u,v) :=   aresta de menor peso tal que u V - B e v B
T :=   T U {(u,v)}
B :=   B U {u}
Retornar T
Para ilustrar, consideremos de novo o grafo da figura 7, começando arbitrariamente pelo vértice a:

Passo Aresta considerada Conjunto B
Início - {a}
1 (b,a) {a,b}
2 (c,b) {a,b,c}
3 (d,a) {a,b,c,d}
4 (e,d) {a,b,c,d,e}
5 (g,d) {a,b,c,d,e,g}
6 (f,g) {a,b,c,d,e,f,g}

Figura 8

Para implementar eficientemente esse algoritmo, utiliza-se uma matriz de adjacência A[1..n, 1..n], onde cada elemento indica a distância entre dois vértices. Caso dois vértices não forem ligados por uma aresta o valor será . Para representar o conjunto B, podemos utilizar duas tabelas de n elementos, uma indicando para cada vértice o vértice de B que é mais perto, uma outra que dá a distância até o vértice de B que é mais perto. Seja mais_perto[1..n] e dist_mais_perto[1..n] essas duas tabelas, respectivamente. Para um vértice que já pertence a B, colocamos (-1) na entrada correspondente na tabela. Eis o algoritmo:

função Prim(L = [1..n, 1..n]: grafo): conjunto de arestas {Inicialmente consideramos que o vértice 1 é o único elemento de B}
T := {}
Para i := 2 até n:
mais_perto[i] := 1
dist_mais_perto[i] := L[i,1]
Repetir n-1 vezes:
min :=
Para j := 2 até n:
Se 0 dist_mais_perto[j] < min então
min := dist_mais_perto[j]
k := j
T :=   T U ((k,mais_perto[k])}
dist_mais_perto[k] := -1
Para j := 2 até n:
Se L[k,j] < dist_mais_perto[j] então
dist_mais_perto[j] := L[k,j]
mais_perto[j] := k
Retornar T

Analisando esse algoritmo, conclui-se que ele tem um tempo de execução em O(n2). Qual é o melhor entre esse algoritmo e o algoritmo de Kruskal? Se o grafo tem muitas arestas, istó é, ele tem um número de arestas que se aproxima de n(n-1), o tempo de execução com o algoritmo de Kruskal é em O(n2 lg n), portanto pior que o algoritmo de Prim. Mas se o grafo é esparso, o número de arestas se aproxima de n. Nesse caso, o algoritmo de Kruskal está em O(n lg n) e é o melhor. Na verdade, existem outros algoritmos melhores no caso de grafo esparso.


Exercício 4-1: É possível demonstrar que existe somente seis árvores diferentes de seis vértices. Desenhe essas árvores.

Exercício 4-2: Demonstre que uma árvore com n vértices, onde n 2, tem pelo menos dois vértices de grau 1.

Exercício 4-3: Demonstre que, em uma árvore, a distância entre dois vértices, como definida nesta apostila, é uma métrica.

Exercício 4-4: Desenhe um grafo que não é uma árvore e que tem mais de dois centros.

Exercício 4-5: Demonstre que, em uma árvore, a distância máxima entre um vértice v e qualquer outro vértice vi acontece quando vi é um vértice de grau 1.

Exercício 4-6: Supondo que você quer identificar o centro de uma árvore, utilizando a técnica usada para provar o teorema 4-7. Qual será a melhor maneira de repsentar o grafo? Analise a complexidade do tempo de execução do algoritmo.

Exercício 4-7: Identifique todas as árvores geradoras do grafo ilustrado na figura 9.

Figura 9

Exercício 4-8: Prove que uma aresta pendente (isto é, uma aresta que liga um vértice de grau 1) em um grafo conexo G é contida em toda árvore geradora de G.

Exercício 4-9: É possível construir um grafo conhecendo todas as suas árvores geradoras? Se for, como?

Exercício 4-10: Prove que qualquer aresta de um grafo conexo G é um ramo de uma árvore geradora de G. Podemos também dizer que qualquer aresta de G também é o elo de uma árvore geradora?

* Exercício 4-11: Sugira um método para determinar o número de árvores geradora de um grafo sem que seja preciso enumerá-las.

Exercício 4-12: Prove que duas cores são suficientes para colorir os vértices de uma árvore de tal maneira que nenhum vértice seja adjacente a um vértice da mesma cor.

Exercício 4-13: Suponha um conjunto de n números inteiros positivos. Dê as condições necessárias para que esses números possam representar os graus dos n vértices de uma árvore. Essas condições são suficientes?

Exercício 4-14: Utilize os algoritmos de Kruskal e de Prim para identificar uma árvore geradora mínima em cada um dos grafos ilustrados na figura 10 e 11. Qual é o melhor?

Figura 10

Figura 11

Exercício 4-15: Um grafo pode ter várias árvores geradoras diferentes. É o caso no exemplo da figura 7. Onde essa possibilidade aparece no algoritmos de Kruskal e de Prim dados em cima?

Exercício 4-16: O que acontece se por engano executamos os algoritmos de Kruskal e de Prim com um grafo desconexo?

Exercício 4-17: O que acontece se por engano executamos os algoritmos de Kruskal e de Prim com um grafo que tem pesos negativos?

Exercício 4-18: O que seria o tempo necessário para executar o algoritmo de Kruskal se utilizamos uma matriz de adjacência para representar o grafo?

Exercício 4-19: Demonstre que o algoritmo de Prim funciona corretamente. A prova se faz por indução sobre o número de vértices em B.

Exercício 4-20: Seja G um grafo conexo valorado onde existe uma aresta am cujo peso é menor que o peso de qualquer outra aresta de G. Prove que toda árvore geradora mínima de G deve conter am.

Exercício 4-21: Seja G um grafo conexo valorado onde toda aresta pertence a um circuito. Se al é uma aresta cujo peso é maior que o peso de qualquer outra aresta de G, mostre que nenhuma árvore geradora mínima de G contém al.

Exercício 4-22: Mostre que ambos algoritmos de Kruskal e Prim sempre retornam a mesma árvore geradora com um grafo conexo onde todas as arestas têm um peso diferente.

Exercício 4-23: Podemos afirmar que o caminho entre dois vértices de um grafo que faz parte da árvore geradora mínima é o caminho mais curto entre esses dois vértices?

Exercício 4-24: Supohna que existem exatamente duas arestas com o mesmo peso. Podemos dizer que o algoritmo de Prim retorne a mesma árvore geradora independentemente de qual aresta foi selecionada?

Exercício 4-25: Considere o algoritmo de Prim genérico, onde não temos para cada vértice uma memória do vértice mais próximo em B. Isso significa que a cada etapa temos que comparar cada vértice de B com cada vértice fora de B para determinar a aresta de menor valor. Mostre que esse algoritmo é na ordem de n3.