Macs Ficha
Macs Ficha
1. Indique quais dos grafos que se seguem têm um trajeto e quais têm um circuito euleriano e
defina-os. Caso não tenham nenhum deles, explique porquê.
1.1 1.2
1.3 1.4
1. Um pintor de estradas tem de pintar, a traço interrompido, todas as ruas de uma certa
localidade. O grafo seguinte, onde os vértices representam as esquinas e as arestas
representam as ruas, serve de modelo para esta situação:
1.1 Será possível pintar todas as estradas sem repetir nenhuma rua e regressar ao ponto de
partida? Justifique.
1.2 Qual será, nesse caso, o percurso a seguir pelo pintor?
I II
III IV
Desenhe um grafo orientado que possa auxiliar o funcionário que vai recolher as moedas de
todos os parquímetros.
4. Numa aldeia, há cinco rapazes enamorados de cinco raparigas casadoiras. A tabela seguinte
indica as preferências de cada rapaz em relação às raparigas:
5.1 Represente por um grafo as preferências conjuntas dos rapazes e das raparigas.
5.2 Junte agora os casais tendo em conta as duplas preferências.
I II
2. Uma empresa de venda de material informático tem o seu armazém no ponto X e pretende
entregar materiais em H, passando primeiro por A para deixar algum material. A tabela que se
segue representa a rede viária da região que o representante da empresa tem de visitar, com
os respetivos tempos de percurso.
A B C D E F G H X
A – 10 15 25
B 10 – 17 12 21
C 15 – 40 21
D 25 17 40 – 5 20
E 12 – 8 19
F 21 8 – 14 23 18
G 5 14 – 16
H 21 23 16 – 19
X 20 19 18 19 –
20 km
Guimarães
0 : 15
55 km 50 km
Porto
0 : 35 0 : 30
125 km 120 km 75 km
Aveiro
1 : 15 1 : 10 0 : 50
170 km 160 km 120 km 60 km
Coimbra
1 : 35 1 : 30 1 : 05 0 : 40
230 km 225 km 180 km 115 km 65 km
Leiria
2 : 05 2 : 00 1 : 40 1 : 10 0 : 35
360 km 335 km 310 km 250 km 200 km 135 km
Lisboa
3 : 20 3 : 15 2 : 50 2 : 20 1 : 50 1 : 15
580 km 555 km 530 km 470 km 415 km 360 km 260 km
Faro/Loulé
5 : 20 5 : 15 4 : 50 4 : 20 3 : 50 3 : 20 2 : 30
in http://www.cm-braga.com.pt/euro2004
I II III
IV V VI
2.1 Descreva uma situação do quotidiano que possa ser modelada por este grafo.
2.2 Determine, usando o algoritmo de Kruskal, a árvore abrangente mínima e calcule o seu
peso total.
12. Alguns grupos de jovens de três nacionalidades (portuguesa, espanhola e inglesa) reuniram-se
para fazer um inter-rail. Sabe-se que metade dos jovens são portugueses, nenhum dos jovens
tem dupla nacionalidade e existem mais ingleses do que espanhóis. Escolhe-se, ao acaso, um
dos jovens. Qual pode ser o valor da probabilidade de o jovem escolhido ser espanhol?
(A) 20% (B)25% (C) 30% (D) 50%
13. A Ariel vai participar num sarau de ginástica. Para isso, vai precisar de um maillot, umas
sapatilhas e uma fita para o cabelo. A Ariel tem quatro maillots diferentes (dois brancos, um
preto e um azul), três pares de sapatilhas diferentes (dois brancos e um preto) e duas fitas
para o cabelo (uma branca e uma azul).
13.1 A Ariel escolhe, ao acaso, um maillot. Qual é a probabilidade de não escolher o maillot
azul?
1 3 2 1
(A) (B) (C) (D)
2 4 3 4
13.2 Para o sarau, a Ariel tem de levar um maillot, um par de sapatilhas e uma fita para o
cabelo. De quantas formas diferentes pode a Ariel apresentar-se no sarau?
(A) 24 (B) 12 (C) 16 (D) 28
Número de irmãos 0 1 2 3 4 5
Número de alunos 5 7 6 4 2 1
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. Em cálculos intermédios,
sempre que precisar de efetuar arredondamentos, conserve, no mínimo, quatro casas decimais.
1.1 Indique se cada uma das afirmações seguintes é verdadeira ou falsa, justificando a sua
opção:
1.1.1 O grafo é conexo.
1.1.2 O grafo é completo.
1.1.3 O grafo é simples.
1.1.4 O grafo é regular.
1.5 Indique, caso exista, um trajeto que percorra todas as arestas do grafo uma única vez.
Coloração de grafos
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. Em cálculos intermédios,
sempre que precisar de efetuar arredondamentos, conserve, no mínimo, quatro casas decimais.
Projetos
Funcionários A B C D E F G H I J
F1 X X
F2 X X
F3 X X X X
F4 X X X
F5 X X X X
F6 X X
F7 X X
F8 X X X
F9 X X X
F10 X X X
Para avaliar o ponto da situação relativamente à evolução de cada projeto, vão realizar-se
várias reuniões, cada uma apenas com os participantes respetivos de cada um dos projetos,
num total de dez reuniões. No entanto, nenhum funcionário deverá ter mais de uma reunião
por dia.
1.1 Modele por um grafo a situação descrita, no qual os vértices representem os projetos e
as arestas as incompatibilidades de reunir no mesmo dia.
Árvores
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. Em cálculos intermédios,
sempre que precisar de efetuar arredondamentos, conserve, no mínimo, quatro casas decimais.
1.1 Desenhe duas árvores abrangentes deste grafo e determine o peso total (soma dos
pesos de todas as arestas) de cada uma.
1.2 Utilize o algoritmo de Kruskal para determinar a árvore geradora mínima e calcule o seu
peso total.
1.3 Comprove o resultado anterior utilizando agora o algoritmo de Prim, descrevendo a sua
aplicação.
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.
As respostas aos itens que envolvam o uso da calculadora gráfica devem apresentar, consoante a situação:
ͻ Os gráficos obtidos, a janela de visualização e as coordenadas dos pontos relevantes para a resolução
(por exemplo, coordenadas de pontos de interseção de gráficos, máximos ou mínimos).
ͻ As linhas da tabela obtida relevantes para a resolução.
ͻ As listas introduzidas na calculadora para se obterem as estatísticas pedidas (por exemplo, média,
desvio-padrão, coeficiente de correlação, declive ou ordenada na origem de uma reta de regressão).
3. No grafo seguinte, as arestas representam a rede viária de uma certa cidade e os vértices
representam as freguesias:
Numa composição:
ͻ Justifique que não é possível, começando e acabando na freguesia C, visitar todas as outras
freguesias sem repetir nenhuma estrada de ligação.
ͻ Indique, justificando, qual o número mínimo de estradas a repetir para que seja possível
efetuar o percurso pretendido e apresente um grafo com a solução encontrada.
4. A tabela seguinte contém os preços, em euros, dos bilhetes de comboio entre algumas cidades
portuguesas:
Porto 24,30 €
Coimbra 19,20 € 13,20 €
Braga 25,80 € 11,70 € 17,20 €
Guarda 20,70 € 20,10 € 12,70 € 23,00 €
Resposta restrita 8
Itens de construção
Resposta extensa 7
Conteúdos
Tema 3 — Modelos matemáticos
ͻ Modelos de grafos
– Conceitos básicos
– Trajetos e circuitos eulerianos, circuitos hamiltonianos
– Problema do carteiro chinês — eulerização de grafos
– Problema do caixeiro-viajante
– Coloração de grafos
Cotações
Item 1.1 1.2 1.3 1.4 1.5 1.6 1.7 2 3 4.1 4.2.1 4.2.2 5.1 5.2 5.3
Cotação 5 5 5 10 10 15 10 15 25 15 20 20 15 20 10
Duração
O teste tem a duração de 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.
As respostas aos itens que envolvam o uso da calculadora gráfica devem apresentar, consoante a situação:
ͻ Os gráficos obtidos, a janela de visualização e as coordenadas dos pontos relevantes para a resolução
(por exemplo, coordenadas de pontos de interseção de gráficos, máximos ou mínimos).
ͻ As linhas da tabela obtida relevantes para a resolução.
ͻ As listas introduzidas na calculadora para se obterem as estatísticas pedidas (por exemplo, média,
desvio-padrão, coeficiente de correlação, declive ou ordenada na origem de uma reta de regressão).
1. Uma empresa pretende ligar as suas sucursais com ligações de telefone e internet seguras e
exclusivas. Assim, solicitou um orçamento a uma outra empresa, especializada em
telecomunicações. Em vez de um único valor total, a empresa de telecomunicações forneceu
os valores para cada ligação entre as diversas sucursais, cabendo ao cliente a decisão sobre
quais as ligações a efetuar. Na tabela seguinte, encontram-se os custos por cada ligação, em
dezenas de euros por ano:
A B C D
B 40
C 85 10
D 96 132 68
E 50 60 115 125
FICHA 1
1.1 Circuito: A B E C D A E D C B A
1.2 Trajeto: C B C H B A H G F H E F E C D E
1.3 Trajeto: A B C A G C D G F E G
1.4 Não tem trajeto nem circuito. Tem mais de dois
vértices com grau ímpar.
2.1 Não, porque existem dois vértices de grau ímpar.
2.2 B D A B C E H J I G D F H G F E D B E B (repete BD e BE)
2.3 A B D E B C E H J I G H F D E F G D A (repete DE)
FICHA 2
1.1 Sim, porque todos os vértices têm grau par.
1.2 Por exemplo, A B C I H B I F E D C H F G A
2.1 Apenas o IV tem.
4.2 Por exemplo: H1 com M3; H2 com M2; H3 com M5;
2.2
H4 com M1; H5 com M4.
I. II.
5.1
III.
FICHA 3
3. 1.1 I: Sim. A B C D A II: Sim. A B C D E A
1.2 I: A D C B A (47) II: A D E B C A (36)
1.3 I: A B C D A (47) II: E D A C B E (36)
2.1
o Aveiro
75
o Coimbra
60
o Leiria
65
o Lisboa
135
o Faro
260
o Braga
580
o Coimbra
60
o Leiria
65
o Lisboa
135
o Faro o
260 555
Guimarães
Distância: 1225 quilómetros
3.1.2
Porto o Guimarães o Braga o Aveiro
Aveiro o Guimarães
120
o Porto
50
50 20 125
o Guimarães o Aveiro o Faro
260
o Leiria
360
20 120
Distância: 1250 quilómetros
Distância: 1595 quilómetros
Lisboa o Leiria o Coimbra
o Aveiro
Aveiro o Leiria
115
o Coimbra
65
o Porto
120
135 65 60
o Guimarães
o Braga o Lisboa o Porto
75
o Guimarães
50
o Braga
20
50 20 360
Coimbra o Guimarães
160
o Lisboa
335
o Aveiro
60
o Porto
75
o Guimarães
50
o Braga
360
o Faro
580
o Aveiro
470
o Braga
20
o Faro
580
o Porto
75
o Leiria
180
o Coimbra
65
Distância: 1245 quilómetros
3.1.7
Distância: 2225 quilómetros
Braga o Guimarães o Porto o Aveiro
Coimbra o Aveiro
60
o Porto
75
20 50 75
o Coimbra o Leiria o Lisboa
o Guimarães
50
o Braga
20
o Faro
580
60 65 135
o
355
Guimarães
o Porto
50
o Aveiro
75
o Leiria
115
o Coimbra
65