Exercícios de Grafos e algoritmos

20 exercícios de Grafos e algoritmos de Matemática Aplicada às Ciências Sociais que saíram no Exame Nacional (2021-2026). Com resolução passo a passo.

Exercício 4 · 1.ª fase 2026

Determinar a ordem de visita de cidades por parte da Maria com base nas capacidades dos estádios (Tabela 3) e tempos de voo direto (Tabela 4), aplicando o algoritmo do vizinho mais próximo com critério de desempate, e representar o grafo correspondente.

Exercício 5 · 2.ª fase 2026

Modelar a inscrição de membros da direção nas 6 sessões de ciclismo de pista (E, I, K, M, O, P) através de um grafo que represente as incompatibilidades/compatibilidades de ocorrência simultânea, determinar a constituição de cada bloco de sessões e o número mínimo de blocos necessários para que Iúri Leitão assista a…

Exercício 4 · Época especial 2026

Modelação de uma planta simplificada através de um grafo para encontrar um percurso que comece e termine na área A, passando por todas as portas/passagens exatamente uma vez (circuito de Euler). Determinar que áreas recebem a nova passagem e justificar com base nos graus dos vértices.

Exercício 3 · 1.ª fase 2025

Com base no grafo de precedências e durações de tarefas dado na Figura 1, selecionar a opção correta para cada um dos quatro espaços (I, II, III e IV).

Exercício 4 · 1.ª fase 2025

Determinar as distâncias em falta no grafo da Figura 2 recorrendo ao mapa da Figura 3. Aplicar o algoritmo de ordenação de arestas para construir um percurso fechado hamiltoniano que visite todos os vértices e apresentar um possível percurso.

Exercício 4 · 2.ª fase 2025

Aplicação do algoritmo do vizinho mais próximo a uma matriz de distâncias (Tabela 4) entre cinco postos de controlo (C1 a C5), iniciando em C2 e passando por todos sem repetir. Determinar o comprimento do percurso, a ordem de passagem e apresentar o grafo resultante.

Exercício 4 · Época especial 2025

Determinar o comprimento mínimo, em metros, de cabo de fibra ótica necessário instalar para interligar seis departamentos (D1 a D6) aplicando o algoritmo de Prim (árvore abrangente mínima) e apresentar o grafo resultante com as distâncias selecionadas.

Exercício 4 · 1.ª fase 2024

Modelar o jogo de peças como um grafo onde cada vértice é uma letra e cada aresta é uma peça. Apresentar o grafo correspondente às peças da Figura 2, uma razão que justifique a impossibilidade de criar a sequência pretendida e indicar as letras da peça em falta.

Exercício 4 · 2.ª fase 2024

Problema de modelação com grafos e empilhamento de cartas (A, B, C, D, E, F e a desaparecida G). Pede a construção do grafo das seis primeiras cartas, verificar se o algarismo da carta G pode ser o 3 e indicar um possível empilhamento das sete cartas iniciando por D, A e B.

Exercício 3.2 - Grafos e algoritmos · Época especial 2024

Identificar a tabela compatível com os graus dos vértices de um grafo conexo com vértices L1, L3, L5, L7 e L9, sabendo que ao adicionar uma aresta entre L3 e L7 o grafo passa a admitir um circuito de Euler.

Exercício 4 · Época especial 2024

A partir das tabelas com altitudes e ligações diretas entre miradouros na ilha da Madeira, modelar um grafo com os miradouros de altitude superior a 350 metros e determinar o percurso seguido pela Dora, começando pelo de maior altitude e escolhendo sempre o miradouro de maior altitude de entre os ligados diretamente e…

Exercício 2 · 1.ª fase 2023

2.1. Completar o texto sobre percursos possíveis no recinto da festa que visitam todos os expositores a partir de L. 2.2. Aplicar o algoritmo do vizinho mais próximo a partir de R1 para determinar o grafo, o percurso e a distância total percorrida.

Exercício 2 · 2.ª fase 2023

Calcular o número mínimo de troços pedonais a construir para que o grafo admita um circuito euleriano.

Exercício 3 · 2.ª fase 2023

Aplicar o método das arestas ordenadas à tabela de durações de viagens entre Atenas (A), Istambul (I), Volos (V), Mykonos (M), Rodes (R) e Santorini (S). Apresentar a ordenação das arestas selecionadas, o grafo que modela a situação, um possível itinerário e concluir se a Luísa poderá visitar os locais pela mesma…

Exercício 3 · 1.ª fase 2022

Apresentar um grafo que modele as reuniões de trabalho para agendamento sem conflitos de horário, identificar a constituição de cada bloco de reuniões e indicar o tempo mínimo total necessário em horas.

Exercício 3 · 2.ª fase 2022

Determinar um itinerário para recolha de ecopontos com início e fim no portão (P) aplicando o algoritmo das arestas ordenadas (Kruskal modificado para ciclo hamiltoniano). Apresentar a ordenação das arestas selecionadas, um grafo que modele a situação e um itinerário possível.

Exercício 3 · Época especial 2022

Determinar o percurso de inspeção de estádios de futebol (com capacidade superior a 85 000 espectadores) utilizando o algoritmo das arestas ordenadas / árvore geradora mínima adaptado para circuito Hamiltoniano, apresentando o grafo e a ordem de visita com início na África do Sul.

Exercício 3 · 1.ª fase 2021

A partir do esquema de ligações entre postos de comunicação P1 a P6, determinar o grafo resultante da aplicação do algoritmo do vizinho mais próximo com início em P4, e calcular a quantidade mínima, em quilómetros, de cabo de fibra ótica a renovar.

Exercício 4 · 2.ª fase 2021

A partir de uma tabela de comprimentos de fio de luzes entre seis edifícios (E1 a E6), aplicar o algoritmo de Prim para construir uma árvore de suporte mínima, determinar o comprimento mínimo do fio e calcular o custo total a 3,5 €/m.

Exercício 4 · Época especial 2021

De modo a garantir o isolamento acústico entre os diferentes espaços onde funciona a rádio OnOfff, cada uma das portas de ligação irá ser calafetada. Na Figura 1, apresenta-se uma planta com um pátio, uma receção e seis salas (S1 a S6). O responsável pretende definir um percurso com início e fim no pátio, cruzando…

Outros temas de Matemática Aplicada às Ciências Sociais

Métodos de apoio à decisão

Modelos matemáticos

Estatística e probabilidades