Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012
Thomas CormenIBSN: 9788535236996Elaborado por professores e especialistas
Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up
Consideremos uma árvore geradora mínima e uma aresta
. Seja
, com
. A árvore
mostra o vértice
e a árvore
mostra o vértice
. Do mesmo modo, temos que
, onde
contém os vértices de
e
contém os vértices de
.
Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up
Os vértices formam o corte que é cruzado pela aresta
com relação a
. Consideremos que existe uma aresta
onde o peso de
é menor do que o peso de
, isto é,
. A nova árvore geradora
pode ser definida como
, com peso
.
Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up
Adicionando o zero na equação do peso de (no caso
) temos:
Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up
Esse resultado contradiz a afirmação que para todo
, que passa pelo corte
. Então a aresta
é a aresta de peso mínimo que passa pelo corte.
Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up
Portanto, pertence a alguma árvore geradora mínima de
.
Navegar por capítulo
- Capítulo A.A
- Capítulo A.A1
- Capítulo A.A2
- Capítulo A.B
- Capítulo A.B1
- Capítulo A.B2
- Capítulo A.B3
- Capítulo A.B4
- Capítulo A.B5
- Capítulo A.C
- Capítulo A.C1
- Capítulo A.C2
- Capítulo A.C3
- Capítulo A.C4
- Capítulo A.C5
- Capítulo A.D
- Capítulo A.D1
- Capítulo A.D2
- Capítulo 1.1
- Capítulo 1.2
- Capítulo 2
- Capítulo 2.1
- Capítulo 2.2
- Capítulo 2.3
- Capítulo 3
- Capítulo 3.1
- Capítulo 3.2
- Capítulo 4
- Capítulo 4.1
- Capítulo 4.2
- Capítulo 4.3
- Capítulo 4.4
- Capítulo 4.6
- Capítulo 5
- Capítulo 5.1
- Capítulo 5.2
- Capítulo 5.3
- Capítulo 5.4
- Capítulo 6
- Capítulo 6.1
- Capítulo 6.2
- Capítulo 6.3
- Capítulo 6.4
- Capítulo 6.5
- Capítulo 7
- Capítulo 7.1
- Capítulo 7.2
- Capítulo 7.3
- Capítulo 7.4
- Capítulo 8
- Capítulo 8.1
- Capítulo 8.2
- Capítulo 8.3
- Capítulo 8.4
- Capítulo 9
- Capítulo 9.1
- Capítulo 9.2
- Capítulo 9.3
- Capítulo 10
- Capítulo 10.1
- Capítulo 10.2
- Capítulo 10.3
- Capítulo 10.4
- Capítulo 11
- Capítulo 11.1
- Capítulo 11.2
- Capítulo 11.3
- Capítulo 11.4
- Capítulo 11.5
- Capítulo 12
- Capítulo 12.1
- Capítulo 12.2
- Capítulo 12.3
- Capítulo 12.4
- Capítulo 13
- Capítulo 13.1
- Capítulo 13.2
- Capítulo 13.3
- Capítulo 13.4
- Capítulo 14
- Capítulo 14.1
- Capítulo 14.2
- Capítulo 14.3
- Capítulo 15
- Capítulo 15.1
- Capítulo 15.2
- Capítulo 15.3
- Capítulo 15.4
- Capítulo 16
- Capítulo 16.1
- Capítulo 16.2
- Capítulo 16.3
- Capítulo 16.4
- Capítulo 16.5
- Capítulo 17
- Capítulo 17.1
- Capítulo 17.2
- Capítulo 17.3
- Capítulo 17.4
- Capítulo 18
- Capítulo 18.1
- Capítulo 18.2
- Capítulo 18.3
- Capítulo 19
- Capítulo 19.2
- Capítulo 19.3
- Capítulo 19.4
- Capítulo 20
- Capítulo 20.1
- Capítulo 20.2
- Capítulo 20.3
- Capítulo 21
- Capítulo 21.1
- Capítulo 21.2
- Capítulo 21.3
- Capítulo 21.4
- Capítulo 22
- Capítulo 22.1
- Capítulo 22.2
- Capítulo 22.3
- Capítulo 22.4
- Capítulo 22.5
- Capítulo 23
- Capítulo 23.1
- Capítulo 23.2
- Capítulo 24
- Capítulo 24.1
- Capítulo 24.2
- Capítulo 24.3
- Capítulo 24.4
- Capítulo 24.5
- Capítulo 25
- Capítulo 25.1
- Capítulo 25.2
- Capítulo 25.3
- Capítulo 26
- Capítulo 26.1
- Capítulo 26.2
- Capítulo 26.3
- Capítulo 26.4
- Capítulo 26.5
- Capítulo 27
- Capítulo 27.1
- Capítulo 27.2
- Capítulo 27.3
- Capítulo 28
- Capítulo 28.1
- Capítulo 28.2
- Capítulo 28.3
- Capítulo 29
- Capítulo 29.1
- Capítulo 29.2
- Capítulo 29.3
- Capítulo 29.4
- Capítulo 29.5
- Capítulo 30
- Capítulo 30.1
- Capítulo 30.2
- Capítulo 30.3
- Capítulo 31
- Capítulo 31.1
- Capítulo 31.2
- Capítulo 31.3
- Capítulo 31.4
- Capítulo 31.5
- Capítulo 31.6
- Capítulo 31.7
- Capítulo 31.8
- Capítulo 31.9
- Capítulo 32
- Capítulo 32.1
- Capítulo 32.2
- Capítulo 32.3
- Capítulo 32.4
- Capítulo 33
- Capítulo 33.1
- Capítulo 33.2
- Capítulo 33.3
- Capítulo 33.4
- Capítulo 34
- Capítulo 34.1
- Capítulo 34.2
- Capítulo 34.3
- Capítulo 34.4
- Capítulo 34.5
- Capítulo 35
- Capítulo 35.1
- Capítulo 35.2
- Capítulo 35.3
- Capítulo 35.4
- Capítulo 35.5
Aprenda agora com os exercícios mais difíceis
junte-se a outros estudantes
- +11 milhões
R$29,90/mês
Cancele quando quiser, sem multaAproveite também
- check Exercícios passo a passo
- check Resumos por tópicos
- check Disciplinas ilimitadas
- check Ferramentas para otimizar seu tempo