Enunciado:
Dado um grafo G=(V,E) conexo e não orientado, para o qual sendo utilizado o algoritmo de Kruskal a fim de encontrar a árvore espalhada mínima do mesmo. Tal algoritmo armazena em A o conjunto de arestas que farão parte da árvore espalhada mínima. Considere B o conjunto das arestas de G que não pertencem a A durante a execução do algoritmo. Em um instante t da execução do algoritmo uma aresta (x,y) foi selecionada e será adicionada em A. Sobre a escolha desta aresta no instante t podemos afirmar que:

A) A aresta (x,y) possuirá necessariamente um dos vértices x ou y igual ao vértice de uma das arestas de A.

B) Entre as arestas de B que não formam um ciclo com as arestas de A, não há aresta com peso menor que (x,y).

C) O peso de (x, y) é necessariamente menor que qualquer aresta de B.

D) A aresta (x, y) não pode ter nenhum de seus vértices (nem x, nem y) igual ao vértice de uma das arestas de A.

E) NDA

Autor(a): André Santanchè
RA: 022287