Grafos

M.A.C.S. (11.
o ano)
Teoria de grafos
Exercı́cios de Provas Nacionais
1. Em cada uma das opções, A, B, C e D, apresenta-se um esquema, sob a forma de grafo, que representa
um jardim. Em cada grafo, os vértices representam canteiros, e as arestas representam os caminhos
existentes entre eles.
No jardim onde o Rui trabalha, foi construı́do um novo caminho entre dois canteiros que ainda não
estavam ligados. Graças a este novo caminho, é agora possı́vel iniciar e terminar um percurso num
mesmo canteiro, percorrendo todos os caminhos, incluindo o novo, sem repetir nenhum deles.
Qual das opções representa o jardim onde trabalha o Rui, antes da construção do novo caminho?
(A) (B)
B B
A A
C C
F F
D D
E E
(C) (D)
B B
A A
C C
F F
D D
E E
Exame – 2020, Ép. especial

2/32
2. No parque municipal de Avelares, vão ser instalados oito bebedouros em locais previamente selecionados,
designados por A, B, C, D, E, F, G e H, que serão interligados através de uma canalização.
Na tabela seguinte, apresenta-se o comprimento, em metros, das ligações que é possı́vel estabelecer entre
os diversos locais.
B C D E F G H
A 500 620 — 840 — 502 —
B 505 — 446 — 800 —
C 1140 850 — 754 —
D — 976 721 952
E 700 — —
F 412 1310
G 1360
De modo a minimizar o custo da canalização, construiu-se um grafo, aplicando o método que a seguir se
descreve.
• Seleciona-se a ligação de menor comprimento (se houver mais do que uma, escolhe-se ao acaso uma
delas).
• Em seguida, seleciona-se, de entre as ligações restantes, a de menor comprimento, desde que esta
não leve à formação de um ciclo.
• Termina-se quando todos os locais onde serão instalados bebedouros estiverem ligados.
Determine o comprimento total da canalização.
Na sua resposta, apresente o grafo que resulta da aplicação do método descrito.

mat.absolutamente.net
3/32
3. A Elsa, que em 2018 fez um Interrail, relatou à Maria a sua viagem, explicando-lhe também algumas
dificuldades na sua organização.
Uma das dificuldades foi decidir que paı́ses visitariam e, em cada paı́s, a quantas cidades iriam.
O grupo de amigos da Elsa acabou por decidir que visitariam a Alemanha, a Áustria, a França, a Itália
e a Suı́ça e que, em cada paı́s, iriam apenas a uma cidade.
Na tabela seguinte, apresentam-se as distâncias, em quilómetros, entre as cidades que o grupo considerou
mais atrativas e os paı́ses a que pertencem.
Cidades Viena Salzburgo Paris Milão Veneza Zurique

Alemanha Munique 430 140 800 500 520 340
Viena 290 1230 860 600 740
Áustria
Salzburgo 980 530 460 450
Paı́ses
França Paris 850 1100 650

Milão 270 280
Itália
Veneza 540
Suı́ça Zurique
Os amigos acordaram que o percurso a realizar seria definido partindo de um grafo no qual duas cidades
são interligadas se não pertencerem ao mesmo paı́s, selecionando-se apenas uma cidade de cada paı́s e
atendendo ao seguinte algoritmo:
• escolher a aresta do grafo com menor peso, qualquer que ela seja;
• escolher, sucessivamente, as arestas de menor peso, garantindo que três arestas do percurso que está
a ser definido não se encontram num mesmo vértice e não permitindo que se fechem percursos sem
que todos os vértices sejam incluı́dos.
Apresente um percurso possı́vel, definido pelo grupo de amigos da Elsa, com inı́cio e fim na cidade de
Paris.
Na sua resposta, apresente:

– a ordenação das arestas selecionadas pelo algoritmo descrito;
– um grafo que resulte da aplicação do algoritmo;
– um percurso que o grupo de amigos da Elsa poderá ter definido.
Exame – 2020, 2.a Fase
4/32
4. Num determinado verão, decorreram os festivais F1, F2, F3, F4, F5 e F6. Estes festivais realizaram-se
ao fim de semana e tiveram, cada um, a duração de dois dias (sábado e domingo).
Na tabela seguinte, apresentam-se os festivais a que quatro jovens assistiram. Cada jovem assistiu,
sempre, a ambos os dias de cada um dos festivais.
Jovens Festivais
Elsa F1, F2, F3
Filipe F1, F2, F4
Gaspar F1, F3, F5
Manuel F4, F5, F6
Indique o número mı́nimo de fins de semana em que os festivais podem ter decorrido.
Na sua resposta:
– apresente um grafo que modele a situação descrita;
– identifique os festivais que decorreram em simultâneo.
5/32
5. Numa das alas do Centro Comercial Futuro existem 8 pontos de vigilância, designados A, B, C, D, E, F,
G e H, nos quais estão instaladas câmaras de vigilância.
Pretende-se encontrar a solução mais económica para a substituição das ligações internas entre as câmaras.
A tabela seguinte apresenta o comprimento, em metros, das ligações existentes entre os pontos de vi-
gilância.
B C D E F G H
A 23 20
B 25 19 14
C 15 45
D 22 18
E 16 30
G 50
De modo a minimizar os custos da intervenção, construiu-se um grafo, adotando-se o procedimento

seguinte:
• seleciona-se a ligação de menor comprimento (se houver mais do que uma, escolhe-se ao acaso uma
delas);
• em seguida, seleciona-se, de entre as ligações restantes, a de menor comprimento, desde que esta não
leve à formação de um ciclo;
• termina-se quando todos os pontos de vigilância pertencerem a alguma das ligações selecionadas no
grafo.
Admita que a substituição de cada metro de ligação interna tem o custo de 12 euros.
Determine o custo total da substituição.
Na sua resposta, apresente o grafo que resulta da aplicação do método descrito.

