Se eu entendi direito, o que se pede para provar na parte (2) do exercício é falso. Alguém sabe o que fura nesse contra-exemplo?
N = {s, t, i, j}
A = {st, si, ij, jt}
y(s) = 0, y(t) = 1, y(i) = 1, y(j) = 2
z(s) = 1, z(t) = 2, z(i) = 0, z(j) = 1
Temos que y é um 1-potencial (s, *) ótimo, z é um 1-potencial (*, t) ótimo, ainda z(j) - z(i) = 1 = y(j) - y(i), mas o arco ij não pertence a um s-t caminho mínimo.
Ola, pode ser q no enunciado esteja faltando a seguinte consideracao:
(2) Prove que z(j)-z(i) = 1 = y(j) - y(i) para algum arco ij de algum caminho de s a t, entao ij pertence a um caminho que tem comprimento minimo.
Ateh porque, qualquer grafo q tenha um arco st e outros arcos eh um contra exemplo.
faz sentido?!
(2) Prove que z(j)-z(i) = 1 = y(j) - y(i) para algum arco ij de algum caminho de s a t, entao ij pertence a um caminho que tem comprimento minimo.
Ateh porque, qualquer grafo q tenha um arco st e outros arcos eh um contra exemplo.
faz sentido?!
no contraexemplo que eu dei tem um s-t caminho que usa ij: s, i, j, t
acho que o seu contra exemplo falha no seguinte: os vértices i e j ditos no enunciado não são necessariamente os que você nomeou, mas i e j quaisquer no grafo, desde que adjacentes.
Vamos chamar no seu exemplo i de a e j de b, e usar t = j e s = i, pra não confundir com os que vc citou. Usando os potenciais dados, a afirmativa é valida, não?
Vamos chamar no seu exemplo i de a e j de b, e usar t = j e s = i, pra não confundir com os que vc citou. Usando os potenciais dados, a afirmativa é valida, não?
O enunciado não fala deve existir uma escolha de i e j tais a propriedade se verifique, mas que para qualquer ij em A tal que y(j)-y(i) = 1 = z(j)-z(i), então existe um s-t caminho de comprimento mínimo que passe por ij.
O que pode acontecer é que se queira que use a suposição do item (1), de que existe um s-t caminho de comprimento mínimo que passe por i (ou j), aí acredito que a proposição será verdadeira.
O que pode acontecer é que se queira que use a suposição do item (1), de que existe um s-t caminho de comprimento mínimo que passe por i (ou j), aí acredito que a proposição será verdadeira.
Vcs resolveram essa dúvida?
Eu transformei o enunciado e consegui resolver (acho):
(2) Prove que, se i é um vértice de um st-caminho de comprimento mínimo, e z(j) - z(i) = 1 = y(j) - y(i) para algum arco ij, então ij pertence a um caminho de s a t que tem comprimento mínimo.
Seria bom uma resposta oficial a respeito desta questão. Realmente parece que o enunciado está incompleto, mas o que exatamente falta nele?
Para mim ao invés de mudar o enunciado preferi deixar um contra-exemplo!
Eu acabei dando esse contra-exemplo acima, depois coloquei uma demonstração com a suposição adicional de que existe um caminho mínimo que passe por i.
Acho que seu contra-exemplo está realmente quebrando o enunciado. Valeu pela observação! E eu que já tinha provado a propriedade achando que estava abafando 