Projeto e Análise de Algoritmos I
Aula 20 - Árvores Geradoras de Custo Mínimo: Algoritmo de Prim
Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica
Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado e André Grahl.
Árvores Geradoras
Motivação: Design de Redes
Motivação: Design de Redes
Motivação: Design de Redes
Na situação anterior:
- Temos um conjunto de torres.
- Para conectar duas torres, usamos um cabeamento.
- Queremos que todas elas estejam interconectadas.
P. Como minimizar o comprimento do cabeamento?
- Este é um problema de otimização.
- A entrada pode ser modelada como um grafo.
Árvores Geradoras
Definição: Seja G = (V,E) um grafo simples. Um subgrafo gerador de G é um grafo G' = (V',E') onde G' \subseteq G e V' = V.
Definição: Um subgrafo gerador de G que é uma árvore é chamado uma árvore geradora de G.
Exemplo: G', G'' e G''' são árvores geradoras distintas de G (arestas da árvore em verde):
Nota: Árvores geradoras também são conhecidas como árvores de extensão, árvores espalhadas ou árvores de espalhamento. Termo em inglês: spanning tree.
Árvores Geradoras em Grafos com Pesos
Definição: O peso de uma árvore geradora A = (V,E,w) de G (grafo com pesos) é a soma W(A) = \sum_{e \in E} w(e)
Definição: Dado um grafo com pesos G, uma árvore geradora mínima (AGM) é:
- Uma árvore geradora com peso menor ou igual a todas as demais árvores geradoras de G
- Isto é, uma árvore que minimiza W.
Aplicações de Árvores Geradoras Mínimas
O problema da Árvore Geradora Mínima tem diversas aplicações:
- Design de redes de comunicação, computadores, elétricas, hidráulicas, etc.
- Análise de clusters.
- Encontrar redes de trânsito em imagens de satélite.
- Identificação de faces em tempo real.
- Algoritmos aproximados para problemas NP-hard (e.g., caixeiro viajante).
- Protocolo de autoconfiguração para Ethernet para evitar ciclos em redes.
- Dithering.
- \ldots
Aplicações de Árvores Geradoras Mínimas
Exemplo: Conectar diversos computadores com o mínimo de cabos, estações de energia elétrica com o mínimo de fios, etc.
Exercício: Apresente uma AGM para o seguinte grafo:
Nota: Existe AGM para um grafo simples com pesos nas arestas G sss G é conexo, e AGMs não são necessariamente únicas.
Propriedades de Árvores Geradoras
Proposição. Dado um grafo G=(V,E) e um subgrafo G'=(V,T) de G, com T\subseteq E, as seguintes afirmações são equivalentes:
- G' é uma árvore geradora de G.
- G' é acíclico e conectado.
- G' é conectado e tem |V|-1 arestas.
- G' é acíclico e tem |V|-1 arestas.
- G' é minimamente conectado: remover qualquer aresta desconecta o grafo.
- G' é maximamente acíclico: adicionar qualquer aresta gera um ciclo.
Enumeração de Árvores Geradoras
Enumeração de Árvores
Pergunta: Quantas árvores existem com exatos n vértices?
Nota: Árvores concretas, não classes de isomorfismo.
Podemos começar a contagem com número pequeno de vértices:
| |V| | 1 | 2 | 3 | 4 | 5 | \dots |
|---|---|---|---|---|---|---|
| número de árvores | 1 | 1 | 3 | 16 | 125 | \dots |
Pode-se detectar algum padrão?
Enumeração de Árvores: Fórmula de Cayley
Teorema: (Cayley, 1889) O número de árvores com n vértices é n^{n-2}.
- Em 1918, Prüfer apresentou uma prova alternativa desse teorema.
- A prova de Prüfer é interessante por introduzir uma codificação de árvores conhecida como código de Prüfer.
Ideia: estabelecer uma bijeção:
Árvores com n vértices \quad \Leftrightarrow \quad strings de tamanho n-2 sobre alfabeto \{a_1,\ldots,a_n\}, onde a_1 < a_2 < \cdots < a_n
Código Prüfer: Codificação
Código Prüfer: Exemplo de Codificação
Árvore:
Código Prüfer: 744171
Observações
- O código não faz nenhuma referência às folhas da árvore.
- Todos os nodos não-folha ocorrem no código.
- O primeiro nodo “removido” no processo de codificação é o menor número que não ocorre no código.
Código Prüfer: Codificação Passo a Passo
Regra: Em cada passo, removemos a menor folha f, registramos seu vizinho g e atualizamos a[i] \leftarrow g.
vermelho: folha removida agora. azul: vizinho registrado. cinza: já removido.
| i | f | g | a \text{ após } a[i]\leftarrow g | \text{novo }i |
|---|---|---|---|---|
| 1 | 2 | 7 | \boxed{7}\ \_ \ \_ \ \_ \ \_ \ \_ | 2 |
| 2 | 3 | 4 | 7\ \boxed{4}\ \_ \ \_ \ \_ \ \_ | 3 |
| 3 | 5 | 4 | 7\ 4\ \boxed{4}\ \_ \ \_ \ \_ | 4 |
| 4 | 4 | 1 | 7\ 4\ 4\ \boxed{1}\ \_ \ \_ | 5 |
| 5 | 6 | 7 | 7\ 4\ 4\ 1\ \boxed{7}\ \_ | 6 |
| 6 | 7 | 1 | 7\ 4\ 4\ 1\ 7\ \boxed{1} | 7 |
i=7 > n-2=6 \qquad \text{sobram } 1 \text{ e } 8
\textbf{Código Prüfer final: } 744171
Código Prüfer: Decodificação
Código Prüfer: Decodificação Passo a Passo
Entrada: s=744171 e n=8. Em cada passo, f é o menor número que não ocorre em s, adicionamos \{f,s[i]\} e substituímos s[i]\leftarrow f.
vermelho: aresta adicionada agora. azul: s[i]. cinza: aresta já adicionada.
| i | s | f | s[i] | \{f,s[i]\} | s \text{ após} |
|---|---|---|---|---|---|
| 1 | \boxed{7}44171 | 2 | 7 | \{2,7\} | \boxed{2}44171 |
| 2 | 2\boxed{4}4171 | 3 | 4 | \{3,4\} | 2\boxed{3}4171 |
| 3 | 23\boxed{4}171 | 5 | 4 | \{5,4\} | 23\boxed{5}171 |
| 4 | 235\boxed{1}71 | 4 | 1 | \{4,1\} | 235\boxed{4}71 |
| 5 | 2354\boxed{7}1 | 6 | 7 | \{6,7\} | 2354\boxed{6}1 |
| 6 | 23546\boxed{1} | 7 | 1 | \{7,1\} | 23546\boxed{7} |
i=7 > n-2=6
\text{em } s=235467,\ \text{não ocorrem } 1 \text{ e } 8
T \leftarrow T \cup \{\{1,8\}\}
\begin{array}{l} \textbf{Árvore reconstruída:}\\ \{2,7\},\{3,4\},\{5,4\},\{4,1\},\\ \{6,7\},\{7,1\},\{1,8\} \end{array}
Código Prüfer: Exercício de Decodificação
Exercício: Decodifique a árvore com 10 vértices (dígitos 1 a 10) representada pela seguinte string:
2, 3, 9, 5, 1, 8, 5, 2
Código Prüfer: Decodificação do Exercício
Entrada: s=2,3,9,5,1,8,5,2 e n=10. Em cada passo, f é o menor número que não ocorre em s, adicionamos \{f,s[i]\} e substituímos s[i]\leftarrow f.
vermelho: aresta adicionada agora. azul: s[i]. cinza: aresta já adicionada.
| i | s | f | s[i] | \{f,s[i]\} | s \text{ após} |
|---|---|---|---|---|---|
| 1 | \boxed{2}3951852 | 4 | 2 | \{4,2\} | \boxed{4}3951852 |
| 2 | 4\boxed{3}951852 | 6 | 3 | \{6,3\} | 4\boxed{6}951852 |
| 3 | 46\boxed{9}51852 | 3 | 9 | \{3,9\} | 46\boxed{3}51852 |
| 4 | 463\boxed{5}1852 | 7 | 5 | \{7,5\} | 463\boxed{7}1852 |
| 5 | 4637\boxed{1}852 | 9 | 1 | \{9,1\} | 4637\boxed{9}852 |
| 6 | 46379\boxed{8}52 | 1 | 8 | \{1,8\} | 46379\boxed{1}52 |
| 7 | 463791\boxed{5}2 | 8 | 5 | \{8,5\} | 463791\boxed{8}2 |
| 8 | 4637918\boxed{2} | 5 | 2 | \{5,2\} | 4637918\boxed{5} |
\begin{array}{c} i=9 > n-2=8 \\[0.6ex] \text{em } s=46379185,\ \text{não ocorrem } 2 \text{ e } 10 \\[0.6ex] T \leftarrow T \cup \{\{2,10\}\} \\[0.8ex] \begin{array}{l} \textbf{Árvore reconstruída:}\\ \{4,2\},\{6,3\},\{3,9\},\{7,5\},\\ \{9,1\},\{1,8\},\{8,5\},\{5,2\},\{2,10\} \end{array} \end{array}
Código Prüfer: Prova de Bijeção
Afirmação. Para todo conjunto V com n \ge 2 vértices e toda string a \in V^{n-2}, existe exatamente uma árvore T com vértices V e \text{Prüfer}(T) = a.
Prova: Indução em n. Usamos a observação vista antes: as folhas de T são exatamente os vértices que não ocorrem em \text{Prüfer}(T).
- Caso base (n = 2, a vazia): a única árvore com V = \{u, v\} é a aresta \{u, v\}.
- Hipótese de indução (HI): a afirmação vale para todo conjunto com n - 1 vértices.
- Passo (n \ge 3): escreva a = x\,a' e seja f o menor vértice de V que não ocorre em a.
- Toda árvore T com código a tem f como menor folha: a codificação remove f e registra seu vizinho, logo \{f, x\} \in T, e continua em T - f, cujo código é a'.
- Pela HI aplicada a V \setminus \{f\} (n - 1 vértices; a' não contém f), existe exatamente uma árvore T' com código a'.
- Logo T = T' \cup \{\{f, x\}\} é a única árvore com código a (e ela tem código a, pois f é sua menor folha). \blacksquare
Provando a Fórmula de Cayley
- A prova da bijeção transforma o problema de contar árvores em um problema de contar strings.
\begin{array}{c} \{\text{árvores rotuladas com vértices } 1,\ldots,n\}\\[0.4ex] \Updownarrow\ \text{bijeção de Prüfer}\\[0.4ex] \{\text{strings } a_1\ldots a_{n-2},\ a_i \in \{1,\ldots,n\}\} \end{array}
- Como a correspondência é bijetiva, os dois conjuntos têm exatamente o mesmo tamanho.
- Para contar as strings: há n escolhas independentes para cada uma das n-2 posições.
\#\{\text{árvores rotuladas}\} = \#\{\text{strings de Prüfer}\} = \underbrace{n \cdot n \cdots n}_{n-2 \text{ vezes}} = n^{n-2}
\boxed{\#\{\text{árvores rotuladas com } n \text{ vértices}\}=n^{n-2}}
Cálculo da Árvore Geradora Mínima
Cálculo da Árvore Geradora Mínima
Entrada: Um grafo não direcionado G=(V,E) e um custo c_e para cada aresta e\in E.
- Assume representação por lista de adjacência.
Saída: Uma árvore T=(V,E'), com E'\subseteq E, de custo mínimo (soma dos custos das arestas em E') que alcança todos os vértices.
- T não possui ciclos.
- T é conectado – contém um caminho entre todo par de vértices.
AGM e Caminhos Mínimos
Atenção: O problema da árvore geradora mínima e o problema do caminho mínimo são distintos.
T \subseteq G \qquad\Longrightarrow\qquad d_T(u,v) \ge d_G(u,v)
- Todo caminho em T também existe em G, mas G pode ter caminhos que não existem em T (pensando nos pesos como distâncias).
- Assim, uma AGM pode manter uma distância, mas também pode aumentá-la.
Distância preservada
d_G(1,3)=2 \quad d_T(1,3)=1+1=2
Distância aumentada
d_G(1,3)=\frac{3}{2} \quad d_T(1,3)=2
Atenção: Em relação ao grafo original, uma AGM minimiza o custo total de infraestrutura, mas remove redundância; por isso, pode tornar a rede menos robusta a falhas em arestas.
Árvore Geradora Mínima
Abordagem Gulosa: Constrói a solução passo a passo aplicando decisões locais que otimizam algum critério.
P. Qual decisão?
- Adiciona a T a aresta com menor custo que não forma um ciclo.
- Adiciona a T o vértice que minimiza o custo de conexão.
- Deleta de G a aresta com maior custo mantendo G conectado.
- Outras regras.
P. Alguma funciona?
Algoritmo de Prim
Algoritmo de Prim
Observação: O loop aumenta o número de vértices alcançados da menor forma possível.
Algoritmo de Prim: Exemplo de Execução
Execução de AlgoritmoPrimHeap no grafo do exercício, a partir de s = A. Empates: ordem alfabética.
| # | ExtraiMin | aresta em \textcolor{#3a7a10}{T} | \text{key} atualizadas (\text{pai}) | W(\textcolor{#3a7a10}{T}) |
|---|---|---|---|---|
| 0 | — | — | \text{key}[A]=0; demais \infty | 0 |
| 1 | (0, A) | — | \text{key}[B]=1 (A), \text{key}[C]=1 (A), \text{key}[D]=2 (A) | 0 |
| 2 | (1, B) | A–B | \text{key}[E]=4 (B) | 1 |
| 3 | (1, C) | A–C | \text{key}[F]=3 (C) | 2 |
| 4 | (2, D) | A–D | \text{key}[G]=5 (D) | 4 |
| 5 | (3, F) | C–F | nenhuma | 7 |
| 6 | (4, E) | B–E | \text{key}[G]=2 (E) | 11 |
| 7 | (2, G) | E–G | nenhuma | 13 |
Visualização do Algoritmo de Prim
Algoritmo de Prim: Implementação em Python
Implementação do algoritmo de Prim (e de Kruskal) em Python:
Veremos uma implementação eficiente, usando heaps, ao final da aula.
Corretude do Algoritmo de Prim
Corretude do Algoritmo de Prim
Teorema. O algoritmo de Prim computa uma MST.
Parte 1: Computa uma árvore geradora T^*.
- Fatos básicos sobre grafos em árvores geradoras.
Parte 2: T^* é uma MST.
- Propriedade do corte: a aresta de menor custo entre as duas partições de um corte deve necessariamente fazer parte de uma AGM do grafo.
Depois: Implementação eficiente usando heaps.
Corretude do Algoritmo de Prim: Ilustração
A aresta vermelha representa a escolha gulosa segura em um corte.
Corte
Definição: Um corte de um grafo G=(V,E) é uma partição de V em dois conjuntos não vazios.
Exemplo: corte (A,B) com A=\{1,2\},\qquad B=\{3,4,5\}. As arestas em vermelho cruzam o corte.
P. Quantos cortes um grafo com n vértices possui? 2^n-2 (todos os subconjuntos exceto \emptyset e V).
Lema do Corte Vazio
Lema do Corte Vazio. Um grafo é não conectado \iff \exists corte(A,B) sem arestas que cruzam o corte.
Prova.
- (\rightarrow) Assume RHS. Escolhe qualquer u\in A e v\in B. Já que não existe uma aresta que cruza(A,B) então não existe um caminho entre u,v em G. Assim, G não é conectado.
- (\leftarrow) Assume LHS. Não existe caminho entre u – v.
- A=\{Vértices alcançáveis em G a partir de u\}.
- B=\{G-A\}.
- Nenhuma aresta cruza corte(A,B) senão A seria maior. \blacksquare
Lema do Corte Vazio: Ilustração
Sem arestas cruzando (A,B), o grafo é desconexo.
Lema do Cruzamento-Duplo e Lema do Corte Solitário
Lema do Cruzamento-Duplo. Suponha que um ciclo C\subseteq E tem uma aresta cruzando o corte(A,B). Então?
- Alguma outra aresta também cruza o corte(A,B).
Lema do Corte Solitário. Se e é a única aresta que cruza algum corte(A,B). Então?
- Aresta e não pertence a nenhum ciclo.
Lema do Cruzamento-Duplo: Ilustração
Um ciclo que cruza um corte precisa cruzar novamente para retornar.
Lema do Corte Solitário: Ilustração
Se e é a única aresta de cruzamento, então e não pode estar em ciclo.
Corretude do Algoritmo de Prim
Afirmação. O algoritmo de Prim computa uma árvore geradora.
Prova. O algoritmo mantém o conjunto de arestas T que alcança todos os vértices em X.
O algoritmo gera T que alcança todos os vértices no término.
- Caso contrário não existe aresta que cruza o corte(X,V-X) e, pelo Lema do Corte Vazio, o grafo é não conectado.
Nenhum ciclo é criado em T.
- Considere uma iteração do algoritmo com atuais conjuntos X e T.
- Suponha que a aresta e é adicionada. O que pode ser dito sobre e?
- A aresta e é a primeira a cruzar (X,V-X) que é adicionada a T. Assim, pelo Lema do Corte Solitário não cria um ciclo. \blacksquare
Corretude do Algoritmo de Prim
Teorema. O algoritmo de Prim computa uma árvore geradora mínima.
P. Quando é seguro adicionar uma aresta a T?
Propriedade do Corte.
- Considere uma aresta e de G.
- Suponha que existe um corte(A,B) tal que e é a aresta de menor custo de G que o corta.
- Então e pertence à árvore geradora mínima de G.
Corretude do Algoritmo de Prim: Ilustração do Teorema
A menor aresta que cruza o corte é segura para estender a AGM.
Corretude do Algoritmo de Prim
Teorema. Propriedade do Corte \rightarrow O algoritmo de Prim computa uma árvore geradora mínima.
Prova. O algoritmo de Prim retorna uma árvore geradora T.
Toda aresta e adicionada pelo algoritmo é a menor aresta que cruza (X,V-X) e assim é justificada pela Propriedade do Corte.
Já que T é uma árvore geradora então T é uma árvore geradora mínima. \blacksquare
Propriedade do Corte
Propriedade do Corte
Propriedade do Corte. Considere uma aresta e de G. Suponha que existe um corte(A,B) tal que e é a aresta de menor custo de G que o corta. Então e pertence à árvore geradora mínima de G.
Plano:
- Prova por contradição usando o argumento da troca.
- Suponha que existe uma aresta e que possui o menor custo das arestas que cruzam um corte(A,B), e a aresta e não faz parte da árvore geradora mínima T^*.
- Troca e por outra aresta em T^* e obtém uma árvore geradora com custo ainda menor. Uma contradição.
Propriedade do Corte: Ilustração
T = T^* \cup \{\textcolor{#c40000}{e}\} - \{\textcolor{#6b777d}{e'}\}: \textcolor{#c40000}{e} e \textcolor{#6b777d}{e'} conectam o mesmo corte (\textcolor{#2e75b6}{A},\textcolor{#23373b}{B})
- Seja C o ciclo criado ao adicionar a aresta \textcolor{#c40000}{e} a uma árvore geradora mínima T^*.
- Pelo Lema do Cruzamento-Duplo, existe outra aresta \textcolor{#6b777d}{e'} \in C, com \textcolor{#c40000}{e} \neq \textcolor{#6b777d}{e'} e \textcolor{#6b777d}{e'} \in T^*, que cruza (\textcolor{#2e75b6}{A},\textcolor{#23373b}{B}).
- Definimos T = T^* \cup \{\textcolor{#c40000}{e}\} - \{\textcolor{#6b777d}{e'}\}.
- Então T ainda é uma árvore geradora e, como c_{\textcolor{#c40000}{e}} < c_{\textcolor{#6b777d}{e'}}, seu custo é menor que o de T^*, uma contradição.
Propriedade do Corte
Propriedade do Corte. Considere uma aresta \textcolor{#c40000}{e} de G. Suponha que existe um corte(\textcolor{#2e75b6}{A},\textcolor{#23373b}{B}) tal que \textcolor{#c40000}{e} é a aresta de menor custo de G que o corta. Então \textcolor{#c40000}{e} pertence à árvore geradora mínima de G.
Objetivo: Encontrar uma aresta \textcolor{#6b777d}{e'} tal que a troca por \textcolor{#c40000}{e} gere uma árvore geradora de G.
P. Como? Seja C o ciclo criado por adicionar \textcolor{#c40000}{e} a T^*.
Pelo Lema do Cruzamento-Duplo alguma outra aresta \textcolor{#6b777d}{e'} em C com \textcolor{#c40000}{e}\neq \textcolor{#6b777d}{e'} e \textcolor{#6b777d}{e'}\in T^* cruza (\textcolor{#2e75b6}{A},\textcolor{#23373b}{B}).
T=T^*\cup \{\textcolor{#c40000}{e}\}-\{\textcolor{#6b777d}{e'}\} é uma árvore geradora.
Assim, como c_{\textcolor{#c40000}{e}} < c_{\textcolor{#6b777d}{e'}}, T tem um custo menor que T^*, uma contradição. \blacksquare
Análise do Algoritmo de Prim
Análise do Algoritmo de Prim
P. Tempo de execução?
- O(n) iterações.
- O(m) por iteração.
- Total O(mn).
Análise do Algoritmo de Prim
Heap: Insere e extrai mínimo em tempo O(\log k), onde k é o número de elementos no heap.
Ideia: Uso de heap com as arestas candidatas a entrar na árvore.
- H guarda triplas (c, v, u): a aresta (u, v) de custo c = w(u, v), com u \in \textcolor{#2e75b6}{X}.
- Quando v entra em \textcolor{#2e75b6}{X}, inserimos em H as arestas de v para vértices fora de \textcolor{#2e75b6}{X}.
- Se a tripla extraída tem v \in \textcolor{#2e75b6}{X}, ela é obsoleta (a aresta formaria um ciclo) e é descartada.
P. Operação? Só Insert e ExtractMin: não precisamos de DecreaseKey (mesma ideia do Dijkstra com heap da aula 18).
Análise do Algoritmo de Prim
Análise do Algoritmo de Prim
Responsabilidade por Arestas
Uma aresta \{v, x\} é inserida em H (linha 15) no máximo uma vez: quando a primeira de suas pontas entra em \textcolor{#2e75b6}{X}. Quando a outra ponta entrar, a primeira já estará em \textcolor{#2e75b6}{X}.
- No máximo m + 1 triplas no heap, contando (0, s, \bot);
- Cada tripla é extraída no máximo uma vez: no máximo m + 1 chamadas de
ExtractMin(linha 6), incluindo as obsoletas descartadas (linhas 7 e 8).
Complexidade Total
\text{Operações de heap: } O(m) \qquad \text{Custo por operação: } O(\log m) = O(\log n) \text{pois } m \le n^2 \Rightarrow \log m \le 2 \log n \Rightarrow \text{Tempo total: } \boxed{O(m \log n)}
Obs: A parada antecipada ao completar |V| - 1 arestas (linhas 12 e 13) ajuda na prática, mas não muda o pior caso.
Implementação em Python
Implementação em Python
Ver também: arvore_geradora_minima.ipynb
Próxima Aula
- Vimos o problema da árvore geradora mínima, a propriedade do corte e o algoritmo de Prim, com complexidade O(m \log n) usando heaps.
- Na próxima aula, veremos o algoritmo de Kruskal e a estrutura de dados Union-Find.
?