6/32
6. O Clube de Colecionadores possui um espaço próprio para exposições.
Na figura seguinte, apresenta-se uma planta simplificada do referido espaço, que é composto por um Átrio
e seis salas: S1, S2, S3, S4, S5 e S6.
O presidente do Clube pretendia inicialmente definir um percurso, com inı́cio e fim no Átrio, cruzando
todas as portas e entrando em todas as salas, sem cruzar nenhuma porta mais de uma vez.
Tendo verificado que o seu objetivo não podia ser posto em prática, e como o espaço será alvo de
remodelação, o presidente decidiu que uma das intervenções a levar a cabo seria eliminar uma das portas
existentes ou acrescentar uma nova porta para viabilizar o seu objetivo.
Indique, justificando, qual terá sido a intervenção decidida pelo presidente (se eliminou uma porta ou
acrescentou uma porta, e entre que salas).
Na sua resposta, apresente um grafo que modele a situação descrita.

7. Uma empresa foi convidada a participar num certame. Para expor os seus produtos, terá de montar uma
banca, sendo necessário levar a cabo diversas tarefas. O diretor de operações da empresa fez a lista dessas
tarefas, desde que se inicia a montagem da banca até tudo estar concluı́do.
A tabela seguinte apresenta o tempo necessário para executar cada tarefa (Duração), em minutos, e,
quando é o caso, quais as tarefas que devem ser previamente concluı́das (Tarefas precedentes).
Tarefa Duração (minutos) Tarefas precedentes

T1 3 —
T2 10 T1
T3 15 T1
T4 12 T2 T3
T5 15 T2 T3
T6 5 T4 T5
Determine o tempo mı́nimo necessário, em minutos, para executar todas as tarefas que compõem a mon-
tagem da banca.
7/32
8. Admita que, no distrito de Castelo Branco, se pretende adotar uma nova tecnologia na iluminação de
estradas. Na tabela seguinte, apresenta-se a extensão, em quilómetros, das estradas onde se poderá
adotar esta tecnologia.
Benquerença Louriçal do
Oleiros(O) Torrozelo (T)
(B) Campo (L)
Alcafozes(A) 60 51 124 167
Benquerença (B) — 39 68 173
Louriçal do Campo (L) — — 100 144
Oleiros (O) — — — 112
Não sendo viável, por razões económicas, adotar esta tecnologia em todas as estradas, decidiu-se, numa
fase inicial, proceder à sua adoção somente em algumas delas.
Para a seleção das estradas recorreu-se ao algoritmo seguinte.
• Constrói-se um grafo, cujos vértices representam as localidades, selecionando-se, sucessivamente, as

menores extensões de estradas entre elas, tendo-se em conta que:
– se a aresta a que corresponde a extensão selecionada levar à formação de um circuito, essa aresta
não deve ser considerada;
– caso contrário, essa aresta deve ser considerada.
• O algoritmo termina quando, no grafo, o número de arestas é igual ao número de vértices menos um.
Determine, nestas condições, o número de quilómetros de estrada que o projeto de iluminação deve con-
templar na sua fase inicial. Na sua resposta, apresente o grafo que resulta da aplicação do algoritmo,
indicando o peso de cada aresta.
8/32
9. Na preparação da sua digressão pelas ilhas do arquipélago dos Açores, a companhia de teatro optou por
apresentar a peça somente nas ilhas com, pelo menos, 6000 habitantes.
Na tabela seguinte, está registado o número de habitantes em cada uma das ilhas.
Ilha N.o de habitantes

Santa Maria 5547
São Miguel 137 699
Terceira 56 062
Graciosa 4393
São Jorge 8998
Pico 14 144
Faial 15 038
Flores 3791
Corvo 430
Fonte: Censos 2011
De modo a minimizar o custo das deslocações aéreas, foram analisados os preços das ligações aéreas dire-
tas, existentes entre as diferentes ilhas, a que a companhia de teatro poderá recorrer.
Na figura seguinte, estão indicadas essas ligações aéreas diretas entre as ilhas do arquipélago dos Açores
e o respetivo custo, por pessoa.
A companhia de teatro optou por começar a digressão na ilha do Faial, pretendendo terminá-la noutra ilha.
De modo a minimizar o custo das viagens, aplicou o método que a seguir se descreve.
• Seleciona-se a ilha seguinte, tendo em conta que:
– deverá corresponder à viagem de preço mais baixo;
– se houver duas ilhas para as quais seja possı́vel viajar pelo mesmo preço, a seleção é aleatória.
• Procede-se como foi indicado no ponto anterior, não se repetindo nenhuma ilha e terminando depois
de serem visitadas todas as ilhas incluı́das na digressão.
9/32
Determine o custo mı́nimo em deslocações aéreas de cada elemento da companhia de teatro na sua di-
gressão pelo arquipélago dos Açores, respeitando as condições definidas.

– um grafo ponderado que resulte da aplicação do método descrito;
– a ordem pela qual a companhia de teatro visitará as ilhas.
10. Mariana decidiu viajar até Praga e, a partir daı́, visitar outras capitais europeias, regressando a essa
primeira cidade no final da visita.
As capitais que pretende visitar, além de Praga, são Berlim, Bratislava, Varsóvia e Viena.
Para planear as suas férias, Mariana utilizou a tabela seguinte, que apresenta as distâncias, em quilómetros,
entre as referidas capitais.
Bratislava Praga Varsóvia Viena

Berlim 677 349 572 640
Bratislava —– 328 673 80
Praga —– —– 681 305
Varsóvia —– —– —– 689
Com base na informação apresentada e num mapa da Europa semelhante ao que se apresenta na figura
seguinte, Mariana construiu um grafo em que duas capitais são interligadas, desde que os paı́ses a que
pertencem façam fronteira entre si.
O seu percurso será definido a partir do grafo construı́do e atendendo ao seguinte algoritmo:
• escolher a aresta do grafo com menor peso, qualquer que ela seja;
• escolher, sucessivamente, as arestas de menor peso, garantindo que três arestas do percurso que está
que todos os vértices sejam incluı́dos.
Apresente um percurso possı́vel, definido por Mariana, com inı́cio e fim em Praga.

