MO417 - Questão para a prova oral

Número: 2003-147

Enunciado: Dado um grafo G=(V,E) conexo e não orientado, considere o algoritmo de Kruskal para encontrar uma árvore espalhada mínima de G. Tal algoritmo armazena em A um conjunto de arestas que farão parte da árvore espalhada mínima. Seja B o conjunto das arestas de G que não pertencem a A num certo momento durante a execução do algoritmo, quando uma aresta (x,y) foi selecionada e será adicionada em A. Sobre a escolha desta aresta, 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

Ideia original de: André Santanchè