Matematica

ESCOLA SECUNDÁRIA DE CALDAS DAS TAIPAS
MATEMÁTICA APLICADA ÀS CIÊNCIAS SOCIAIS (11.º ano) 2024/2025
Ficha de Trabalho 2
Modelos de Grafos (Grafos de Euler; Grafo de Hamilton; Árvores abrangentes)
1. Considera os seguintes grafos:
1.1. Verifica se os grafos a seguir

indicados têm circuito de Euler.
1.2. Verifica se têm caminho de Euler

e em caso afirmativo indique um.
1.3. Verifica se existem caminhos de Hamilton em cada um dos grafos e em caso afirmativo indique
um.
2. Considera o seguinte grafo.
2.1. Aplicando o algoritmo da cidade mais próxima calcule o

caminho mínimo do grafo começando em a.
2.2. Encontra uma árvore abrangente mínima do grafo.
3. A empresa GNC, de transporte de gás natural comprimido, está sediada em Sines. A sua frota de
distribuição utiliza diferentes trajetos, que ligam as cidades de Coimbra, Évora, Faro, Lagos, Porto, Vila
Real e Sines. A distribuição começa sempre em Sines e termina sempre em Sines.
Na figura 1, encontra-se o grafo que serve de modelo aos
vários circuitos utilizados pela GNC.
Cada vértice do grafo representa uma cidade, e cada aresta
representa um trajeto que liga duas cidades.
3.1. Mostra que não é possível organizar um circuito que permita que um camionista da GNC cumpra,
em simultâneo, as seguintes condições:
• entregar gás natural comprimido em todas as cidades representadas no grafo da figura 1;
• percorrer, uma e uma só vez, cada trajeto representado;
• percorrer todos os trajetos representados.
3.2. Considera, agora, apenas os circuitos que incluem as cidades de Évora, Porto, Vila Real e Sines,
percorridas não necessariamente por esta ordem. Na tabela seguinte, encontram-se as distâncias
entre cada duas dessas cidades quando se percorrem os trajetos indicados pelas arestas do grafo
da figura 1.
Catarina Ferreira Página 1 de 3

O preço do transporte cobrado pela empresa GNC aos clientes é de € 2,00 por quilómetro.
A empresa GNC faz um desconto de 8% sobre o preço total de transporte quando o camião, partindo da
refinaria de Sines, faz entregas de gás natural comprimido nas cidades de Évora, Porto e Vila Real
(percorridas não necessariamente por esta ordem), passando apenas uma vez por cada cidade, e regressa
à refinaria em Sines.
Determina o preço mínimo, em euros, que o comprador paga por cada transporte.
Na tua resposta deves:
• indicar o número de circuitos possíveis e as respetivas extensões, referindo apenas os que têm
extensão distinta e obedecem aos critérios definidos;
• calcular o preço a pagar pelo menor circuito.
Exame 2009 – 2.ª fase
4. O Luís pretende visitar quatro cidades: Braga, Porto, Lamego e Viseu. A viagem inicia-se e termina em
Amarante, não importando a ordem pela qual as cidades são visitadas, pois a partir de cada uma delas é
possível ir diretamente a qualquer uma das outras. Na tabela seguinte, estão indicadas as distâncias, em
quilómetros, entre as cidades referidas.
O Luís pretende aplicar uma das opções seguintes para determinar um percurso com início e fim em
Amarante e no qual nenhuma cidade seja repetida.

O Luís considera que a opção 1 dá um percurso cujo número total de quilómetros é inferior ao dado pela
opção 2. Verifique se o Luís tem, ou não, razão. Na sua resposta, deve:
• apresentar um grafo ponderado que represente a situação;
• aplicar cada uma das opções;
• indicar o número total de quilómetros percorridos em cada uma das duas opções;
• apresentar uma conclusão.
Exame 2013, Época especial
5. Um escritório de contabilidade contratou uma empresa para fazer o serviço de limpeza. A empresa terá
de limpar todas as divisões do escritório. Na figura abaixo está representada a planta do escritório.
Cada divisão está assinalada pelas letras de A a G.
A D
C
E F G
5.1. A equipa de limpeza tem passar por todas as portas pelo menos uma vez. Diga, justificando, se é
possível encontrar um percurso que permita passar por todas as portas uma única vez.
Na sua resposta, apresente:
 um grafo que modele a planta do escritório;
 o significado dos elementos, arestas e vértices que constituem o grafo;
 uma conclusão acerca da possibilidade de encontrar um percurso nas condições
descritas.
5.2. A chefe de limpeza, após analisar a planta do escritório afirmou:

“É impossível efetuar a limpeza passando por todas as portas uma única vez iniciando e
terminando na divisão A sem repetir pelo menos uma porta.”
Justifique a veracidade desta afirmação.
Na sua resposta, apresente:
 justificação da afirmação efetuada;
 um grafo modificado;
 um percurso.
5.3. No final da limpeza efetuada, a chefe de equipa, foi inspecionar todas as divisões.
Considerando que para verificar uma divisão não precisa de passar por todas as portas, indique
um percurso que inicie e termine na divisão D.

Matematica

Enviado por

Direitos autorais:

Formatos disponíveis

Matematica

Enviado por

Dados do documento

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

Matematica

Enviado por

Direitos autorais:

Formatos disponíveis

ESCOLA SECUNDÁRIA DE CALDAS DAS TAIPAS

MATEMÁTICA APLICADA ÀS CIÊNCIAS SOCIAIS (11.º ano) 2024/2025

1. Considera os seguintes grafos:

1.1. Verifica se os grafos a seguir

1.2. Verifica se têm caminho de Euler

2. Considera o seguinte grafo.

2.1. Aplicando o algoritmo da cidade mais próxima calcule o

2.2. Encontra uma árvore abrangente mínima do grafo.

Catarina Ferreira Página 1 de 3

Catarina Ferreira Página 2 de 3

5.2. A chefe de limpeza, após analisar a planta do escritório afirmou:

Catarina Ferreira Página 3 de 3

Você também pode gostar