– um grafo semelhante ao que Mariana construiu;
– a ordenação das arestas selecionadas pelo algoritmo descrito;
– um percurso que Mariana poderá ter definido.
10/32
11. Na figura seguinte, está representada a planta do recinto de um dos cinemas onde decorre o CineJov.
O recinto é composto por cinco salas, numeradas de 1 a 5, e por uma Zona Exterior, num total de
seis espaços. Todas as salas têm um único acesso à Zona Exterior e todas têm comunicação com, pelo
menos, uma outra sala, como se observa na figura seguinte.
No final do dia, um funcionário faz uma inspeção completa ao recinto, respeitando as seguintes condições:
– passa por todas as portas;
– começa e termina na Sala 1.
Para realizar esta inspeção, o funcionário pode sair das diferentes áreas do recinto e nelas voltar a entrar
as vezes que considerar necessárias. Com base na sua experiência, afirma que é impossı́vel fazer a inspeção
completa ao recinto, passando uma única vez por cada uma das portas.
Justifique que o funcionário tem razão e identifique a porta pela qual terá necessariamente de passar
duas vezes.
11/32
12. A associação de estudantes está a preparar um pedipaper que engloba seis postos de controlo, designados
por C1 , C2 , C3 , C4 , C5 e C6 .
Na tabela seguinte, estão indicadas as distâncias, em metros, entre diferentes postos de controlo.
C2 C3 C4 C5 C6
C1 160 – – 302 180
C2 – 253 – 350 270
C3 – – 286 340 267
C4 – – – – 294
A associação de estudantes decidiu que o pedipaper se iniciaria no posto de controlo C5 e terminaria num
outro posto de controlo.
Além disso, para definir o percurso, a associação de estudantes optou por utilizar o método seguinte.
• Seleciona-se o posto de controlo seguinte, tendo em conta que:
– deve ser o mais próximo possı́vel;
– se houver dois postos à mesma distância, a seleção é aleatória.
• Procede-se como foi indicado no ponto anterior, não se repetindo nenhum posto de controlo, e ter-
minando depois de serem visitados todos os postos de controlo.
Determine o comprimento do percurso, respeitando as condições definidas pela associação de estudantes.

– um grafo ponderado que modele a situação descrita na tabela anterior;
– a ordem de visita dos postos de controlo.
12/32
13. As seis diversões mais procuradas da zona Studiospeed estão representadas na figura seguinte pelas letras
D1, D2, D3, D4, D5 e D6.
As linhas representam as ligações existentes entre essas diversões. O comprimento de cada ligação está
indicado junto da linha que a representa.
D3
480 m
D4
302 m 286 m
490 m
D5
580 m
492 m
D2
520 m
308 m
360 m
D6
D1 472 m
Uma empresa de eletricidade pretende renovar a rede de cabos elétricos, aproveitando algumas destas
ligações. De modo a minimizar a quantidade de cabo utilizado, aplica-se o método que a seguir se
descreve.
• Escolhe-se, ao acaso, uma das seis diversões e, de entre as ligações a essa diversão, seleciona-se a
ligação de menor comprimento.
• Seleciona-se a ligação de menor comprimento de entre as ligações a qualquer uma das duas diversões
escolhidas para uma diversão ainda não selecionada.
• Seleciona-se a ligação de menor comprimento de entre as ligações a qualquer uma das diversões
escolhidas para uma diversão ainda não selecionada.
• Repete-se o ponto anterior até todas as diversões terem sido selecionadas.
Determine a quantidade mı́nima, em metros, de cabo elétrico que é necessário instalar para que as seis
diversões recebam energia elétrica.

– um grafo que resulte da aplicação do método descrito e que permita identificar as ligações utilizadas;
– a quantidade mı́nima, em metros, de cabo elétrico que é necessário instalar.
13/32
14. As instalações do TPT estão distribuı́das por cinco edifı́cios: E1, E2, E3, E4 e E5.
As distâncias mı́nimas, em metros, entre cada dois edifı́cios estão registadas na tabela seguinte.
E2 E3 E4 E5
E1 166 206 125 287
E2 — 151 264 169
E3 — — 207 109
E4 — — — 309
No final de cada dia, um estafeta recolhe o correio em cada um dos edifı́cios. De modo a tornar mais
eficiente o seu trabalho, começou por ordenar, de forma crescente, as distâncias registadas na tabela
anterior. De seguida, recorrendo a um grafo, construiu um percurso fechado que ligava os cinco edifı́cios.
Para tal, adotou o seguinte método.
• Representou a primeira aresta do grafo correspondente à menor das distâncias entre os edifı́cios.
• Representou as restantes arestas, selecionando sucessivamente as menores distâncias, garantindo que
três delas não se encontrassem num mesmo vértice e que não se fechassem percursos sem que todos
os vértices estivessem incluı́dos.
Apresente um possı́vel percurso final definido pelo estafeta, com inı́cio e fim no edifı́cio principal (E3).
– a ordenação, de forma crescente, das distâncias registadas na tabela anterior;

– um grafo semelhante ao que terá sido construı́do pelo estafeta.
14/32
15. No Encontro Desportivo Internacional, existem atletas que estão inscritos em mais do que uma modali-
dade. Para que todos consigam realizar um treino de adaptação ao estádio onde se irão realizar as provas,
vai ser criado um horário com blocos de utilização das instalações. De cada bloco deverão fazer parte as
modalidades nas quais não haja atletas inscritos simultaneamente.
A constituição de cada bloco será definida considerando os dados da tabela seguinte, na qual o sı́mbolo 7
indica as modalidades que podem ser inseridas num mesmo bloco.
Modalidades A B C D E F G H
A 7 7 7
B 7
C 7 7
D 7 7
E
F 7 7
G 7
H 7
Determine, tendo em conta as condições dadas, o número mı́nimo de blocos que será necessário constituir,
de modo que todos os atletas possam realizar o treino de adaptação em todas as modalidades em que
estão inscritos. Na sua resposta
– apresente um grafo que modele a situação;
– identifique as modalidades que constituem cada um dos blocos.
15/32
16. Na figura seguinte, apresenta-se um mapa do recinto do MaréFest no qual estão representadas as infraes-
truturas I1 , I2 , I3 , I4 , I5 , I6 e I7 , ligadas entre si através de troços pedonais.
Considera-se troço pedonal a ligação entre duas infraestruturas adjacentes, isto é, o percurso que pode ser
usado para ir de uma dessas infraestruturas à outra sem passar por mais nenhuma.
Um vigilante do recinto pretende vistoriar as condições de segurança de todos os troços pedonais, ini-
ciando e terminando a sua vistoria junto da mesma infraestrutura. Observando o mapa, conclui que não
será possı́vel, nestas condições, percorrer todos os troços pedonais sem repetir nenhum.
Apresente uma sugestão de um único troço pedonal a repetir pelo vigilante, que lhe permita percor-
rer todos os troços, iniciando e terminando a vistoria junto da mesma infraestrutura, sendo o número de
troços a percorrer o menor possı́vel.

