Número:
Enunciado: Considere as seguintes afirmações:
I - Todo caminho disjunto nas arestas também é disjunto nos vértices.
II - Todo caminho maximal em uma árvore é uma orelha da árvore.
III - O grafo linha de Cn é Cn, e o grafo linha de Kn é Kn(n-1)/2.
IV - Seja N uma rede composta pelos vértices s e t, e um digrafo D bipartido nos conjuntos X e Y com capacidades associadas aos arcos. Considere que s é ligado a todo vértice de X, e todo vértice de Y é ligado a t, por arcos com capacidade infinita. A capacidade de um corte mínimo corresponde a soma total da capacidade dos arcos de D.
Podemos afirmar que são verdadeiras somente as afirmações:
A. I, II e III.
B. II, III e IV.
C. III e IV.
D. IV.
E. NDA.
Ideia original de: Lucas
Boa questão, fico com ela. Baseada em algo que eu erroneamente sugeri em classe a respeito de outro problema, mas você consertou, hem? Muito bem.
ResponderExcluir