Esse é um problema típico de cobertura de conjunto. Para cada cidade x, seja Sx o conjunto de cidades distantes 30km dele. Uma escola em x irá esse...

Esse é um problema típico de cobertura de conjunto. Para cada cidade x, seja Sx o conjunto de cidades distantes 30km dele. Uma escola em x irá essencialmente “cobrir” essas outras cidades. Um modelo computacional comum para esse cenário é o uso de grafos: cada conjunto Sx vai ser representado por vértices e as distâncias de 30km que unem cada par de cidades por arestas. Considere esse cenário e o seguinte algoritmo guloso para ele: Algoritmo guloso Entrada: Um conjunto de elementos B e uma coleção S1, …, Sm. Saída: A seleção dos Si cuja união é B. 1. Repetir até que todos os elementos de B estejam cobertos. 2. Pegue o conjunto Si com maior número de elementos não cobertos. 3. Adicione Si à seleção que será retornada. Analise as afirmativas a seguir: I – O algoritmo guloso encontra a solução ótima para o problema. II – O primeiro Si selecionado pelo algoritmo corresponde ao vértice 'a'. III – Na segunda iteração, o algoritmo deve escolher entre quatro elementos possíveis. IV – O vértice de maior grau compõe a solução ótima para o problema. Quais estão corretas?

I – O algoritmo guloso encontra a solução ótima para o problema.
II – O primeiro Si selecionado pelo algoritmo corresponde ao vértice 'a'.
III – Na segunda iteração, o algoritmo deve escolher entre quatro elementos possíveis.
IV – O vértice de maior grau compõe a solução ótima para o problema.
II e III.
I e II.
II e IV.
I, II e III.