– um grafo que modele o mapa do recinto com as infraestruturas, de I1 a I7 , e com os troços pedonais.
– uma justificação da veracidade da conclusão do vigilante.
16/32
17. A companhia de aviação ASA5 opera nos aeroportos nacionais.
O diretor de operações de terra da companhia de aviação ASA5 fez uma lista das tarefas efetuadas
entre a aterragem de um certo avião e uma nova descolagem.
A tabela seguinte apresenta o tempo necessário para concretizar cada tarefa (Duração) e, quando existem,
as tarefas que devem ser previamente concluı́das (Tarefa(s) precedente(s)).
Duração
Tarefa Tarefa(s) precedente(s)
(em minutos)
Carregamento de bagagem (CB) 16 Descarga de bagagem (DB)
Descarga de bagagem (DB) 2 —
Desembarque de passageiros (DP) 14 —
Desembarque de passageiros (DP)
Embarque de passageiros (EP) 20
e Descarga de bagagem (DB)
Limpeza da cabine (LC) 12 Desembarque de passageiros (DP)
Reabastecimento alimentar (RA) 4 Limpeza da cabine (LC)
Há tarefas que se podem realizar em simultâneo, por exemplo, enquanto decorre o Desembarque de pas-
sageiros (DP), pode estar a realizar-se a Descarga de bagagem (DB).
Determine o tempo mı́nimo, em minutos, necessário para realizar todas as tarefas que antecedem uma
nova descolagem (D) desse avião da ASA5, nas condições previstas na tabela anterior.

– um grafo que represente a situação, incluindo o significado dos elementos (arestas e vértices) que o
constituem;
– as possı́veis sequências de concretização das tarefas e a respetiva duração.
17/32
18. O Sr. Pereira é motorista da empresa PTM.
Num certo dia, o Sr. Pereira tem de passar nas cidades A, B, D e E, não necessariamente por esta
ordem, partindo da sede da empresa, localizada na cidade C, e regressando ao local de partida. Nesse
percurso, não pode passar pela mesma cidade mais do que uma vez.
Na tabela seguinte, estão assinaladas com o sı́mbolo 3 as ligações rodoviárias existentes entre as cidades.
O sı́mbolo 7 significa que não existe ligação rodoviária entre as cidades.
A B C D E
A 3 7 3 3
B 3 7 3
C 3 7
D 3
O Sr. Pereira, ao organizar o percurso, considerou duas possibilidades:
alternativa 1: passar pela cidade A e só depois pela cidade E.

alternativa 2: passar pela cidade D antes de passar pela cidade B.
O Sr. Pereira afirma que a alternativa 1 permite definir mais percursos do que a alternativa 2.
O Sr. Pereira tem razão? Justifique, apresentando um grafo que modele a situação descrita, e identi-
fique todos os percursos possı́veis para cada uma das alternativas.
18/32
19. Uma agência de viagens, sediada no concelho de Avelares, organiza e vende, através da Internet, percursos
de autocarro entre várias cidades europeias.
Para organizar um percurso que passe por Amesterdão, Berlim, Munique, Paris e Viena, um funcionário
da agência começou por registar, na tabela seguinte, as distâncias mı́nimas, em quilómetros, entre cada
duas cidades.
Amesterdão Berlim Munique Paris Viena
Amesterdão 663 825 501 1148
Berlim 604 1055 674
Munique 828 435
Paris 1236
Viena
De forma a minimizar os custos operacionais, o funcionário definiu, através de um grafo, um percurso

fechado que liga as cinco cidades, tendo adotado o seguinte procedimento:
• escolher a aresta do grafo com menos peso, qualquer que ela seja;
• escolher, sucessivamente, as arestas de menos peso, garantindo que três arestas do percurso que está
que todos os vértices sejam incluı́dos;
• apresentar um percurso pretendido conforme o vértice de partida escolhido.
Apresente um percurso possı́vel, com inı́cio e fim em Amesterdão, de acordo com o procedimento utilizado
pelo funcionário da agência.
– o grafo usado, indicando os pesos de cada aresta;

– um percurso que o funcionário poderá ter definido.
19/32
20. O Francisco reside na vivenda A, em Penha Alta, e dá apoio domiciliário a residentes em quatro vivendas,
B, C, D e E.
Na tabela seguinte, estão registadas as distâncias mı́nimas, em metros, entre as cinco vivendas: A, B,
C, D e E.
B C D E
A 100 110 100 150
B — 100 190 110
C — — 180 140
D — — — 110
De modo a determinar a distância mı́nima a percorrer na visita aos residentes a quem dá apoio domiciliário,
o Francisco aplica o algoritmo seguinte.
• Define-se A como ponto de partida.
• Seleciona-se a vivenda mais próxima e estabelece-se a ligação entre as duas tendo em conta que, se
houver duas vivendas à mesma distância, a escolha é aleatória. Essa ligação é o caminho a percorrer
entre as duas vivendas.
• Procede-se como foi indicado no ponto anterior, não se repetindo nenhuma vivenda e regressando-se
ao ponto de partida depois de selecionar todas as vivendas.
Mostre, aplicando o algoritmo, que a escolha aleatória, quando existem duas vivendas à mesma distância,
pode levar o Francisco a percorrer uma distância maior do que seria necessário para visitar os residentes
a quem dá apoio domiciliário.
20/32
21. O conselho diretivo de uma faculdade pretende instalar cabo de fibra ótica a ligar sete pavilhões: A1, A2,
A3, A4, A5, A6 e A7.
Na tabela seguinte, encontram-se registadas algumas distâncias mı́nimas, em metros, entre os pavilhões.
A2 A3 A4 A5 A6 A7
A1 500 — — — 730 350
A2 — 190 — 200 340 —
A3 — — 150 100 — —
A4 — — — 220 240 —
A5 — — — — 220 —
A6 — — — — — 650
A instalação de cabo de fibra ótica custa 3,40 euros por metro.
De modo a minimizar o custo da instalação do cabo de fibra ótica, a ligação entre os pavilhões foi feita
recorrendo-se ao algoritmo seguinte.
• Ordenam-se as distâncias registadas na tabela anterior, pela ordem crescente da sua grandeza,
indicando-se, para cada distância, o par de pavilhões que lhe corresponde.
• Constrói-se um grafo, cujos vértices representam os pavilhões, selecionando-se, sucessivamente, as
distâncias menores e tendo-se em conta que, se a aresta a que corresponde a distância selecionada
não levar à formação de um circuito, essa aresta deve ser considerada; caso contrário, essa aresta não
deve ser considerada.
• O algoritmo termina quando, no grafo, o número de arestas é igual ao número de vértices menos um.
Determine, nestas condições, o custo mı́nimo da instalação do cabo de fibra ótica.
Na sua resposta, deve:

