Teste de Avaliação 1

Nome______________________________________ N.o______Turma _______Data ____ /out./2019

Avaliação ________________E. Educação _________________ Professor______________________

MATEMÁTICA APLICADA ÀS CIÊNCIAS SOCIAIS – 11.o ANO Duração: 90 minutos

Na resposta a cada item apresente todos os cálculos que tiver de efetuar e todas as justificações necessárias.
Quando para um resultado não for pedida aproximação, apresente sempre o valor exato.
Sempre que recorrer à calculadora, apresente todos os elementos recolhidos na sua utilização.

1. Considere o grafo seguinte:

1.1. Podemos dizer que este grafo é:

(A) não conexo. (B) completo. (C) regular. (D) simples.

1.2. Indique, justificando, se cada uma das sequências seguintes representa um trajeto
euleriano, um caminho hamiltoniano, ambos ou nenhum.

1.2.1. DAECB.

1.2.2. CEADCBA.

1.2.3. DCEABCD.

1.3. O grafo representado na figura é hamiltoniano? Justifique.

2. Considere a seguinte afirmação:

«Num grafo com nove vértices, todos com grau par, é sempre possível encontrar um circuito
euleriano.»
Esta afirmação é verdadeira ou falsa? Justifique a sua resposta e apresente um grafo que a
sustente.

Elisabete Longo 1
Isabel Branco
3. A Cândida esteve a estudar o serviço de transportes entre algumas cidades que terá de visitar por
questões de trabalho. Na tabela seguinte registou as distâncias, em quilómetros, entre cada
cidade, no caso de haver transporte entre elas:

Alva Branca Clara Desvanecida Esbatida

Alva 52 36 145 80
Branca 36 Não existe 93
Clara Não existe Não existe
Desvanecida 29
Esbatida

3.1. Desenhe um grafo ponderado que modele a situação descrita na tabela, indicando o
significado dos vértices e das arestas. Para simplificar, pode utilizar apenas a primeira letra
de cada cidade.

3.2. O grafo obtido na alínea anterior é completo? Justifique.

3.3. Para aproveitar o tempo das viagens para conhecer a região, a Cândida gostava de começar
em Branca, onde mora, fazer todos os percursos existentes sem repetir nenhum e regressar
a casa. Justifique que a pretensão da Cândida não é possível, indique o número mínimo de
estradas a repetir para que consiga efetuar o percurso pretendido, e apresente um grafo
com a solução encontrada.

3.4. A Cândida quer encontrar um percurso que passe por todas as cidades e decide utilizar o
algoritmo seguinte:
• Passo 1: define-se uma das localidades como ponto de partida.
• Passo 2: seleciona-se a localidade mais próxima, tendo em conta que se houver duas
localidades à mesma distância a seleção é aleatória.
• Passo 3 e seguintes: procede-se como foi indicado no passo anterior, não se repetindo
nenhuma localidade, e termina-se depois de visitadas todas as localidades.

3.4.1. Em qual das situações se pode obter um percurso menor: começando em Alva ou em
Esbatida?
Na sua resposta deve:
- aplicar o algoritmo considerando os dois pontos de partida distintos;
- indicar o número mínimo de quilómetros para cada uma das duas situações e os
respetivos percursos;
- indicar a melhor solução.

2 Elisabete Longo
Isabel Branco
 3.4.2. Mostre, aplicando o algoritmo, que iniciando o percurso na localidade C, a opção
aleatória de uma localidade à mesma distância pode levar a percursos com diferentes
comprimentos. Na sua resposta deve contemplar os aspetos também pedidos na
alínea anterior.

4. Um clube recreativo vai organizar um campeonato de jogos de tabuleiro. Os jogos escolhidos são:
abalone (A), damas (D), gamão (G), hex (H), mastermind (M), ouri (O) e xadrez (X). Como há
participantes inscritos em mais do que um jogo e cada pessoa só pode jogar um jogo por dia, foi
feito um registo para que se pudessem estudar melhor as incompatibilidades. A tabela seguinte
traduz esse registo:

Participante Jogos
1 A, O
2 D, X
3 A, X
4 A, G, O
5 G, H
6 D, M
7 G, X
8 H, O
9 D, H, M
10 D, G

4.1. Construa um grafo que traduza os dados da tabela e contextualize o significado dos vértices
e arestas.

4.2. Utilize o processo de coloração de vértices de grafos para determinar o número mínimo de
dias necessários para realizar o campeonato de jogos.

4.3. Indique uma organização possível dos jogos em cada dia.

Elisabete Longo 3
Isabel Branco
5. Uma empresa proporciona aos seus funcionários um serviço de transporte casa-empresa de
manhã e o regresso ao fim do dia. O shuttle recolhe os colaboradores da empresa em locais
predefinidos os quais se encontram representados pelos vértices do grafo ponderado seguinte:

Os valores numéricos representam as distâncias, em quilómetros, entre cada ponto de recolha.

Utilize o algoritmo de Kruskal para determinar o percurso mínimo na recolha matinal dos
funcionários. Apresente uma árvore abrangente mínima para esse percurso, bem como o seu
comprimento.

Cotações:
1.1. 1.2.1. 1.2.2. 1.2.3 1.3 2. 3.1 3.2. 3.3. 3.4.1. 3.4.2. 4.1. 4.2. 4.3. 5.
5 10 10 10 10 15 15 5 20 20 15 15 20 10 20

Total: 200 pontos

FIM

4 Elisabete Longo
Isabel Branco