(Estas versões do sumário e do índice remissivo podem estar ligeiramente desatualizadas. Veja páginas 2 a 7 e 163 a 164 do livro.)
Introdução
- Resumo de programação linear e dualidade
- Conceitos básicos de redes
Caminhos e ciclos
- Algoritmos de busca
- Ciclos e ordenação topológica
- Caminhos de comprimento mínimo (busca em largura)
- Caminho de custo mínimo (Ford-Bellman)
- Ciclos de custo negativo (Ford-Bellman)
- Caminho mínimos sob custos não-negativos (Dijkstra)
- Caminho mínimos em redes acíclicas
Fluxo
- Fluxo: introdução
- Fluxo máximo
- Redes simétricas e pseudofluxo
- Algoritmo de Ford-Fulkerson
- Fluxo: capacity scaling
- Fluxo: algoritmo de Edmonds-Karp
- Fluxo: algoritmo layered networks de Dinits
- Preflow-push: algoritmo básico
- Preflow-push: implementação FIFO
Fluxo viável de custo mínimo
- Fluxo viável
- Fluxo viável de custo mínimo: introdução
- Fluxo em redes simétricas
- Algoritmo de Klein (O(n m2 CU))
- Algoritmo de Jewell (O(n3 B))
- Algoritmo cost scaling (O(n2 m log(nC)))
- Algoritmo do ciclo de custo médio mínimo (O(n2 m3 log n))
- Circulações com limites inferiores
Este índice dá a página do livro onde cada termo técnico é definido. (Esta versão do índice pode estar ligeiramente desatualizada. Veja as páginas 163 a 164 do livro.)
acúmulo ... 69, 86
alcance ... 13
ao alcance ... 13
arco ... 11
direto ... 26, 50, 77
entra ... 11
folgado ... 31, 34
inverso ... 26, 50, 77
justo ... 31, 34, 42, 53, 59, 103, 112
positivo ... 25, 37
relaxado ... 31, 34, 42, 53, 59
sai ... 11
secundário ... 83
tenso ... 31, 34, 42, 53, 59, 149
vital ... 82
arcos
anti-paralelos ... 11
inversos ... 11
bipartição ... 101
busca
em largura ... 24
em profundidade ... 24
caminho ... 13
bem-casado ... 45
de incremento ... 88
determinado por ... 14
mínimo ... 39
capacidade
de arco ... 75
de corte ... 76
carga ... 114
de nó ... 114
ciclo ... 13
circulação ... 70, 157
definida por ... 70
elementar ... 70
respeita ... 157
circulação
satisfaz ... 157
coleção
disjunta ... 82
comprimento
de passeio ... 13
concatenação
de passeios ... 13
corte ... 15, 19
determinado por ... 15
mínimo ... 77
custo
de arco ... 39, 132
de fluxo ... 132
de passeio ... 39
médio ... 152
mínimo ... 39
reduzido ... 48
demanda ... 16
desigualdade
triangular ... 41, 58
excesso ... 69, 86
fase
de algoritmo ... 95, 105, 121, 122
fluxo ... 69, 72, 125
de _ a _ ... 72
definido por ... 72
elementar ... 72
maximal ... 78
máximo ... 118
normalizado ... 86
ótimo ... 132
respeita ... 125
satisfaz ... 125
viável ... 125, 132
folgas complementares ... 134, 148
fonte ... 76
fortemente polinomial ... 17
fracamente polinomial ... 17
função parcial ... 14
função-capacidade ... 16, 75
ímpar ... 81
par ... 81
função-custo ... 16, 39, 51, 132
anti-simétrica ... 139
função-demanda, 125
função-limite-inferior ... 157
função-predecessor ... 14
função-sucessor ... 36
grafo ... 11
acíclico ... 27
de predecessores ... 14
de sucessores ... 36
denso ... 12
dirigido ... 11
esparso ... 12
orientado ... 11
residual ... 88
simétrico ... 11 ... 85
simples ... 11
grau
entrada ... 11
saída ... 11
invariantes ... 20
lista
incidência ... 12
matriz
adjacências ... 12
incidência ... 12
nó ... 11
ativo ... 111
ordem
topológica ... 28
origem
de passeio ... 13
otimalidade
de fluxo ... 156
passeio ... 13
degenerado ... 13
ponta
final ... 11
inicial ... 11
negativa ... 11
positiva ... 11
potencial ... 16, 19, 27, 32, 41, 51, 58
ótimo ... 35, 36, 42, 58
pré-fluxo ... 16, 110
problema
dual ... 9
ilimitado ... 9
viável ... 9
pseudocaminho ... 26, 50, 77
de incremento ... 77
positivo ... 127
pseudofluxo ... 16, 86
respeita ... 86
pseudopolinomial ... 17
quantidade
de fluxo ... 72
quantidade de fluxo ... 71
quase-caminho ... 13
rede ... 15
representam ... 72
respeita ... 75
rótulo ... 32, 102
saturação
de arco ... 100, 113
segmento
de passeio ... 13
final ... 13
inicial ... 13
separa ... 15, 19, 72
solução
dual-viável ... 133
ótima ... 9
viável ... 9
sorvedouro ... 76
subgrafo ... 12
teorema
Gale ... 127
Hoffman ... 158
término
de passeio ... 13
vai de _ a _ ... 13
valor
de fluxo ... 72, 118