– aplicar o algoritmo;
– indicar o número mı́nimo de metros de cabo de fibra ótica necessários;
– calcular o custo mı́nimo da instalação do cabo de fibra ótica.
21/32
22. O Luı́s pretende visitar quatro cidades: Braga, Porto, Lamego e Viseu.
A viagem inicia-se e termina em Amarante, não importando a ordem pela qual as cidades são visita-
das, pois a partir de cada uma delas é possı́vel ir diretamente a qualquer uma das outras.
Na tabela seguinte, estão indicadas as distâncias, em quilómetros, entre as cidades referidas.
Braga Porto Lamego Viseu
Amarante 74 61 71 107
Braga — 70 117 130
Porto — — 106 75
Lamego — — — 62
O Luı́s pretende aplicar uma das opções seguintes para determinar um percurso com inı́cio e fim em
Amarante e no qual nenhuma cidade seja repetida.
Opção 1 Opção 2
Passo 1: define-se a cidade de Amarante Passo 1: ordenam-se as distâncias entre
como ponto de partida. cada par de cidades por ordem crescente,
indicando-se, para cada valor, o par de
Passo 2: seleciona-se a cidade mais cidades que lhe corresponde.
próxima, tendo em conta que, se houver
duas cidades à mesma distância, a seleção Passo 2: selecionam-se, sucessivamente,
é aleatória. as distâncias menores, tendo em conta
que:
Passo 3 e passos seguintes: • uma cidade nunca poderá aparecer
procede-se como foi indicado no passo an- três vezes;
terior, não se repetindo nenhuma cidade,
e regressando-se ao ponto de partida • nunca se fecha um circuito enquanto
depois de visitadas todas as cidades. houver cidades por visitar.
Passo 3: ordena-se a solução de acordo

com a cidade de partida (Amarante).
O Luı́s considera que a opção 1 dá um percurso cujo número total de quilómetros é inferior ao dado pela
opção 2.
Verifique se o Luı́s tem, ou não, razão.
• apresentar um grafo ponderado que represente a situação;

• aplicar cada uma das opções;
• indicar o número total de quilómetros percorridos em cada uma das duas opções;
• apresentar uma conclusão.
22/32
23. Um grupo de professores de Educação Fı́sica do agrupamento de escolas de Pontes de Cima pretende pro-
mover hábitos de vida saudáveis. Para a concretização desse projeto, os professores decidiram organizar
uma caminhada no jardim municipal.
Na figura seguinte, encontra-se um grafo que serve de modelo ao percurso dessa caminhada.
A D
C B
E
G F
No grafo, os vértices A, B, C, D, E, F e G representam os postos de visita obrigatória. Cada aresta

representa um trajeto direto que liga dois desses postos.
Mostre que não é possı́vel organizar um percurso para essa caminhada que cumpra, em simultâneo, as
seguintes condições:
• passar por todos os postos representados no grafo da figura anterior, começando e terminando no
posto A;
• percorrer uma só vez cada trajeto direto representado;
• percorrer todos os trajetos diretos representados.
23/32
24. Um arquiteto organizou o recinto destinado à realização de uma conferência internacional de arte (figura
seguinte). O recinto tem os seguintes espaços: auditório, cantina, espaço de debate, exposição, pátio e
teatro.
Todos os espaços têm, pelo menos, uma porta.
Ao analisar o esquema desenhado pelo arquiteto (figura anterior), uma funcionária comentou que, caso se
mantivesse o número de portas, não conseguiria efetuar uma ronda ao recinto começando e terminando
essa ronda na cantina, percorrendo todas as portas e passando por cada porta uma única vez.
A funcionária pretendeu, então, encontrar uma solução que lhe permitisse efetuar essa ronda percor-
rendo todas as portas e passando o menor número de vezes possı́vel por cada porta.
Determine, justificando, uma solução que permita satisfazer a pretensão da funcionária.

• apresentar um grafo que modele a situação descrita;
• apresentar o significado dos elementos, arestas e vértices, que constituem o grafo;
• apresentar, justificando, uma solução.
24/32
25. Na aldeia de Xisto, vai realizar-se uma minimaratona.
Na figura seguinte, encontra-se o grafo que serve de modelo ao percurso da minimaratona.
A
D
F
C
No grafo, o vértice B representa o ponto de partida e de chegada, e os vértices A, C, D, E e F representam

postos de distribuição de água.
Cada aresta representa um trajeto direto que liga dois postos de distribuição de água ou um posto de
distribuição de água ao ponto de partida.
Os organizadores da corrida decidiram que todos os participantes tinham de passar por todos os tra-
jetos diretos, sem repetirem nenhum.
O Carlos, um dos organizadores da corrida, observou o grafo e afirmou:
É impossı́vel passar por todos os trajetos diretos sem repetir nenhum. Para garantir que os participan-
tes passam por todos os trajetos diretos, é necessário admitir duplicações de trajetos diretos já existentes.
Justifique a veracidade da afirmação, e apresente no grafo um par de duplicações de trajetos diretos

