MO417 - Questão para a prova oral
Número: 074
Enunciado:
Considere o grafo G=(V,E) mostrado na figura abaixo e seja a curva em vermelho o corte C. Qual das alternativas abaixo é INCORRETA?
- C respeita exatamente 8 arestas de G.
- Existe uma única aresta leve que cruza C.
- (h,g) é uma aresta presente em todas as árvores espalhadas
mínimas de G.
- Pelo menos duas arestas que cruzam C devem fazer parte de uma mesma árvore geradora mínima de G.
- NDA
Autor(a): Alexandre Toshio Hirata