Perguntaram sobre todos os que eu tinha entendido bem o enunciado ^_^
Exercício 6.1: Entendi da seguinte forma: Seja P = V . W um caminho de custo mínimo e sejam V e W caminhos. Assim, V é um segmento inicial de P. Devemos provar que V não pode não ser um caminho de custo mínimo se a rede tiver ciclo negativo. É isso?
Exercício 8.12: O enunciado não diz exatamente o que é pra fazer. Supus que era pra dar um algoritmo e provar sua correção. Era isso mesmo?
>Perguntaram sobre todos os que eu tinha entendido bem o enunciado ^_^
>
>Exercício 6.1: Entendi da seguinte forma: Seja P = V . W um caminho de custo >mínimo e sejam V e W caminhos. Assim, V é um segmento inicial de P. >Devemos provar que V não pode não ser um caminho de custo mínimo se a rede >tiver ciclo negativo. É isso?
É tá meio confuso isso... Bom, pra mim o enunciado é o seguinte:
Encontre uma rede (N, V, c) tal que exite um caminho (não passeio, essa é uma distinção importante aqui) minimo P = (s, ..., t) de 's' a 't', com a seguinte propriedade: existe um 'w' pertencente a P, tal que o caminho induzido por P de 's' a 'w' não é mínimo para a rede (N, V, c).
A parte do ciclo negativo é uma dica, esse caminho P só é possível se a rede possuir um ciclo negativo.
>Exercício 8.12: O enunciado não diz exatamente o que é pra fazer. Supus que >era pra dar um algoritmo e provar sua correção. Era isso mesmo?
Foi isso o que fiz.
>
>Exercício 6.1: Entendi da seguinte forma: Seja P = V . W um caminho de custo >mínimo e sejam V e W caminhos. Assim, V é um segmento inicial de P. >Devemos provar que V não pode não ser um caminho de custo mínimo se a rede >tiver ciclo negativo. É isso?
É tá meio confuso isso... Bom, pra mim o enunciado é o seguinte:
Encontre uma rede (N, V, c) tal que exite um caminho (não passeio, essa é uma distinção importante aqui) minimo P = (s, ..., t) de 's' a 't', com a seguinte propriedade: existe um 'w' pertencente a P, tal que o caminho induzido por P de 's' a 'w' não é mínimo para a rede (N, V, c).
A parte do ciclo negativo é uma dica, esse caminho P só é possível se a rede possuir um ciclo negativo.
>Exercício 8.12: O enunciado não diz exatamente o que é pra fazer. Supus que >era pra dar um algoritmo e provar sua correção. Era isso mesmo?
Foi isso o que fiz.