que permita garantir que os participantes passam por todos os trajetos diretos.
Reproduza o grafo modificado na sua folha de respostas.
25/32
26. A junta de freguesia de Freixo promoveu atividades desportivas entre os habitantes da vila de Freixo (F)
e das aldeias A, B, C e D.
Na tabela seguinte, estão indicadas as distâncias, em quilómetros, entre A, B, C, D e F.
B C D F
A 28 38 30 18
B — 36 32 26
C — — 48 20
D — — — 24
Para transportar os habitantes, o presidente da junta de freguesia pretende encontrar um percurso que
ligue todos os locais referidos. De modo a encontrar esse percurso, o presidente da junta apoiou-se nos
dados da tabela anterior e no algoritmo seguinte.
Algoritmo
Passo 1: define-se a vila de Freixo como ponto de partida.
Passo 2: seleciona-se a aldeia mais próxima, tendo em conta que, se houver duas aldeias à mesma distância,
a seleção é aleatória.
Passo 3 e passos seguintes: procede-se como foi indicado no passo anterior, não se repetindo nenhuma
aldeia, e regressando-se ao ponto de partida depois de visitadas todas as aldeias.
Uma semana antes do inı́cio do serviço de transporte, é feito o anúncio seguinte.
Se a estrada que liga a aldeia A à aldeia B estiver intransitável, é necessário percorrer mais quilómetros
para utilizar um percurso alternativo.
Justifique a veracidade ou a falsidade da informação, aplicando o algoritmo acima descrito aos dois casos:
• a estrada que liga A a B está transitável;
• a estrada que liga A a B está intransitável.
26/32
27. O senhor Jerónimo e o senhor Manuel depositaram, cada um, a quantia de e25 000,00 em contas em duas
instituições financeiras.
O senhor Manuel ofereceu o capital acumulado no final de 2008 ao seu filho Miguel. Esse dinheiro foi
investido pelo Miguel na sua empresa de distribuição de congelados.
Na figura seguinte, encontra-se o grafo que serve de modelo à volta utilizada pelo camião da empresa
do Miguel, para efetuar a distribuição de congelados pelos supermercados que fornece. No grafo, o vértice
A representa a sede da empresa do Miguel, e os vértices B, C, D e E representam os supermercados. Cada
aresta representa um trajeto direto que liga dois supermercados, ou que liga um supermercado à sede da
empresa do Miguel.
A
B
E
O Miguel elaborou uma lista com as voltas de distribuição, que começam e terminam na sede da sua
empresa, visitando todos os supermercados, e não repetindo nenhum deles. Para o Miguel, o que importa
é o número de quilómetros percorridos, por isso, é indiferente, por exemplo, percorrer ABCDEA ou
percorrer AEDCBA.
27.1. Num determinado dia, o camião deve visitar, em primeiro lugar, o supermercado representado por
D, visitando depois os restantes, e não repetindo nenhum deles, antes de regressar à sede da empresa.
Identifique todas as voltas possı́veis para esse dia.
27.2. Mostre que o grafo da figura anterior admite, exatamente, doze voltas distintas, que podem fazer
parte da lista do Miguel.
28. Na figura seguinte, encontra-se o grafo que serve de modelo aos percursos utilizados pela RecSol, uma
empresa de recolha de resı́duos sólidos. Cada vértice do grafo representa um local de recolha de resı́duos
sólidos, e cada aresta representa uma estrada que liga dois desses locais.
B C
G F D
Na tabela seguinte, encontram-se registadas as distâncias mı́nimas, em metros, entre cada dois locais de
recolha de resı́duos sólidos, representados pelos vértices do grafo da figura anterior, quando se percorrem
as estradas representadas pelas arestas do mesmo grafo.
27/32
A B C D E F G
A — 1253 — — — — 1248
B — — 1421 — 712 938 —
C — — — 911 941 — —
D — — — — 1001 — —
E — — — — — 1198 —
F — — — — — — 832
G — — — — — — —
28.1. O António, um motorista da empresa RecSol, quer verificar se existem resı́duos abandonados ao longo
das estradas. Pretende partir do local representado pela letra A, percorrer todas as estradas, sem as
repetir, e regressar ao mesmo local.
Podem todas as pretensões do António ser satisfeitas, em simultâneo?
Justifique a sua resposta.
28.2. A RecSol vai ligar todos os locais de recolha de resı́duos sólidos com um cabo de fibra ótica, utilizando
algumas das estradas representadas no grafo da figura anterior.
De modo a usar a menor extensão de cabo de fibra ótica, a empresa contactou dois especialistas
em instalação de fibra ótica, o João e o José.
O João afirma, sem recurso a nenhum método, que a ligação que requer menos cabo é
{(A,B),(F,G),(B,F ),(B,E),(C,E),(C,D)}
O José propõe uma ligação apoiando-se no uso do algoritmo seguinte.
Algoritmo
Passo 1: Escolhem-se as duas arestas com o menor valor de distância.
Passo 2: Escolhe-se a aresta seguinte com o menor valor de distância, desde que essa aresta não feche
um circuito.
Passo 3: Repete-se o ponto anterior até que todos os vértices façam parte da árvore, tendo em conta
as regras seguintes:
• se houver empate na escolha de arestas, seleciona-se a aresta aleatoriamente;
• se a aresta a escolher fechar um circuito, essa aresta não deve ser considerada.
Indique qual das duas propostas deve escolher a empresa, de modo a usar a menor extensão de cabo
de fibra ótica.

