MACS

MACS - Preparação para exame Ficha de trabalho – 1

1. 30 alunos de uma turma votaram, por ordem de preferência, nos três candidatos ao cargo de delegado da mesma. 10 ordenaram-nos do seguinte modo: Artur, Etelvino e Ivone. Outros dez preferiram Ivone, Artur e Etelvino e os restantes optaram por Etelvino, Ivone e Artur. O vencedor da eleição foi:
(A) Artur, porque ganhou em despique directo ao Etelvino.
(B) Etelvino, porque ganhou em despique directo à Ivone.
(C) Ivone, porque ganhou em despique directo ao Artur.
(D) Nenhum deles, porque se registou uma situação de empate

2. Numa comunidade existem cinco homens, que desejam casar com cinco outras meninas. Alguns homens têm preferência por algumas das meninas. Abaixo segue uma tabela, que apresenta o gosto pessoal de cada um. Como unir os pares de tal forma que todos se casem?
Homens Mulheres
1 1, 2, 5
2 2, 3, 5
3 1, 4
4 1, 4
5 1, 3
3. . 3.1 3.2

3.3

a)Os grafos são completos? Justifique
b)Os grafos são conexos? Justifique.
c) Indique o grau de cada vértice d) Como se pode verificar os grafos anteriores não são grafos de Euler. Eulerize cada um deles e) Determine a árvore geradora mínima aplicando o algoritmo de Kruskal

4.
4.1 O engenheiro José Alexandre é representante de uma marca de chapas de aço, tendo regularmente necessidade de visitar cinco cidades cujas distâncias estão representadas no quadro seguinte:

Sabendo que parte de Aveiro, tem de visitar todas as cidades e regressar a Aveiro, qual a menor distância que poderá percorrer?
Resolva o problema usando:
a) o método do vizinho mais próximo b) o método do peso das arestas.
4.2 Suponha agora que se vai realizar uma