arm

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Qual das seguintes declarações não é correta?

1. O Maximum-spanning-tree do G=(V,E) pôde ser encontrado usando o mesmo algoritmo para encontrar o minimum-spanning-tree, basta com definir w'(u,v)=-w(u,v) para toda (u,v) no conjunto E.
2. Para qualquer ciclo C no grafo G, seja (u,v) a aresta com maior peso no C, então (u,v) não pertence ao minimum-spanning-tree do G.
3. Na ordenação topológica nenhuma aresta u→v no grafo cumprem (v.f ≤ u.f).
4. Seja n o numero de componentes fortemente conectados do grafo G=(V,E), então (0 < n ≤ |V|) é verdadera.
5. NDA.

Ideia original de: Armando Faz Hernández.