• determinar o número de metros da proposta do João;
• aplicar ao grafo da figura anterior o algoritmo proposto pelo José;
• determinar o número de metros da proposta do José;
• apresentar uma conclusão sobre a escolha da empresa.
28/32
29. O António é carteiro. Habitualmente, organiza o percurso antes de iniciar a distribuição das encomendas.
Certo dia, o António decidiu fazer um grafo ponderado (figura seguinte), com as distâncias a cada um dos
locais de entrega das encomendas desse mesmo dia.
No grafo da figura seguinte, os seis vértices representam a estação de correios (C), a escola (E), o ginásio
(G), o restaurante (R), a fábrica (F) e a associação desportiva (A). Cada aresta do grafo representa um
trajeto direito entre dois dos locais já referidos. A ponderação de cada aresta representa a distância, em
metros, entre os locais considerados.
E
495
C G
700 700
250 250
R
A
923 F 895
O António pretende partir da estação de correios, (C), passar por todos os outros locais representados,
nos quais tem de entregar encomendas nesse dia, não mais do que uma vez por cada um deles, e regressar
depois à estação de correios, percorrendo o número mı́nimo de metros.
Defina um percurso que satisfaz o que o António pretende e indique o número de metros que ele tem
de percorrer.
30. A empresa Silva-Filhos dedica-se à limpeza de estradas. A empresa está sediada no distrito de Viseu.
Na figura seguinte, encontra-se o grafo que serve de modelo ao circuito utilizado pela empresa ao efe-
tuar a limpeza das estradas.
Cada vértice do grafo representa uma localidade, e cada aresta representa uma estrada que liga duas
localidades.
Penedono Ovadas
Resende
Ourozinho Freigil
Beselga
Pachorra
Antas
Considere a afirmação:
Não é possı́vel limpar todas as estradas representadas no grafo da figura anterior, percorrendo cada
estrada uma e uma só vez, se o camião de limpeza partir de Beselga e regressar a Beselga. Mas, é possı́vel
alterar esta situação.
Justifique a veracidade da afirmação anterior.
Reproduza o grafo da figura anterior, na folha de respostas, e acrescente-lhe uma aresta de modo que
o grafo obtido represente um modelo a partir do qual seja possı́vel limpar todas as estradas, percorrer
cada estrada uma e uma só vez, partindo de Beselga e regressando a Beselga.
29/32
31. A empresa GNC, de transporte de gás natural comprimido, está sediada em Sines. A sua frota de distri-
buição utiliza diferentes trajectos, que ligam as cidades de Coimbra, Évora, Faro, Lagos, Porto, Vila Real
e Sines. A distribuição começa sempre em Sines e termina sempre em Sines.
Na figura seguinte, encontra-se o grafo que serve de modelo aos vários circuitos utilizados pela GNC.
Cada vértice do grafo representa uma cidade, e cada aresta representa um trajecto que liga duas cidades.
Porto Vila Real
Coimbra
Évora
Sines
Faro
Lagos
31.1. Mostre que não é possı́vel organizar um circuito que permita que um camionista da GNC cumpra,
em simultâneo, as seguintes condições:
• entregar gás natural comprimido em todas as cidades representadas no grafo da figura anterior;
• percorrer, uma e uma só vez, cada trajeto representado;
• percorrer todos os trajetos representados.
31.2. Considere, agora, apenas os circuitos que incluem as cidades de Évora, Porto, Vila Real e Sines,
percorridas não necessariamente por esta ordem.
Na tabela seguinte, encontram-se as distâncias entre cada duas dessas cidades quando se percor-
rem os trajetos indicados pelas arestas do grafo da figura anterior.
Porto Vila Real Sines
Évora 406km 525km 172km
Porto — 125km 442km
Vila Real — — 559km

O preço do transporte cobrado pela empresa GNC aos clientes é de e 2,00 por quilómetro.
A empresa GNC faz um desconto de 8% sobre o preço total de transporte quando o camião, partindo
da refinaria de Sines, faz entregas de gás natural comprimido nas cidades de Évora, Porto e Vila
Real (percorridas não necessariamente por esta ordem), passando apenas uma vez por cada cidade,
e regressa à refinaria em Sines.
Determine o preço mı́nimo, em euros, que o comprador paga por cada transporte.
Na sua resposta deve:

• indicar o número de circuitos possı́veis e as respetivas extensões, referindo apenas os que têm
extensão distinta e obedecem aos critérios definidos;
• calcular o preço a pagar pelo menor circuito.
30/32
32. Uma Câmara Municipal elaborou um contrato com a empresa FUTUROLIMPO, empresa especializada
na recolha selectiva de resı́duos.
Na figura seguinte, apresenta-se um mapa de uma zona residencial desse municı́pio, que possui oito
espaços de recolha seletiva de resı́duos (ecopontos). Os oito ecopontos estão representados por E1 , E2 ,
E3 , E4 , E5 , E6 , E7 e E8 .
Designa-se por troço de rua a ligação entre dois ecopontos adjacentes, isto é, o percurso que se efetua
para ir de um desses ecopontos ao outro sem passar por mais nenhum.
32.1. Considere que o camião de recolha seletiva de resı́duos que passa por essa zona residencial inicia o
seu percurso no ecoponto E4 e que o termina no ecoponto E2 .
Admita que, em cada troço de rua, o camião pode estacionar junto de cada ecoponto, indepen-
dentemente do sentido de circulação.
Indique um percurso, de E4 a E2 , para que o camião possa recolher os resı́duos de todos os ecopontos,
passando por cada um deles uma única vez.
Apresente o percurso na forma de uma sequência, utilizando as designações dos ecopontos.
32.2. Os moradores da mesma zona residencial reclamaram das condições de alguns troços de rua de acesso
aos ecopontos. A Câmara Municipal decidiu enviar um funcionário especializado, para inspecionar
as condições dos mesmos.
Admita que o funcionário decidiu iniciar e terminar as suas inspeções junto do mesmo ecoponto.
No entanto, ao analisar o mapa da zona em causa, concluiu que, para concretizar essa decisão,
não tinha possibilidade de inspecionar todos os troços de rua, passando por cada um deles uma única
vez. Por isso, de forma a rendibilizar o tempo da inspeção, procurou encontrar um percurso cujo
número de troços de rua a percorrer fosse o menor possı́vel, garantindo o inı́cio e o fim da inspeção
junto do mesmo ecoponto.
Num pequeno texto:

