-
|
|
C |
T |
G |
A |
T |
A |
G |
A |
T |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
| T |
0 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
2 |
| G |
0 |
0 |
1 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
| C |
0 |
1 |
1 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
| G |
0 |
1 |
1 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
| T |
0 |
1 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
4 |
| A |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
| T |
0 |
1 |
2 |
2 |
3 |
4 |
4 |
4 |
4 |
5 |
-
Dependendo da ordem em que os vértices aparecem nas listas de adjacência, uma possível solução seria a seguinte, dada pela fila em que os vértices são colocados para processamento, e pelo grafo resultante, com arestas pai mais grossas e rótulos nos vértices da forma "x:d" onde d é a distância.
Fila: 1, 6, 2, 4, 9, 14, 3, 10, 5, 12, 15, 18, 17, 8, 11, 13, 19, 16, 20, 21, 7
Outras soluções são possíveis, mas elas vão diferir apenas nas arestas pai e não nas distâncias.
-
No desenho a seguir temos a forma geral de uma árvore espalhada mínima deste grafo. As arestas grossas, azuis, são obrigatórias. Ds arestas de peso 2, em vermelho, temos que escolher duas quaisquer de um total de 3 (há 3 possibilidades). Das arestas verdes, temos que escolher 3 de 5, sem formar ciclo (8 possibilidades). Das arestas amarelas, temos que escolher 4 de 7, sem formar ciclos (21 possibilidades). Multiplicando as possibilidades, temos 3x8x21 = 504 possíveis árvores espalhadas mínimas.
O peso de cada MST é 17.
-
Nesta questão pode-se usar o algoritmo de Dijkstra. Há várias soluções, dependendo da ordem em que vértices com estimativas iguais são retirados do heap. Uma possível ordem de retirada seria a seguinte: 1, 2, 3, 4, 7, 6, 12, 9, 5, 11, 13, 8, 15, 18, 20, 17, 19, 10, 14, 16.
O grafo a seguir ilustra esta solução, com arestas pai mais grossas e rótulos nos vértices da forma "x:w" onde w é o peso de um caminho mínimo.
Outras soluções são possíveis, mas elas vão diferir apenas nas arestas pai e não nos pesos dos caminhos mínimos.
Quem acertou todos os valores da matiz ganhou 2,5. Conforme o número de erros,
os alunos foram perdendo pontos, seguindo o esquema abaixo:
1 a 5 erros: -0,5.
6 a 20 erros: -1,0.
21 a 50 erros: -1,5.
51 a 95 erros: -2,0.
96 a 100 erros: -2,5.
Nesta questão tiveram que ser dadas as arestas de pai e as distâncias. Quem acertou todas as arestas de
pai e todas as distâncias ganhou 2,5. Quem errou distâncias ou arestas, foi perdendo pontos à razão de 0,5
ponto a cada 3 elementos (arestas ou distâncias) errados.
Além disso, as seguintes penalidades foram aplicadas:
não começou no vértice 1: -1,5.
não começou no vértice 2 na segunda busca: -1,0.
inicializou as distâncias com 1 em vez de zero: -1,0.
não reinicializou as distâncias com 0 para as demais buscas: -1,0.
- Nesta questão o valor do peso da árvore espalhada mínima contribuiu com 0,1 para a nota
da questão. Os restantes 2,4 dependeram do número de árvores descritas, com justificativa.
Neste quesito de número de árvores, os alunos às vezes apontaram algumas árvores corretas, mas também
apontaram conjuntos de arestas que não eram árvores espalhadas mínimas. Chamaremos estes conjuntos de
"árvores erradas". Pois bem, no critério de correção, cada 5 árvores erradas anularam uma certa.
O percentual de árvores corretas líquidas (retirando as anuladas pelas erradas) em relação ao
valor correto de árvores espalhadas mínimas, que é 504, foi aplicado a 2,4 para compor esta parte da nota.
Resumindo, se o aluno descreveu (com justificativa) C árvores corretas e E árvores erradas, sua nota
foi 2,4*(C - E/5)/504, mais 0,1 se acertou o valor do peso (que era 17).
Houve ainda um critério nesta questão. Quem deu sinais de não saber o que era uma árvore
espalhada mínima ganhou zero na questão.
Nesta questão tiveram que ser dados os caminhos mínimos a partir do vértice 1.
A melhor forma de fazer isto é indicar uma árvore, com raiz em 1, orientada sempre
para longe de 1, e que alcance todos os vértices. Opcionalmente, embora a questão não pedisse,
poder-se-ia indicar as distâncias de 1 a cada vértice. Isto ajuda bastante e quase todos os
alunos fizeram. Quem fez uma árvore destas correta ganhou 2,5.
Alguns alunos não indicaram os caminhos, mas colocaram as distâncias, e eu considerei
que a partir delas é possível deduzir os caminhos, por isto aceitei como válida tal resposta,
desde que as distâncias estivessem todas corretas. Quem errou arestas ou distâncias,
foi perdendo pontos à razão de 0,5
ponto a cada 2 elementos (arestas ou distâncias) errados.
Além disso, as seguintes penalidades foram aplicadas:
citou Kruskal: -1,0.