Aula 5 - Introdução à Teoria de Grafos; Problema do Caminho Mínimo_EaD_atualizado_08_04_2020

Prévia do material em texto

Otimização em Redes
Teoria de Grafos: Problema do Caminho Mínimo; 
Problema da Árvore Geradora de Peso Mínimo.
Ormeu Coelho da Silva Júnior, D.Sc.
Departamento de Engenharia de Produção Revisão: Breno dos Santos de Assis, abr/2020.
PROBLEMA DO CAMINHO MÍNIMO
Há aplicações do Problema do Caminho Mínimo em que é necessário determinar as
distâncias entre diversos ou mesmo todos os pares de vértices da rede. Nestes casos, o
uso dos algoritmos de Dijkstra ou Ford pode não ser alternativa mais eficiente, pois eles
precisariam ser aplicados para cada par de vértices.
Em uma rede com 𝑛 vértices, o número de pares é dado pelas combinações destes, de
dois em dois, o que resulta em (𝑛2 – 𝑛)/2 pares. Nas redes não-orientadas há
exatamente uma cadeia de comprimento mínimo para cada um destes pares, enquanto,
na presença de orientação há dois caminhos para cada par, um de ida e outro de volta,
totalizando (𝑛2 – 𝑛) caminhos mínimos.
2
PROBLEMA DO CAMINHO MÍNIMO
Supondo um grafo sem ligações de valor negativo, estes caminhos mínimos poderiam
ser obtidos com o algoritmo de Dijkstra, cujo número de iterações no pior caso é Ο(𝑛2) –
leia-se “da ordem de n2”. Ou seja, como o número de caminhos a determinar também é
desta ordem de grandeza, vê-se que o uso do algoritmo de Dijkstra para mapear os
caminhos entre todos os pares de vértices, no pior caso, é Ο(𝑛4).
Todavia, estes caminhos podem ser calculados pelo algoritmo de Floyd em apenas
Ο ( 𝑛3 ), sendo, portanto, a alternativa mais eficiente. Nos slides seguintes são
apresentados os fundamentos deste algoritmo recurso, seu pseudocódigo e alguns
exemplos introdutórios.
3
ALGORITMO DE FLOYD
O algoritmo de Floyd opera de forma recursiva para determinar as distâncias entre todos
os pares de vértices de uma rede, mesmo na presença de arcos de valor negativo.
Entretanto, não devem existir ciclos/circuitos de comprimento negativo no grafo.
Dada uma ordenação dos vértices 𝑣1, 𝑣2, … , 𝑣𝑛 da rede, em cada iteração 𝑘, determinam-
se os caminhos mínimos entre todos os pares vértices que passem apenas pelos 𝑘
primeiros vértices, 𝑑𝑘(𝑖, 𝑗). Na iteração inicial, 𝑑0 𝑖, 𝑗 = C𝑖𝑗 para todos os arcos/arestas
(𝑖, 𝑗) existentes na rede, e 𝑑0 𝑖, 𝑗 = +∞, caso contrário. Para 𝑖 = 𝑗, tem-se 𝑑0 𝑖, 𝑗 = 0.
Na iteração 𝑘, se 𝑑𝑘 𝑖, 𝑗 = +∞, isso significa que nenhum caminho entre 𝑖 e 𝑗 foi
encontrado, seja direto ou através de um dos 𝑘 primeiros vértices,𝑣1, 𝑣2,..., 𝑣𝑘. Por outro
lado, se um caminho tiver sido determinado (𝑑𝑘 𝑖, 𝑗 < +∞), este caminho passará pelo
k-ésimo vértice, 𝑣𝑘, ou por um dos demais vértices já analisados, 𝑣1, 𝑣2,..., 𝑣𝑘−1.
ALGORITMO DE FLOYD
Se o caminho passar pelo k-ésimo vértice, ele será composto dos caminhos mínimos
entre 𝑖 e 𝑘, e entre 𝑘 e 𝑗, os quais passam por um dos primeiros (𝑘 − 1) vértices.
Portanto, em cada iteração 𝑘 (𝑘 = 1,… , 𝑛), o menor caminho de 𝑖 para 𝑗 através de
𝑣1, 𝑣2, … , 𝑣𝑘 é dado pela expressão recursiva:
Esta expressão mostra que podemos calcular o melhor caminho até a iteração k a partir
do melhor caminho até a iteração imediatamente anterior. Ou seja, na primeira iteração
se constrói 𝑑1 𝑖, 𝑗 a partir de 𝑑0 𝑖, 𝑗 , na segunda iteração se obtém 𝑑2 𝑖, 𝑗 a partir de
𝑑1 𝑖, 𝑗 e assim sucessivamente até a o obtenção de 𝑑𝑛 𝑖, 𝑗 , que corresponde ao valor
do caminho mínimo entre 𝑖 e 𝑗. Se 𝑑𝑛 𝑖, 𝑗 = +∞, então não existe um caminho entre 𝑖 e
𝑗 na rede. Em uma rede não orientada, um tal resultado é suficiente para caracterizar o
grafo como desconexo.
1 1 1min{ ; }   k k k kij ij ik kjd d d d
ALGORITMO DE FLOYD
Observe ainda que nas iterações intermediárias, 𝑘 < 𝑛 , o valor dos caminhos
encontrados até então serão tais que 𝑑𝑘 𝑖, 𝑗 > 𝑑𝑛 𝑖, 𝑗 . Caso haja um caminho melhor,
ele será obtido em uma iteração subsequente, através de um nó 𝑘’ ainda não testado.
Para recuperar os caminhos mínimos se usa uma estrutura de dados que permita
retraçá-los através do registro dos vértices predecessores. Mais precisamente, registra-
se o predecessor imediato de 𝑗, 𝑝𝑘(𝑖, 𝑗) = 𝑣’, no melhor caminho identificado até a k-
ésima iteração. Se numa iteração 𝑘’ seguinte, 𝑘’ > 𝑘, um caminho melhor for identificado
(passando por vértice 𝑘’), atualiza-se 𝑝𝑘
′
𝑖, 𝑗 com o valor de 𝑝𝑘
′−1 𝑘, 𝑗 . Ou seja, se o
melhor caminho agora passa por 𝑘’, então o predecessor imediato de j no caminho entre
𝑖 e 𝑗 é o mesmo que do que caminho entre 𝑘’ e 𝑗.
ALGORITMO DE FLOYD
A Figura 10 ilustra o argumento discutido no parágrafo anterior sobre a atualização dos
predecessores imediatos. Na iteração inicial registra-se como predecessor imediato o
vértice 𝑖, 𝑝0(𝑖, 𝑗) ⟵ 𝑖, visto que o caminho direto pelo arco/aresta (𝑖, 𝑗) é o único caminho
conhecido até o momento. Na k-ésima iteração, se 𝑑𝑘−1 𝑖, 𝑗 > 𝑑𝑘−1 𝑖, 𝑘 + 𝑑𝑘−1 𝑘, 𝑗 ,
então, atualiza-se 𝑝𝑘 𝑖, 𝑗 fazendo 𝑝𝑘 𝑖, 𝑗 ⟵ 𝑝𝑘−1 𝑘, 𝑗 .
i
v'
j
pk-1(i,j)
v‘’
k
pk-1(k,j)
Figura 10 – Atualização do predecessor imediato de j na k-ésima iteração
ALGORITMO DE FLOYD
Esta estrutura de dados usada para armazenar os predecessores imediatos é muitas
vezes chamada de “matriz de roteamento”. Logo, os cálculos para determinações de todos
os caminhos mínimos podem ser organizados em duas matrizes, que são atualizadas 𝑛
vezes até que se possa garantir a otimalidade de todos os caminhos na última iteração.
No algoritmo de Dijkstra, por exemplo, o critério de parada é a rotulagem do vértice de
destino. Tão logo isso ocorra o algoritmo para, mesmo que ainda haja vértices não
rotulados. Vértices estes para os quais não se conhece ainda um caminho mínimo. Na sua
k-ésima iteração, o algoritmo de Dijkstra rotula o k-ésimo vértice mais próximo da origem
𝑟. Portanto, é possível que o vértice de destino 𝑠 seja rotulado antes da iteração 𝑛.
Em cada iteração 𝑘 do algoritmo de Floyd, testa-se um caminho entre todos os pares de
vértices 𝑖 e 𝑗, através do vértice 𝑣𝑘 (o k-ésimo vértice do ordenamento considerado), tal
que 𝑖 ≠ 𝑣𝑘 e 𝑗 ≠ 𝑣𝑘. Logo, sua complexidade é 𝑂(𝑛3).
ALGORITMO DE FLOYD
dk: matriz de distâncias na iteração k pk: matriz de roteamento na iteração k
PASSO 1: Iniciando o algoritmo
k  0;
para ( i  V ) faça
para ( j  V) faça
pkij  i;
fim-para;
fim-para;
PASSO 2: construção de caminhos intermediários
para (k = 1,…,|V|) faça
para ( i V | i ≠ k ) faça
para ( j  V | j ≠ k e i ≠ j ) faça
se (dk-1(i,j) > dk-1(i,k) + dk-1(k,j) ) então
dk(i,j)  dk-1(i,k) + dk-1(k,j) ;
pk(i,j)  pk-1(k,j);
fim-se;
fim-para;
fim-para;
fim-para;
PASSO 3:
para ( i V | i ≠ k ) faça
para ( j  V | j ≠ k e i ≠ j ) faça ]
recupere a rota ótima: k1=p(j), k2=p(k1), k3=p(k2)... até atingir a origem, o nó i;
fim-para;
fim-para;
ALGORITMO DE FLOYD
Exemplo-5: Encontre os caminhos mínimos entre todos os pares de vértices da rede do 
exemplo 4, ilustrada novamente abaixo para facilitar a apresentação. 
𝑐23=2
𝑐24=2
4
1
2
3
6
5
𝑐35=5
𝑐45=1
Figura 11 – Rede do exemplo 4
ALGORITMO DE FLOYD
Resolução:
Passo 1:
Passo 2:
0 5 4 10 +∞ +∞
5 0 2 2 2 +∞
4 2 0 +∞ 5 +∞
10 2 +∞ 0 1 3
+∞ 2 5 1 0 2
+∞ +∞ +∞ 3 2 0
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5
6 6 6 6 6 6
ALGORITMO DE FLOYD
k = 1;
k = 2;
0 5 4 10 +∞ +∞
5 0 2 2 2 +∞
4 2 0 14 5 +∞
10 2 14 0 1 3
+∞ 2 5 1 0 2
+∞ +∞ +∞ 3 2 0
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 1 3 3
4 4 1 4 4 4
5 5 5 5 5 5
6 6 6 6 6 6
0 5 4 7 7 +∞
5 0 2 2 2 +∞
4 2 0 4 4 +∞
7 2 4 0 1 3
7 2 4 1 0 2
+∞ +∞ +∞ 3 2 0
1 1 1 2 2 1
2 2 2 2 2 2
3 3 3 2 2 3
2 4 2 4 4 4
2 5 2 5 5 5
6 6 6 6 6 6
ALGORITMO DE FLOYD
k = 3;
k = 4;
0 5 4 7 7 +∞
5 0 2 2 2 +∞
4 2 0 4 4 +∞
7 2 4 0 1 3
7 2 4 1 0 2
+∞ +∞ +∞ 3 2 0
0 5 4 7 7 10
5 0 2 2 2 5
4 2 0 4 4 7
7 2 4 0 1 3
7 2 4 1 0 2
10 5 7 3 2 0
1 1 1 2 2 4
2 2 2 2 2 4
3 3 3 2 2 4
2 4 2 4 4 4
2 5 2 5 5 5
2 4 2 6 6 6
1 1 1 2 2 1
2 2 2 2 2 2
3 3 3 2 2 3
2 4 2 4 4 4
2 5 2 5 5 5
6 6 6 6 66
ALGORITMO DE FLOYD
k = 5;
k = 6;
0 5 4 7 7 9
5 0 2 2 2 4
4 2 0 4 4 6
7 2 4 0 1 3
7 2 4 1 0 2
9 4 6 3 2 0
0 5 4 7 7 9
5 0 2 2 2 4
4 2 0 4 4 6
7 2 4 0 1 3
7 2 4 1 0 2
9 4 6 3 2 0
1 1 1 2 2 5
2 2 2 2 2 5
3 3 3 2 2 5
2 4 2 4 4 4
2 5 2 5 5 5
2 5 2 6 6 6
1 1 1 2 2 5
2 2 2 2 2 5
3 3 3 2 2 5
2 4 2 4 4 4
2 5 2 5 5 5
2 5 2 6 6 6
ALGORITMO DE FLOYD
Passo3: (recuperação dos caminhos ótimos)
De 1 p/ 2: 𝑝(1,2) = 1 ⇒ 𝑃12 = { 1,2 }
De 1´p/ 3: 𝑝(1,3) = 1 ⇒ 𝑃13 = 1,3
De 1 p/ 4: 𝑝(1,4) = 2 ⇒ 𝑝(1,2) = 1 ⇒ 𝑃14 = 1,2 , 2,4
De 1 p/ 5: 𝑝(1,5) = 2 ⇒ 𝑝(1,2) = 1 ⇒ 𝑃15 = 1,2 , 2,5
De 1 p/ 6: 𝑝(1,6) = 5 ⇒ 𝑝(1,5) = 2 ⇒ 𝑝(1,2) = 1 ⇒ 𝑃16 = 1,2 , 2,5 , 5,6
⋮
De 5 p/ 6: 𝑝(5,6) = 5 ⇒ 𝑃56 = 5,6
□
Em cada iteração 𝑘, deve-se a aplicar a função recursiva para todos os pares de vértices i
e j, tal que 𝑖 ≠ 𝑗, 𝑖 ≠ 𝑘 e 𝑗 ≠ 𝑘. Logo, tem-se um total de 6 iterações, sendo realizadas
dezesseis atualizações da função de recursão em cada um delas. Note que todas as
células da diagonal principal e aquelas nas linhas e colunas destacadas em azul não
precisam ser atualizadas.
ALGORITMO DE FLOYD
Observe ainda que as matrizes de distância são simétricas em qualquer iteração, pois o
grafo é não-orientado. Porém o mesmo não acontece na matriz de roteamento. Tome o
caminho entre 1 e 6 como exemplo. Como se viu no passo 3, este caminho é dado por
1,2 , 2,5 , 5,6 . Desta forma, o predecessor imediato de 6 no caminho de 1 para 6 é 5
(𝑝(1,6) = 5 ), enquanto o no caminho de 6 para 1, o predecessor imediato de 1 é o vértice
2 (𝑝(6,1) = 2). Os resultados dos cálculos referente à célula (𝑖, 𝑗) podem ser aproveitados
para poupar os cálculos da célula 𝑗, 𝑖 , mas deve-se tomar os devidos cuidados para a
atualização da matriz de roteamento R.
Para ilustrar as operações que produziram os resultados nos slides 12 a 15, a seguir estão
ilustrados os cálculos das células das matrizes (2,3) e (3,4) das matrizes D e P, na
primeira iteração:
𝐷123 = min 𝐷
0
23; 𝐷
0
21 +𝐷
0
13 = min 2; 5 + 4 ⇒ 𝑃
1 2,3 = 𝑃0 2,3 [ inalterado ]
𝐷134 = min 𝐷
0
34; 𝐷
0
31+ 𝐷
0
14 = min +∞;4 + 10 = 14 ⇒ 𝑃
1 2,3 = 𝑃0 1,4 [ alterado ] 
ÁRVORES EM GRAFOS
Na aula 4 foram apresentadas algumas definições preliminares sobre grafos, dentre as
quais aquela que diz que “árvore é um grafo conexo sem ciclos”. Há outras formas de se
caracterizar uma árvore e a proposição abaixo estabelece a equivalência delas. Ela não
será provada, pois foge ao foco do presente curso. O leitor pode buscar mais
informações na bibliografia listada ao final desta aula. Ao invés de provar a equivalência
destas afirmações será mostrada a partir das árvores na Figura 12.
Proposição: Um grafo G = (V,E) é uma árvore sse:
(i) é uma floresta com exatamente n-1 arestas, sse
(ii) é o grafo “aresta-minimal” que cobre os vértices de G, sse
(iii) ele contém um único caminho entre cada par de vértices, sse
(iv) a adição de uma nova aresta em E cria um único ciclo. 
17
ÁRVORES EM GRAFOS
18
Figura 12 – Exemplo de 3 árvores com 5 vértices e 9 vértices
(a)
(b) (c) (d)
ÁRVORES
O grafo na Figura 12(a) pertence a uma família de grafos denominada de estrelas. Para
melhor definir o que é uma estrela, cabe antes definir o que é grau de um vértice. Em
grafos não orientados simples, o grau de um vértice 𝑣 ∈ 𝑉, 𝑔𝑟(𝑣), pode ser como o
número de arestas que nele incidem. Em uma estrela há (𝑛 − 1) vértices com grau 1 e
um vértice com grau (𝑛 − 1), no caso o vértice central. A Figura 12(b) explicita o fato de
que toda cadeia é uma árvore com (𝑛 − 2) vértices de grau 2, e dois vértices com grau
1. As árvores nas Figuras 12(c)-(d) não pertencem a famílias específicas.
Tome qualquer uma das árvores nas Figuras 12(a)-(d) para verificar uma a uma as
afirmações na proposição anterior. Por exemplo, a partir das definições preliminares na
aula 4, vê-se que que todos estes grafos são florestas com exatamente (𝑛 − 1) arestas.
O conjunto das arestas de qualquer destes grafos é minimal, uma vez que não é
subconjunto de nenhuma outra árvore com o mesmo conjunto de vértices.
19
ÁRVORES
Tome qualquer par de vértices nesta rede e você verá que existe apenas um conjunto de
arestas entre qualquer par de vértices. E, por fim, note que a inserção de uma aresta
ligando qualquer um destes pares produz um ciclo no grafo, definindo um caminho
alternativo ao que já existia na árvore.
Outra definição que é importante relembrar é a de árvore geradora. Dada uma rede 𝐺 =
(𝑉, 𝐸), define-se como árvore geradora de 𝐺 um sub-grafo 𝑆𝑇 = (𝑉, 𝐸’) que possua o
mesmo conjunto de vértices, mas apenas um subconjunto das arestas, 𝐸′ ⊆ 𝐸
(obviamente, sendo uma árvore, 𝐸′ = 𝑛 − 1). Se o próprio G não for uma árvore,
existirá mais de uma árvore geradora de 𝐺.
20
PROBLEMA DA ÁRVORE GERADORA MÍNIMA
Em uma rede, orientada ou não, define-se como árvore geradora de peso mínimo a
árvore geradora cuja soma dos pesos de suas ligações seja mínimo. O problema possui
interesse prático, principalmente no projeto de redes de comunicação, na distribuição
de energia e água, na coleta de esgoto e em diversos problemas que envolvem o
transporte de fluidos em dutos.
Ele pertence a uma classe de problemas de otimização cuja estrutura é uma
generalização de grafos denominada matróide. Todos os problemas com esta estrutura
são suscetíveis de resolução em tempo polinomial por um algoritmo de guloso, como o
algoritmo de Prim, que será visto logo adiante.
21
PROBLEMA DA ÁRVORE GERADORA MÍNIMA
O teorema apresentado abaixo é base de todos os algoritmos eficientes para o
Problema da Árvore Geradora de Peso Mínimo.
Teorema: Seja um {(𝑈1, 𝑇1), (𝑈2, 𝑇2), … , (𝑈𝑘, 𝑇𝑘)} uma floresta geradora de 𝑉, e seja
(𝑢, 𝑣) o arco de menor peso 𝑤𝑢,𝑣, tal que 𝑣 ∈ 𝑈1 e 𝑣 ∉ 𝑈1. Logo, dentre todas as árvores
geradoras com arestas no conjunto 𝑇 = 𝑗=1
𝑘 𝑇𝑗 , há ao menos uma árvore ótima
contendo a aresta (𝑢, 𝑣).
Este resultado leva quase que diretamente a um algoritmo polinomial para o problema. 
Sendo o teorema válido para todas as florestas geradoras de 𝑉, ele também é válido 
quando 𝑈𝑗 = {𝑣𝑗}, 𝑗 = 1, … , 𝑛 e 𝑇 = ∅. Pela aplicação do teorema anterior, pode-se 
afirmar que a aresta de menor peso com uma extremidade em 𝑈1 = {𝑢1} pertence a (ao 
menos) uma árvore geradora mínima. Seja 𝑢1, 𝑢2 esta aresta. 
22
PROBLEMA DA ÁRVORE GERADORA MÍNIMA
Agora, aplica-se o teorema aos conjuntos 𝑈1 = {𝑢1, 𝑢2}, 𝑈3 = {𝑢3}, 𝑈4 = {𝑢4},..., 𝑈𝑛 =
𝑢𝑛 e 𝑇 = 𝑢1, 𝑢2 , para obter o arco de menor peso que possui apenas uma
extremidade no conjunto 𝑈1, 𝑢1 ou 𝑢2. Repete-se então este processo até que a árvore
ótima seja formada.
Tem-se assim um algoritmo para o problema, que consiste em, iniciando de um vértice
qualquer, adicionar novos vértices à árvore pela adição da aresta de menor peso que
conecta um vértice que já está na árvore com outro que ainda não foi incluído. Este é o
algoritmo de Prim, capaz de resolver eficientemente o Problema da Árvore Geradora de
Peso Mínimo em 𝛰 𝑛2 .
23
ALGORITMO DE PRIM
Dados de entrada:
G = (V,E); Cij, i,j  V.
Dados de saída:
ST – árvore geradora mínima.
LST – comprimento da árvore geradora mínima.
Passo 1:
LST ← 0;
C ← {v}; “escolha arbitrária de um vértice”
C’ ← V – C;
ST ← { };
24
ALGORITMO DE PRIM
Passo 2: 
enquanto (C’ ≠ {} ) faça
selecione (k,j)  E tal que dkj = minr,s {drs : r  C, s  C’}
LST ← LST + dkj;
C ← C  {j};
C’ ← C’ \ {j};
ST ← ST  {(k,j)};
fim-enquanto;
25
ALGORITMO DE PRIM
Exemplo-6: Encontre a árvore geradora de peso mínimo para a rede do exemplo 5.
Resolução:
Passo 1:
LST = 0;
C ← {1};
C' ← {2, 3, 4, 5, 6};
ST = { };
Passo 2:
k = 1;
LST = 4;
C ← {1, 3};
C' ← {2, 4, 5, 6};
ST = {(1,3)};
k = 2;
LST = 6;
C ← {1, 2, 3};
C' ← {4, 5, 6};
ST = {(1,3), (2,3)};
k = 3;
LST = 8;
C ← {1, 2, 3, 4};
C' ← {5, 6};
ST = {(1,3), (2,3), (2,4)};
ALGORITMO DE PRIM
Resolução:
k = 4;
LST = 9;
C ← {1, 2,3, 4, 5};
C' ← { 6 };
ST = {(1,3), (2,3), (2,4),(4,5)};
□
A árvore ótima possui peso 11 e é formada pelo conjunto de arestas {(1,3), (2,3), 
(2,4),(4,5),(5,6)}. As figuras 13 a 15 apresentam os sub-grafos obtidos a cada iteração 
e a árvore ótima. Para facilitar a visualização, as arestas selecionadas foram ilustradas 
em vermelho sobre a rede original. Ao afinal, a árvore ótima é apresentada em 
destaque na Figura 15.
k = 5;
LST = 11;
C ← {1, 2, 3, 4, 5, 6};
C' ← {};
ST = {(1,3), (2,3), (2,4),(4,5),(5,6)};
ALGORITMO DE PRIM
28
𝑐23=2
𝑐24=2 4
1
2
3
6
5𝑐35=5
𝑐45=1
𝑐23=2
𝑐24=2 4
1
2
3
6
5𝑐35=5
𝑐45=1
Figura 13 – 1ª e 2ª iterações do algoritmo de Prim nos dados do exemplo 6
1ª iteração
2ª iteração
ALGORITMO DE PRIM
29
𝑐23=2
𝑐24=2 4
1
2
3
6
5𝑐35=5
𝑐45=1
𝑐23=2
𝑐24=2 4
1
2
3
6
5𝑐35=5
𝑐45=1
Figura 14 – 3ª e 4ª iterações do algoritmo de Prim nos dados do exemplo 6
3ª iteração
4ª iteração
ALGORITMO DE PRIM
30
𝑐23=2
𝑐24=2 4
1
2
3
6
5𝑐35=5
𝑐45=1
Figura 15 – 5ª iteração do algoritmo de Prim nos dados do exemplo 6 e a árvore ótima em destaque
𝑐23=2
𝑐24=2 4
1
2
3
6
5
𝑐45=1
5ª iteração
Árvore ótima
OUTROS PROBLEMAS EM ÁRVORES
Problema da Floresta (Árvore) Geradora de Peso Máximo: Neste problema se procura
determinar a floresta (ou árvore) de Peso Máximo. Ele também pode ser resolvido em
tempo polinomial e por um algoritmo guloso, assim como o Problema da Árvore
Geradora de Peso Mínimo, com o qual guarda estreita relação.
Árvore de Caminhos Mínimos (a partir do vértice 𝑟): É a árvore formada pelas arestas
(arcos) dos caminhos mínimos entre 𝑟 e cada um dos demais vértices. Ao conectar
estes (𝑛 − 1) caminhos ótimos, obtém-se necessariamente uma árvore, pois, se
existissem ciclos, ao menos um dos caminhos mínimos não seria ótimo. Para obter
todos os caminhos a partir de um dado vértice origem podem ser usados os algoritmos
de Dijkstra ou Ford, parando-se quando todos os vértices tiverem sido rotulados.
31
OUTROS PROBLEMAS EM ÁRVORES
Problema da Árvore de Steiner: Dado um grafo 𝐺 = (𝑉, 𝐸) e um conjunto de terminais 𝑇,
𝑇 ⊆ 𝑉, uma árvore de Steiner contém todos os vértices em 𝑇, podendo ter ou não
arestas incidentes nos demais vértices, 𝑉\T. O Problema da Árvore de Steiner consiste
na determinação da árvore de Steiner de peso mínimo. Trata-se de um problema NP-
difícil, ao contrário daqueles citados no slide anterior, que pertencem à classe P.
32
BIBLIOGRAFIA
 ARENALES, M. et al., Pesquisa Operacional para Cursos de Engenharia. Rio de 
Janeiro: Elsevier, 2007. 
 GOLDBARG, M.C. e LUNA, H.P., Otimização Combinatória e Programação Linear. 
Rio de Janeiro: Elsevier, 2005. 
 PAPADIMITRIOU, C.H., STEIGLITZ, K. Combinatorial Optimization: Algoritmos e 
Complexidade. Mineola: Dover Publications, 1998.
 TAHA, H.A., Pesquisa Operacional, 8. ed.. São Paulo: Pearson Prentice Hall, 2008.
 WOLSEY, L.A., Integer Programming. New York: John Wiley & Sons, 1998.
33