MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 059

Enunciado: Considere as seguintes afirmações:

I - Caminhos disjuntos nas arestas também são disjuntos nos vértices.
II - Todo caminho maximal em uma árvore é uma orelha da árvore.
III - O grafo linha de C_n é C_n, e o grafo linha de K_n é K_n(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 à soma total da capacidade dos arcos de D.

Podemos garantir 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