MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 020

Uma estratégia para identificar grafos conexos é ir marcando os vértices, de acordo com certos critérios, de forma que, ao final, se todos os vértices estiverem marcados, o grafo é conexo; caso contrário, o grafo não é conexo.  Qual dos algoritmos abaixo efetua a marcação corretamente para identificar grafos conexos segundo esta estratégia?

a)
marcação(Grafo Simples){
____Para cada Vértice U
____Se existe pelo menos uma aresta U-V
________Marque U
}

b)
marcação(Grafo Simples){
____Para cada aresta ligando U a V
________Marque U
________Marque V
}

c)
marcação(Grafo Simples){
____Marque um vértice aleatório U
____Para cada aresta ligando U a V________Marque V
}

d)
marcação(Grafo Simples){
____Marque um vértice qualquer
____Enquanto existir aresta ligando um vértice marcado U a um vértice desmarcado V
________Marque V
}

e) NDA

Ideia Original de: Marlon Fernandes de Alcantara