ANO: 11º ANO - MACS DATA: OUT
TEMA: GRAFOS. MÉTODO DE CONTAGEM DE BORDA. DADOS BIDIMENSIONAIS.
TIPO: FICHA DE REVISÕES
LR MAT EXPLICAÇÕES
Grupo I
Seleciona a alínea de forma a construir afirmações verdadeiras.
1. Um dígrafo é ...
(A) ... um grafo em que todos os vértices estão ligados por uma aresta.
(B) ... um grafo em que as arestas têm pesos.
(C) ... um grafo em que as arestas têm direções definidas.
(D) ... um grafo em que todos os vértices têm grau.
2. Um grafo diz-se conexo se ...
(A) ... tiver um circuito euleriano.
(B) ... tiver um caminho euleriano.
(C) ... existir uma aresta a ligar qualquer par de vértices.
(D) ... todos os vértices têm grau ímpar.
3. Um percurso que percorre todas as arestas de um grafo uma única vez e começa e termina no mesmo
vértice é:
(A) um caminho euleriano.
(B) um circuito euleriano.
(C) um caminho de hamilton.
(D) um ciclo de hamilton.
Grupo II
4. Seis localidades no concelho de Évora estão ligadas umas às outras por estradas como podemos ver no
grafo seguinte.
4.1 Determina a árvore geradora mínima aplicando o algoritmo de Kruskal.
4.2 Elabora um circuito Euleriano se possível.
5. Constrói um grafo com cinco vértices e que não contenha um circuito euleriano.
Do grafo construído indica:
(a) o grau de cada vértice.
(b) se é conexo, justificando.
(c) se é possível encontrar um ciclo hamiltoniano e, caso seja, indica-o.
6. Um grupo de amigos (José, Diana, Pedro, Carla, António e Mónica) está a planear a Páscoa. Para
organizar tudo cada um tem de esconder, na casa de algum dos seus amigos, ovos da Páscoa.
Escolheu-se à sorte quem devia esconder ovos na casa de quem.
Quem vai à casa de um rapaz esconde lá 2 ovos, quem vai à casa de uma rapariga esconde lá 3 ovos.
A Carla tem de ir à casa da Mónica, do Pedro e do José.
A Diana à do António e do Pedro.
A Mónica à da Diana, à do José e da Carla.
O José à do Pedro e do António.
O António à da Diana.
6.1 Representa, com um grafo orientado e pesado, a organização da Páscoa dos amigos.
6.2 Indica quantos ovos receberá cada um dos amigos.
7. Considera o seguinte grafo.
7.1 Indica o grau de cada vértice.
7.2 Diz, justificando, se é conexo.
7.3 Diz, justificando, se é um grafo de Euler.
7.4 Determina um circuito que inicie em D.
7.5 Indica um circuito de Euler, caso exista.
7.6 Indica um ciclo de Hamilton.
8. Seis pequenas localidades, no concelho do Funchal, estão ligadas umas à outras por estradas, como se
mostra no grafo do exercício 7.
Os vértices representam as cidades, as arestas as estradas que as ligam e os números associados às
arestas as distâncias, em km, entre as localidades.
Encontra o caminho de distância mínima, utilizando:
8.1 o algoritmo de Kruskal, apresentando a árvore obtida.
8.2 o algoritmo do peso das arestas.
9. Considera os grafos seguintes.
9.1 Justifica que o primeiro é de Euler e o segundo não.
9.2 Euleriza o segundo grafo, com o número mínimo de arestas.
9.3 Indica um caminho de Euler no segundo grafo.
10. Quais dos seguintes grafos são árvores?
11. Determina a árvore geradora mínima para o grafo seguinte.
12. O Engenheiro Joaquim é representante de uma marca de tintas, tendo regularmente necessidade de
visitar cinco cidades cujas distâncias estão representadas no quadro seguinte.
12.1 Sabendo que parte do Porto, tem de visitar todas as cidades e regressar ao Porto, qual a menor
distância que poderá percorrer?
12.2 Resolve o problema utilizando o algoritmo da cidade mais próxima.
13. Considera o grafo da figura ao lado.
13.1 Aplica o algoritmo das arestas classificadas (peso das
arestas), para determinar um circuito que começa e acaba no
vértice C.
13.2 Determina a árvore geradora mínima aplicando o algoritmo
de Kruskal.
14. A junta de freguesia do Alendouro está a organizar uma excursão de autocarro a Santiago de Compostela
com partida em Coimbra. Antes de estabelecer o itinerário final, a comissão organizadora efetuou uma
consulta popular para saber em qual das cidades, no trajeto, os participantes preferem parar para uma
visita de algumas horas. Foram dadas três opções: Porto (P), Braga (B) ou Vigo.
Segundo o método da Contagem de Borda, o apuramento da cidade vencedora faz-se de acordo com
os seguintes critérios e etapas:
• para que um voto possa ser considerado válido, cada pessoa vota em todas as cidades,
ordenando-as de acordo com as suas preferências;
• na ordenação final das cidades, cada primeira preferência recebe tantos pontos quanto as
cidades em votação;
• cada segunda preferência recebe menos um ponto do que a primeira e, assim sucessivamente,
recebendo a última preferência um ponto;
• a escolhida é a cidade com maior número de pontos.
No quadro de preferências que se segue, estão registadas as sequências das preferências obtidas na
votação e o número correspondente de votos.
14.1 A percentagem de votos que indicaram Vigo como última preferência é aproximadamente:
(A) 34,7% (B) 13,9% (C) 33,3% (D) 37,4%
14.2 De acordo com o método indicado, determina a pontuação final de cada cidade e indica a
escolhida.
15. Para responder à pergunta:
Que países da Zona Euro têm maior e menor percentagem
de homens e mulheres entre os 18 e os 24 anos que
deixaram de estudar sem terminar o secundário?
o Matias consultou os registos referentes à taxa, em
percentagem, de abandono precoce de educação e
formação nos 19 países da Zona Euro.
Na tabela que se segue podemos encontrar os dados
recolhidos, em que 𝑥 e 𝑦 designam a percentagem de
homens e de mulheres, respetivamente, que
abandonaram precocemente os estudos sem terminar o
ensino secundário.
Por lapso, o Matias não registou a percentagem de
mulheres italianas que deixaram de estudar antes de
terminar o secundário.
Admite que as variáveis 𝑥 e 𝑦 estão associadas
linearmente.
Utiliza a calculadora gráfica para responder às questões
que se seguem:
15.1 Determina o coeficiente de correlação linear e a equação da reta de regressão. Apresenta os
valores dos parâmetros e do coeficiente com aproximação às décimas.
15.2 Faz uma estimativa para a percentagem de mulheres italianas que deixaram de estudar antes de
terminar o ensino secundário. Apresenta o resultado com uma casa decimal.
SOLUÇÕES
1. (C) ; 2. (C) ; 3. (B);
4. 4.1) Arestas: AB; BC; BF; FE; DE; 4.2) ABCDEFBFA;
6. 6.2) António: 4 ovos; Mónica: 3 ovos; José: 4 ovos; Diana: 6 ovos; Pedro: 6 ovos; Carla: 3 ovos.
7. 7.1) A-2; B-4 C-2; D-E; E-2; F-4; 7.2) Sim, pois qualquer vértice está ligado a outro vértice por uma
sequência de arestas; 7.3) Sim, pois todos os vértices têm grau pau; 7.4) DEABFD; 7.5) ABCDFBDEFA; 7.6)
ABCDEFA;
8. 8.1) Arestas: AB; BC; BF; DE; EF; 59 km; 8.2) ABCDEFA – 76 km.
9. 9.1) Todos os vértices têm grau par no primeiro grafo enquanto que no segundo grafo os vértice A e C
tem grau ímpar; 9.2) colocar outra aresta a ligar os vértices AC; 9.3 ABCEDCEFC
10. os grafos 1 e 3.
11. As arestas a ligar os seguintes vértices: 1 a 2; 1 a 4; 3 a 4; 4 a 7; 6 a 7; 7 a 5.
12. 12.1) PBVCAP com 461 km; 12.2) PBVACP com 509 km.
13. 13.1) CBAFEDC com peso igual a 28; 13.2) Arestas: AF; FE; ED; BC; EC com peso igual a 21.
14. 14.1) (A); 14.2) Porto.
15. 15.1) 𝑎 ≈ 0,7; 𝑏 ≈ −0,2; 𝑟 ≈ 0,9; 15.2) 11,1%