• indique, justificando, a razão que levou o funcionário a concluir da impossibilidade de inspecionar
todos os troços de rua, passando por cada um deles uma única vez, tendo em conta que ele
pretende iniciar e terminar a inspeção junto do mesmo ecoponto;
• indique, ainda, um percurso que se inicie e termine no ecoponto E2 e que permita ao funcionário
inspecionar todos os troços de rua, sendo o número de troços de rua a percorrer o menor possı́vel.
Apresente o percurso na forma de uma sequência, utilizando as designações dos ecopontos.
Comece, obrigatoriamente, por modelar, através de um grafo, o mapa da zona residencial apresen-
tado, considerando que os vértices representam os ecopontos e que as arestas representam os troços
de rua.
31/32
33. O António vive em Lisboa e é vendedor de uma empresa nacional. Todas as semanas, parte de sua casa e
vai visitar duas cidades portuguesas, Faro e Coimbra, a fim de dar assistência aos seus clientes. A partir
da próxima semana, vai começar a dar também assistência a clientes de duas cidades espanholas, Sevilha
e Cáceres. Está neste momento a organizar um plano do percurso pelas quatro cidades: partindo de sua
casa, passa uma única vez por cada uma das quatro cidades e volta de novo a casa.
Pretende, também, percorrer o mı́nimo de quilómetros possı́vel. Na tabela seguinte, estão referidas as
distâncias, em quilómetros, entre aquelas cidades.
Lisboa Faro Sevilha Cáceres Coimbra
Lisboa 282 km 459 km 313 km 206 km
Faro 197 km 442 km 447 km
Sevilha 260 km 625 km
Cáceres 346 km
Coimbra
33.1. Desenhe um grafo ponderado que sirva de modelo às várias hipóteses de percurso possı́veis. Como
peso, atribua a cada aresta a distância, em quilómetros, a ela associada.
33.2. O António está convencido de que, se tiver de visitar, em primeiro lugar, o cliente de Coimbra, per-
correndo depois as restantes cidades, antes do regresso a Lisboa, o percurso mais curto, nas condições
a que está sujeito, consiste em seguir de Coimbra para Faro e só depois visitar as cidades espanholas,
antes do regresso a Lisboa.
Numa composição, justifique se o António tem razão.
Deve incluir, obrigatoriamente, na sua composição:

• o número total de circuitos que obedecem aos critérios definidos;
• a identificação de todos os percursos possı́veis, bem como a distância percorrida em cada um
deles;
• a conclusão final, identificando o percurso de extensão mı́nima.
32/32
34. Alguns visitantes menos civilizados do Parque da Pena, em Sintra, têm por hábito deitar para o chão
sacos de plástico, paus de gelado, latas de refrigerante, etc.
Um grupo de jovens amantes da natureza decide, durante uma tarde, ajudar a recolher todo o lixo exis-
tente nos caminhos duma zona do Parque.
Na figura seguinte, está um mapa dessa zona do Parque da Pena. Os cruzamentos dos caminhos estão
assinalados por letras, de A a F.
Admita que o grupo de jovens parte do ponto A, assinalado no mapa, percorre todos os caminhos assina-
lados, recolhendo o lixo, e regressa ao ponto A.
34.1. O grupo de jovens tem de percorrer pelo menos um caminho, mais do que uma vez.
Justifique esta afirmação, começando por modelar, por meio de um grafo, o mapa da zona do Parque
da Pena representado na figura.
34.2. Indique um percurso em que o número de caminhos percorridos mais do que uma vez seja o menor
possı́vel.
Dê a sua resposta na forma de uma sequência de letras, de acordo com a sequência de cruzamentos
do percurso por si escolhido.
34.3. Na obra de Joseph Malkevitch, Modelos de Grafos, pode ler-se: “A ideia chave na modelação ma-
temática consiste em tomar a situação original e simplificá-la de tal modo que fiquemos com uma
nova visão sobre o problema original.
Elabore uma composição onde desenvolva a ideia expressa, nesta frase, por Joseph Malkevitch.
Baseie-se no modelo que considerou nas alı́neas anteriores ou num exemplo à sua escolha, que integre
a utilização de grafos.
Nessa composição deve referir:

• o porquê da necessidade de simplificar a realidade;
• o porquê da necessidade de distinguir o essencial do acessório;
• os aspetos que foram simplificados, relativamente a situação original.

Grafos

Enviado por

Direitos autorais:

Formatos disponíveis

Grafos

Enviado por

Dados do documento

Descrição original:

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Grafos

Enviado por

Direitos autorais:

Formatos disponíveis

M.A.C.S. (11.

Exame – 2020, Ép. especial

Na sua resposta, apresente o grafo que resulta da aplicação do método descrito.

Cidades Viena Salzburgo Paris Milão Veneza Zurique

França Paris 850 1100 650

Na sua resposta, apresente:

De modo a minimizar os custos da intervenção, construiu-se um grafo, adotando-se o procedimento

Determine o custo total da substituição.

Na sua resposta, apresente o grafo que resulta da aplicação do método descrito.

6. O Clube de Colecionadores possui um espaço próprio para exposições.

Na sua resposta, apresente um grafo que modele a situação descrita.

Tarefa Duração (minutos) Tarefas precedentes

Na sua resposta, apresente um grafo que modele a situação descrita.

Exame – 2019, 1.a Fase

Para a seleção das estradas recorreu-se ao algoritmo seguinte.

• Constrói-se um grafo, cujos vértices representam as localidades, selecionando-se, sucessivamente, as

Exame – 2018, Ép. especial

Ilha N.o de habitantes

Fonte: Censos 2011

Na sua resposta, apresente:

Exame – 2018, 2.a Fase

Bratislava Praga Varsóvia Viena

Na sua resposta, apresente:

Exame – 2018, 1.a Fase

Exame – 2017, Ép. especial

Na sua resposta, apresente:

Exame – 2017, 2.a Fase

Na sua resposta, apresente:

Exame – 2017, 1.a Fase

Na sua resposta, apresente:

– a ordenação, de forma crescente, das distâncias registadas na tabela anterior;

Exame – 2016, Ép. especial

Exame – 2016, 2.a Fase

Na sua resposta, apresente:

Exame – 2016, 1.a Fase

17. A companhia de aviação ASA5 opera nos aeroportos nacionais.

Na sua resposta, apresente:

Exame – 2015, Ép. especial

18. O Sr. Pereira é motorista da empresa PTM.

O Sr. Pereira, ao organizar o percurso, considerou duas possibilidades:

alternativa 1: passar pela cidade A e só depois pela cidade E.

Exame – 2015, 2.a Fase

Amesterdão Berlim Munique Paris Viena

Amesterdão 663 825 501 1148

Berlim 604 1055 674

Munique 828 435

De forma a minimizar os custos operacionais, o funcionário definiu, através de um grafo, um percurso

Na sua resposta, apresente:

– o grafo usado, indicando os pesos de cada aresta;

Exame – 2015, 1.a Fase

A 100 110 100 150

B — 100 190 110

Exame – 2014, 2.a Fase

A1 500 — — — 730 350

A2 — 190 — 200 340 —

A instalação de cabo de fibra ótica custa 3,40 euros por metro.

Determine, nestas condições, o custo mı́nimo da instalação do cabo de fibra ótica.

Na sua resposta, deve: