Exercícios de Exame — Teoria de grafos

Num encontro de ciclismo vão realizar-se seis sessões de esclarecimento, E, I, K, M, O e P, cada uma com um tema diferente.

Na tabela seguinte, indicam-se as sessões em que cada participante se inscreveu.

Como cada participante tem de assistir a todas as sessões em que se inscreveu, é necessário organizar as sessões em blocos que possam decorrer em simultâneo.

Determine o número mínimo de blocos de sessões necessário.

Na sua resposta, apresente um grafo que modele a situação descrita e identifique a constituição de cada bloco.

Como interpretar. Duas sessões não podem decorrer ao mesmo tempo se houver alguém inscrito em ambas. Liga-se por uma aresta cada par nessas condições; os blocos são conjuntos de vértices não ligados entre si.

Observando os dados da tabela, podemos modelar por um grafo em que cada vértice representa uma sessão, e em que cada aresta representa um par de sessões que não podem decorrer em simultâneo:

• aresta EO — participação da Alice;
• arestas EI e EM — participação do Rui;
• arestas IK, IM e KM — participação do César;
• aresta KO — participação do Fábio;
• aresta MP — participação do Gil;
• aresta OP — participação da Júlia.

Assim, podem ser organizados 3 blocos de sessões a realizar em simultâneo, ou seja, que não estão ligadas por uma aresta no grafo, nomeadamente:

• E, P e K
• I e O
• M

O número mínimo de blocos é 3.

A Maria vai assistir a jogos de um campeonato mundial de futebol. Na tabela seguinte, apresentam-se os estádios candidatos, o país onde se localizam e a respetiva capacidade.

A Maria selecionou o estádio de maior capacidade de cada país e, além desses, todos os estádios com capacidade acima de 70 000 espectadores.

Na tabela seguinte, indicam-se os tempos de voo entre as cidades.

Partindo de Kansas City, a Maria define a ordem de visita escolhendo sempre, de entre as cidades ainda não visitadas, aquela cujo voo tem menor duração.

Indique a ordem pela qual a Maria visitará as cidades.

Na sua resposta, apresente um grafo que resulte da aplicação do método descrito.

Como interpretar. É o algoritmo do vizinho mais próximo: em cada passo escolhe-se o voo mais curto para uma cidade ainda por visitar. O primeiro passo é selecionar quais os estádios que interessam.

1.º — Estádios selecionados

• Vancouver (V) — maior capacidade do Canadá;
• Dallas (D) — maior capacidade dos EUA;
• Cidade do México (M) — maior capacidade do México;
• Atlanta (A) — capacidade acima de 70 000;
• Kansas City (K) — capacidade acima de 70 000;
• Nova Iorque (N) — capacidade acima de 70 000.

2.º — Aplicar o algoritmo, partindo de K

• I — voo KD (menor tempo a partir de K)
• II — voo DM (menor tempo a partir de D entre as ainda não visitadas)
• III — voo MA (menor tempo a partir de M)
• IV — voo AN (menor tempo a partir de A)
• V — voo NV (única cidade selecionada ainda por visitar)

Kansas City (K) → Dallas (D) → Cid. do México (M) → Atlanta (A) → Nova Iorque (N) → Vancouver (V)

Numa empresa, pretende-se instalar cabo de fibra ótica a ligar seis departamentos, D1, D2, D3, D4, D5 e D6.

Na tabela seguinte, apresentam-se os comprimentos, em metros, das ligações possíveis entre os departamentos.

De modo a minimizar o comprimento de cabo, seleciona-se, a partir de D1, a ligação de menor comprimento a um departamento ainda não ligado, repetindo o processo até todos os departamentos estarem ligados.

Determine o comprimento mínimo, em metros, de cabo de fibra ótica a instalar.

Na sua resposta, apresente um grafo que resulte da aplicação do método descrito.

Como interpretar. Constrói-se uma árvore geradora mínima, partindo de D1 e juntando de cada vez a ligação mais curta que alcança um departamento ainda não ligado.

• I: D1
• II: D1–D6 (80 m)
• III: D6–D3 (51 m)
• IV: D6–D2 (54 m)
• V: D3–D4 (140 m)
• VI: D4–D5 (43 m)

$80 + 51 + 54 + 140 + 43 = 368 \text{ m}$

São necessários, no mínimo, 368 metros de cabo.

Numa prova de orientação, existem cinco postos de controlo, C1, C2, C3, C4 e C5.

Na tabela seguinte, estão indicadas as distâncias, em metros, entre os postos de controlo.

A prova inicia-se no posto de controlo C2 e, em cada etapa, segue-se para o posto de controlo mais próximo de entre os ainda não visitados, até todos terem sido visitados.

Determine o comprimento do percurso da prova.

Na sua resposta, apresente a sequência de postos de controlo e um grafo ponderado que represente o percurso escolhido.

Como interpretar. Vizinho mais próximo a partir de C2, sem repetir postos. O percurso é aberto: não se regressa a C2.

• I: C2–C4 (2360 m)
• II: C4–C3 (2225 m)
• III: C3–C1 (2400 m) (não se seleciona C3–C4 nem C3–C2, porque C4 e C2 seriam repetidos)
• IV: C1–C5 (1780 m)

Desta forma, a ordem de passagem pelos postos de controlo é: C2 → C4 → C3 → C1 → C5.

$2360 + 2225 + 2400 + 1780 = 8765 \text{ m}$

O percurso da prova tem 8765 metros.

O Edgar tem de concretizar seis tarefas, $T_1$, $T_2$, $T_3$, $T_4$, $T_5$ e $T_6$.

No grafo seguinte, cada vértice representa uma tarefa e o número inscrito representa o número de dias necessários para a concretizar. Cada aresta orientada representa uma relação de precedência.

Complete o texto seguinte, selecionando a opção correta para cada espaço.

Antes de dar início à tarefa $T_5$, o Edgar tem de concluir, no mínimo, I tarefas. Até dar por concluída a tarefa $T_3$, são necessários, no mínimo, II dias. Para concluir todas as tarefas, no número mínimo de dias, o Edgar tem de iniciar, nomeadamente, as tarefas III em simultâneo. O Edgar necessita, no mínimo, de IV dias para concretizar todas as tarefas.

A Leonor faz caminhadas entre seis locais. Nas figuras seguintes, apresentam-se as ligações entre esses locais e as respetivas distâncias, em metros.

A Leonor pretende definir um percurso que passe por todos os locais, sem repetir nenhum, começando e terminando em sua casa.

Para o definir, escolhe sempre a ligação de menor comprimento, garantindo que não se juntam três arestas num mesmo vértice e que não se fecha o percurso antes de incluir todos os locais.

Apresente um percurso possível definido pela Leonor.

Como interpretar. É o algoritmo da aresta de menor peso para construir um circuito de Hamilton. Começa-se por reunir todas as distâncias, somando os troços quando a ligação entre dois locais passa por pontos intermédios.

1.º — Distâncias entre os seis locais

• $CE$: 748 m
• $CQ$: 355 m
• $CM$: 382 m
• $EQ$: 350 m
• $EV$: $450+800 = 1250$ m
• $PV$: 550 m
• $PQ$: $700+400 = 1100$ m
• $PM$: $700+400+160 = 1260$ m

2.º — Aplicar o algoritmo

• I — aresta $CQ$: 355 m (menor distância a partir da casa da Leonor)
• II — aresta $QE$: 350 m
• III — aresta $EV$: 1250 m (não se considera $EC$, porque fecharia o percurso)
• IV — aresta $VP$: 550 m
• V — aresta $PM$: 1260 m (não se considera $PQ$, porque fecharia o percurso)
• VI — aresta $MC$: 382 m

Um percurso possível é $C \to Q \to E \to V \to P \to M \to C$ (o percurso $C \to M \to P \to V \to E \to Q \to C$ também satisfaz as condições).

As levadas são canais de água cuja função original era o transporte de água do norte da ilha da Madeira, onde o clima é mais húmido, para o sul da ilha, onde o clima é mais seco. Atualmente, os percursos pedestres ao longo das levadas são uma das atrações turísticas da Madeira.

Um morador de uma das freguesias da ilha da Madeira construiu um grafo que modela a existência de troços pedonais que permitem transitar entre as levadas L1, L3, L5, L7 e L9. Nesse grafo, conexo, os vértices representam as levadas e as arestas representam os troços pedonais que permitem transitar entre levadas. Com base nesse grafo, o morador chegou à conclusão de que bastaria construir um novo troço pedonal entre as levadas L3 e L7, que ainda não existia, para ser possível iniciar e terminar um percurso numa mesma levada, percorrendo todos os troços pedonais, incluindo o novo, sem repetir nenhum deles.

Qual das tabelas pode apresentar o grau de cada vértice do grafo que o morador construiu?

Na ilha da Madeira, existem diversos miradouros com vistas deslumbrantes.

A Dora consultou um blogue sobre viagens, no qual estavam indicadas as altitudes de diversos miradouros, assim como informação sobre ligações diretas entre eles, quer fossem rodoviárias quer fossem pedonais.

Na tabela seguinte, estão registadas as altitudes, em metros, dos miradouros referidos no blogue.

Na tabela seguinte, estão assinaladas com o símbolo ✓ as ligações diretas entre os miradouros, indicadas no blogue. O símbolo ✗ significa que, no blogue, não estava indicada a existência de uma ligação direta entre os miradouros.

A Dora pretende visitar miradouros de altitude superior a 350 metros e que tenham ligações diretas entre si.

Para definir o seu percurso, construiu um grafo, tendo por base a informação apresentada nas tabelas anteriores.

Depois de construir o grafo, a Dora definiu o percurso, começando pelo miradouro de maior altitude. Em seguida, usando as ligações diretas, optou sempre pelo miradouro que, de entre os restantes, tem maior altitude.

Quantos miradouros poderá a Dora visitar, nestas condições?

Na sua resposta, apresente um grafo semelhante ao que a Dora construiu e o percurso definido pela Dora.

Como interpretar. Primeiro filtram-se os miradouros com altitude superior a 350 m; depois aplica-se a regra «seguir sempre para o mais alto ainda não visitado, desde que haja ligação direta».

Como a Dora pretende visitar miradouros de altitude superior a 350 metros, apenas se consideram os miradouros B, CG, E, PA, PB e PR.

• I — PR (maior altitude) (alternativas: PA (1818), E (1007) e B (860))
• II — PA (alternativas: PR (já visitado), E (1007) e B (860))
• III — E (alternativas: PR e PA (já visitados), CG (580) e PB (355))
• IV — CG (alternativas: E (já visitado), PB (355))
• V — PB (alternativas: E e CG (já visitados), B (860))
• VI — B (alternativas: PR, PA, PB (já visitados))

A Dora poderá visitar seis miradouros: PR → PA → E → CG → PB → B.

Sala de Fuga é um jogo em que uma equipa, fechada numa sala ou num conjunto de salas, tem de resolver desafios, num intervalo de tempo limitado, para o conseguir concluir. Para ter sucesso e resolver os desafios, é necessário recorrer a diversas competências e apelar ao raciocínio lógico e à intuição.

Numa das salas de um jogo de Sala de Fuga, estava exposto um conjunto de seis cartas, A, B, C, D, E e F, semelhante ao apresentado na figura seguinte.

Nas cartas A e D está desenhado um círculo, nas cartas B e F, um quadrado, e nas cartas C e E, um triângulo. As cartas A, B e C estão numeradas com o algarismo 1, a carta D com o 2, a carta E com o 3 e a carta F com o 4.

Junto às cartas, estava um pergaminho com o desafio seguinte.

A equipa do Filipe verificou que, por exemplo, a carta B poderia ser colocada sobre a carta F, porque ambas têm desenhado um quadrado, ou então a carta C poderia ser colocada sobre a carta A, porque ambas têm o algarismo 1.

Para agilizar a resolução do desafio, a equipa decidiu construir um grafo. Nesse grafo, a letra de cada carta correspondia a um vértice, e as arestas representavam a possibilidade de uma carta ser empilhada sobre outra.

O algarismo presente na sétima carta (carta G) poderá ser o 3?

Na sua resposta, apresente um grafo semelhante ao que a equipa terá construído, sem incluir a carta G, e um possível empilhamento das sete cartas, A, B, C, D, E, F e G.

Como interpretar. Duas cartas ligam-se se partilharem a figura geométrica ou o algarismo. Empilhar as sete cartas é encontrar um caminho de Hamilton no grafo.

• Carta A — conecta com as restantes com número 1 (B e C) e as restantes com círculo (D).
• Carta B — conecta com as restantes com número 1 (A e C) e as restantes com quadrado (F).
• Carta C — conecta com as restantes com número 1 (A e B) e as restantes com triângulo (E).
• Carta D — conecta com as restantes com um círculo (A). Não existem outras com o número 2.
• Carta E — conecta com as restantes com um triângulo (C). Não existem outras com o número 3.
• Carta F — conecta com as restantes com um quadrado (B). Não existem outras com o número 4.

Acrescentando ao grafo anterior um vértice que represente a carta G, que ficará conectado ao vértice F, porque sabemos que tem um quadrado, e para averiguar a possibilidade de ter o número 3, deverá ser conectado também com o vértice E, obtém-se o grafo seguinte:

Assim, ignorando as arestas AC e BC, podemos observar que é possível que o algarismo presente na carta G seja o 3.

Sim. Um empilhamento possível é $D \to A \to B \to F \to G \to E \to C$ (o percurso $D \to A \to B \to C \to E \to G \to F$ também satisfaz as condições).

A Estrada Nacional 2 (EN2) foi incluída no Plano Rodoviário Nacional de 1945. É a mais extensa estrada portuguesa, totalizando 739,26 quilómetros, e a única na Europa que atravessa um país em toda a sua extensão, desde Chaves até Faro, passando por 35 concelhos.

Durante as pausas na viagem ao longo da EN2, alguns viajantes aproveitam para se divertir com jogos.

O Manuel inventou um jogo, criando peças divididas ao meio. Nas extremidades de cada peça, inscreveu uma das letras, A, B, C, D, E ou F.

A figura seguinte apresenta a totalidade das peças criadas pelo Manuel.

O objetivo deste jogo é criar uma sequência:

• formada por todas as peças, independentemente da primeira peça a ser jogada;
• em que duas peças adjacentes têm de ter letras iguais nas extremidades de contacto, como se exemplifica na figura seguinte.

Para averiguar se as peças criadas eram suficientes para formar uma sequência nas condições descritas, o Manuel decidiu construir um grafo.

No grafo construído, cada vértice representa uma das letras utilizadas nas peças criadas pelo Manuel, e cada aresta representa uma peça. Assim, por exemplo, a aresta AB representa a existência da peça em que uma das extremidades tem a letra A e a outra extremidade tem a letra B.

Depois de construir o grafo, o Manuel concluiu que faltava uma peça ao jogo.

Indique as letras que devem estar inscritas nas extremidades da peça em falta.

Na sua resposta, apresente um grafo semelhante ao que o Manuel terá construído e uma razão que justifique a impossibilidade de atingir o objetivo do jogo, utilizando apenas as peças da figura inicial.

Como interpretar. Usar todas as peças (arestas) uma só vez, começando em qualquer peça, é um circuito de Euler — exige todos os vértices de grau par.

Pela análise do grafo podemos observar que existem dois vértices de grau ímpar, nomeadamente de grau 3 (os vértices $C$ e $E$). Assim, o jogo só pode ser completado se a sequência começar com a letra C e terminar com a letra E (ou vice-versa), o que não corresponde ao pretendido, porque a sequência deveria ser possível independentemente da primeira peça a ser jogada.

Desta forma, se o grafo tiver uma aresta adicional a ligar os vértices $C$ e $E$, todos os vértices teriam grau par, permitindo criar um circuito de Euler, ou seja percorrer todas as arestas, apenas uma vez, e começando em qualquer vértice.

A peça em falta deve conter as letras C e E.

Num dos navios de cruzeiro da empresa LZD, existe um circuito de manutenção com seis estações. Um circuito de manutenção consiste numa série de exercícios físicos dispostos sequencialmente (em estações), de modo que os turistas, quando passam pelas estações, têm a possibilidade de executar o exercício proposto.

Na figura ao lado, apresenta-se um grafo, no qual os vértices representam as estações, e as arestas representam os troços pedonais existentes entre elas.

Pretende-se construir novos troços pedonais entre as estações existentes, para que seja possível iniciar e terminar o circuito de manutenção numa mesma estação, percorrendo todos os troços, incluindo os novos, sem repetir nenhum deles.

Qual o número mínimo de troços pedonais a construir?

Como interpretar. Cada novo troço liga dois vértices de grau ímpar e torna ambos pares. Com quatro vértices ímpares, bastam dois troços.

A partir do grafo apresentado, analisando o grau de cada vértice, temos:

• A — grau 2
• B — grau 3
• C — grau 1
• D — grau 2
• E — grau 1
• F — grau 3

Iniciar e terminar o circuito de manutenção numa mesma estação, percorrendo todos os troços, incluindo os novos, sem repetir nenhum deles, corresponde à definição de um circuito de Euler. Tal só será possível se todos os vértices tiverem grau par, o que não acontece neste caso, porque existem quatro vértices com grau ímpar: C e E (grau 1) e F e B (grau 3).

Assim, o número mínimo de troços pedonais a construir é 2, correspondendo a novas arestas no grafo que liguem os vértices de grau ímpar, para que passem a ter grau par e assim para que seja possível definir circuitos de Euler.

Opção: (B)

Os pais da Luísa fizeram um cruzeiro com o itinerário seguinte.

A Luísa, não podendo acompanhar os pais, tenciona visitar os mesmos locais, sem repetir nenhum deles, mas viajando em transportes públicos terrestres e marítimos. No seu planeamento, a Luísa pretende iniciar e terminar a viagem em Atenas, despendendo o menor tempo possível nas deslocações entre estes locais.

Na tabela seguinte, estão registadas as durações das viagens entre os vários locais a visitar, pesquisadas na Internet pela Luísa.

Para definir o seu percurso, a Luísa decide construir um grafo para modelar a situação, aplicando o método seguinte.

• Escolhe-se a aresta do grafo com menor peso, qualquer que ela seja.
• Escolhem-se, sucessivamente, as arestas com menor peso, garantindo que três arestas do grafo que está a ser definido não se encontram num mesmo vértice e não permitindo a formação de quaisquer percursos fechados que não incluam todos os vértices.

Poderá a Luísa visitar os locais pela mesma ordem seguida pelos pais?

Na sua resposta, apresente a ordenação das arestas selecionadas, um grafo semelhante ao que terá sido construído pela Luísa e um possível itinerário definido pela Luísa.

Como interpretar. É o algoritmo da aresta de menor peso. Depois compara-se o circuito obtido com o itinerário dos pais (A → I → V → M → R → S → A).

• I — aresta M–S, peso 2h30 (menor peso)
• II — aresta R–S, peso 2h40
• III — aresta A–M, peso 2h50
• IV — aresta A–V, peso 4h40
  (não se considera a aresta M–V, porque três arestas se iriam encontrar no vértice M)
  (não se considera a aresta S–V, porque três arestas se iriam encontrar no vértice S)
  (não se considera a aresta R–V, porque formaria um percurso fechado que não incluía todos os vértices)
  (não se considera a aresta A–S, porque três arestas se iriam encontrar no vértice A)
  (não se considera a aresta M–R, porque três arestas se iriam encontrar no vértice M)
• V — aresta I–V, peso 14h50
• VI — aresta I–R, peso 15h30

Desta forma, um percurso que a Luísa poderá ter definido, com início e fim na cidade de Atenas, é:

Atenas → Mykonos → Santorini → Rodes → Istambul → Volos → Atenas

(o mesmo percurso em sentido inverso também satisfaz as condições do enunciado)

Não: a Luísa não pode visitar os locais pela mesma ordem seguida pelos pais.

No recinto da Festa da Freguesia, existem 5 expositores, $L$, $M$, $N$, $O$ e $P$, que estão ligados por troços pedonais, como se pode observar na figura seguinte.

13.1. O presidente da junta de freguesia pretende visitar todos os expositores, sem repetir nenhum deles, iniciando a visita no expositor $L$.

Complete o texto seguinte, selecionando a opção adequada a cada espaço.

O presidente da junta de freguesia verificou que existem I percursos possíveis, mas, se quiser visitar o expositor $N$ depois de visitar o expositor $O$, apenas existe(m) II percurso(s) possível(is). Verificou também que não poderia visitar o expositor $M$ imediatamente a seguir ao expositor III e que, imediatamente a seguir a visitar o expositor $N$, poderia visitar o expositor IV.

13.2. No final de cada dia, o Rui verifica se todos os expositores, $L$, $M$, $N$, $O$ e $P$, e o restaurante, $R1$, ficam devidamente encerrados.

Na tabela seguinte, estão indicados os comprimentos, em metros, dos troços pedonais que ligam os diferentes espaços.

O Rui deve iniciar a verificação no restaurante, $R1$.

Para definir o percurso, utiliza o método seguinte.

• Seleciona o espaço a visitar em seguida, tendo em conta que:
  • deve ser o mais próximo possível;
  • se houver dois espaços à mesma distância, a seleção é aleatória.
• Procede como foi indicado no ponto anterior, não repetindo nenhum espaço, e termina depois de ter verificado todos os espaços.

Determine a distância, em metros, percorrida pelo Rui.

Na sua resposta, apresente um grafo ponderado que resulte da aplicação do método descrito e o percurso que respeita as condições definidas.

13.1 — Percursos possíveis a partir de L

Como interpretar. Constrói-se um diagrama em árvore a partir de $L$, cortando os ramos que não conseguem visitar os cinco expositores sem repetir.

Assim, vem que: existem 4 percursos possíveis; se quiser visitar $N$ depois de $O$, apenas existem 2 percursos possíveis; não poderia visitar $M$ imediatamente a seguir a $N$; e imediatamente a seguir a $N$ poderia visitar $O$.

I → c)  ·  II → b)  ·  III → a)  ·  IV → b)

13.2 — Distância percorrida pelo Rui

Como interpretar. Vizinho mais próximo a partir de $R1$, sem repetir espaços.

• I — $R1$–$P$ (214 m)
• II — $P$–$O$ (200 m)
• III — $O$–$M$ (255 m) (não se seleciona o troço $O$–$P$ porque $P$ já foi visitado)
• IV — $M$–$L$ (284 m) ($O$, $P$ e $R1$ já foram visitados)
• V — $L$–$N$ (401 m) (todos os restantes já foram visitados)

Desta forma, o percurso que respeita as condições definidas é $R1 \to P \to O \to M \to L \to N$.

$214 + 200 + 255 + 284 + 401 = 1354$

O Rui percorre 1354 metros.

Com o intuito de avaliar as condições de segurança de alguns estádios de futebol, uma comissão vai proceder à sua inspeção.

Na tabela seguinte, para cada um dos sete estádios passíveis de inspeção, estão indicados o país onde o estádio se localiza e a sua capacidade.

A comissão decidiu inspecionar apenas os estádios com capacidade superior a 85 000 espectadores.

De modo a definir um percurso, considerou a duração do voo entre os diferentes países que se apresentam na tabela seguinte.

O percurso será definido atendendo ao método seguinte:

• escolher o menor tempo de voo, qualquer que ele seja;
• escolher, sucessivamente, os menores tempos de voo, garantindo que não são selecionados mais de dois voos que partam do mesmo país ou que cheguem ao mesmo país, e terminar depois de serem selecionados todos os países onde se localizam os estádios a inspecionar.

Apresente o percurso a efetuar pela comissão, com início na África do Sul.

Na sua resposta, apresente um grafo que resulte da aplicação do algoritmo descrito e a ordem pela qual a comissão visitará os estádios.

Como interpretar. Primeiro eliminam-se os estádios com capacidade não superior a 85 000 (Austrália e França); depois aplica-se o algoritmo da aresta de menor peso ao grafo restante.

De acordo com as capacidades indicadas na tabela, e como a comissão decidiu inspecionar apenas os estádios com capacidade superior a 85 000 espectadores, podemos observar que não serão inspecionados os estádios da Austrália e da França.

• I — aresta Espanha–Inglaterra, duração 1h55 (menor tempo de voo)
• II — aresta Espanha–África do Sul, duração 10h25
• III — aresta Inglaterra–Coreia do Norte, duração 11h16
  (não se considera a aresta México–Inglaterra, porque já selecionámos uma aresta com Inglaterra)
  (não se considera a aresta África do Sul–Inglaterra, porque já selecionámos arestas com estes países)
  (não se considera a aresta Coreia do Norte–Espanha, porque já selecionámos arestas com estes países)
  (não se considera a aresta Espanha–México, porque já selecionámos duas arestas com Espanha)
• IV — aresta Coreia do Norte–México, duração 15h26

África do Sul → Espanha → Inglaterra → Coreia do Norte → México

No parque de campismo de Dujal, existem cinco ecopontos: A, B, C, D e E.

No final de cada dia, um funcionário recolhe o conteúdo dos ecopontos. De modo a tornar mais eficiente o seu trabalho, o funcionário definiu um itinerário, com início e fim no portão do parque (P), para a recolha do conteúdo dos cinco ecopontos.

O itinerário definido resultou de um grafo construído com o algoritmo seguinte:

• escolher a aresta do grafo com menor peso, qualquer que ela seja;
• escolher, sucessivamente, as arestas com menor peso, garantindo que três arestas do grafo que está a ser definido não se encontram num mesmo vértice e não permitindo que se formem quaisquer percursos fechados que não incluam todos os vértices.

As distâncias mínimas, em metros, entre cada dois ecopontos e entre o portão e cada um dos cinco ecopontos estão registadas na tabela seguinte.

Apresente um possível itinerário, definido pelo funcionário, com início e fim no portão.

Na sua resposta, apresente a ordenação das arestas selecionadas pelo algoritmo descrito e um grafo semelhante ao que terá sido construído pelo funcionário.

Como interpretar. Algoritmo da aresta de menor peso, com as duas restrições habituais: não juntar três arestas num vértice e não fechar o circuito antes de incluir todos os vértices.

• I — aresta A–B, distância 310 (menor comprimento)
• II — aresta A–D, distância 365
• III — aresta C–P, distância 366 (não se considera a aresta A–P, porque se encontrariam três arestas no vértice A)
• IV — aresta E–P, distância 380 (não se considera a aresta B–D, porque se formaria um percurso fechado sem todos os vértices B–D–A–B)
• V — aresta B–C, distância 550 (não se considera a aresta A–E, porque se encontrariam três arestas no vértice A)
• VI — aresta D–E, distância 605

Um itinerário possível é P – E – D – A – B – C – P (o mesmo itinerário em sentido inverso também satisfaz as condições).

Na agência de viagens Ir&Voltar, realizam-se, ao longo da primeira segunda-feira de cada trimestre, seis reuniões de trabalho, R1, R2, R3, R4, R5 e R6. Cada reunião tem um tema diferente e dura 90 minutos. De modo a planificar o dia das reuniões, é solicitada a cada funcionário a inscrição em uma ou mais reuniões, de acordo com os seus interesses. Para que todos os funcionários possam assistir às reuniões em que se inscrevem, é criado um horário com blocos de reuniões que possam ocorrer em simultâneo.

Na tabela seguinte, apresentam-se as inscrições dos funcionários em cada uma das reuniões a realizar na primeira segunda-feira do terceiro trimestre de 2022.

Com o propósito de determinar o tempo mínimo necessário para que as seis reuniões decorram nas condições definidas, a diretora de planeamento da Ir&Voltar começou por construir um grafo que modelava a situação.

Indique, em horas, o tempo mínimo necessário para que as seis reuniões se realizem nas condições definidas.

Na sua resposta, apresente um grafo que a diretora de planeamento pudesse ter construído e identifique a constituição de cada bloco de reuniões.

Como interpretar. Duas reuniões ficam ligadas quando há pelo menos um funcionário inscrito em ambas — nesse caso não podem ser simultâneas. Os blocos são conjuntos de vértices sem arestas entre si.

Assim, podemos verificar que a reunião R6 não pode ocorrer em simultâneo com qualquer outra; as reuniões R1, R4 e R5 podem decorrer em paralelo, porque não existem arestas entre os respetivos vértices, e, pela mesma razão, as restantes (R2 e R3) também podem ocorrer ao mesmo tempo.

Assim podemos definir os seguintes blocos de reuniões:

• R6
• R1, R4 e R5
• R2 e R3

Como cada reunião tem a duração de 90 minutos, e são necessários três conjuntos de reuniões, o tempo mínimo necessário é $3\times 90 = 270$ minutos, a que correspondem $\dfrac{270}{60} = 4{,}5$ horas.

São necessárias, no mínimo, 4,5 horas.

A rádio OnOfff é uma rádio local que transmite através da Internet, com recurso a tecnologia de transmissão de áudio e de vídeo em tempo real.

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 seguinte, apresenta-se uma planta em que estão representados os diferentes espaços onde funciona a rádio OnOfff: um pátio, uma receção e seis salas (S1, S2, S3, S4, S5 e S6).

O responsável pela calafetagem das portas pretende definir um percurso com início e fim no pátio, cruzando todas as portas e entrando em todos os espaços, sem cruzar nenhuma porta mais de uma vez.

Justifique se é possível definir um percurso nas condições indicadas.

Na sua resposta, apresente um grafo que modele a situação descrita.

Como interpretar. Cada espaço é um vértice, cada porta uma aresta. O percurso pedido é um circuito de Euler.

• Pátio — grau 2
• Receção — grau 4
• Sala 1 — grau 2
• Sala 2 — grau 3
• Sala 3 — grau 2
• Sala 4 — grau 3
• Sala 5 — grau 4
• Sala 6 — grau 2

Para definir um percurso com início e fim no pátio, cruzando todas as portas e entrando em todos os espaços, sem cruzar nenhuma porta mais de uma vez, seria necessário definir um circuito de Euler, o que apenas seria possível se todos os vértices tivessem grau par.

Não é possível: existem vértices de grau ímpar (os correspondentes às salas 2 e 4).

Num campus universitário, pretende-se instalar uma iluminação decorativa, constituída por um fio de luzes suspenso entre seis edifícios, E1, E2, E3, E4, E5 e E6.

A tabela seguinte apresenta o comprimento previsto, em metros, do fio de luzes que seria necessário instalar entre cada par de edifícios.

De modo a minimizar o custo da instalação da iluminação decorativa, construiu-se um grafo que resulta do método que a seguir se descreve.

• Escolhe-se, ao acaso, um dos seis edifícios e, de seguida, de entre os restantes, seleciona-se aquele que, por se encontrar a uma menor distância do primeiro, implique um menor comprimento do fio de luzes previsto.
• Seleciona-se outro edifício que ainda não tenha sido escolhido e que, por se encontrar a uma menor distância dos edifícios anteriormente escolhidos, implique um menor comprimento do fio de luzes previsto.
• Repete-se o ponto anterior até todos os edifícios terem sido selecionados.

Admita que a instalação da iluminação decorativa terá um custo de 3,5 euros por cada metro de fio de luzes previsto.

Determine o custo total desta instalação.

Na sua resposta, apresente um grafo ponderado que resulte da aplicação do método descrito e o comprimento mínimo previsto, em metros, do fio de luzes a instalar.

Como interpretar. É a construção de uma árvore geradora mínima: em cada passo junta-se o edifício mais próximo do conjunto já ligado.

Escolhendo inicialmente o edifício E1:

• I — aresta E1–E6, comprimento 560
• II — aresta E6–E3, comprimento 300
• III — aresta E3–E4, comprimento 810 (não se considera a aresta E3–E6, porque o edifício E6 já foi escolhido)
• IV — aresta E4–E2, comprimento 320
• V — aresta E2–E5, comprimento 340 (não se considera a aresta E2–E4, porque o edifício E4 já foi escolhido)

$560 + 300 + 810 + 320 + 340 = 2330 \text{ m}$

$2330 \times 3{,}5 = 8155 \text{ euros}$

O custo total da instalação é 8155 €.

A ParaPagar pretende renovar a rede de cabo de fibra ótica em algumas das ligações existentes entre seis postos de comunicação, $P1$, $P2$, $P3$, $P4$, $P5$ e $P6$.

Na figura seguinte, apresenta-se um esquema simplificado dessas ligações, no qual se indica, junto de cada segmento de reta, o comprimento, em quilómetros, de cada ligação.

Com vista à minimização de custos, optou-se por começar a renovação no posto de comunicação $P4$ e aplicar o método que a seguir se descreve.

• Seleciona-se o posto seguinte, tendo em conta que:
  • deverá corresponder ao posto mais próximo;
  • se houver dois postos à mesma distância, a seleção é aleatória.
• Procede-se como foi indicado no ponto anterior, partindo do último posto selecionado, não se repetindo nenhum e terminando depois de todos os postos serem incluídos.

Determine a quantidade mínima, em quilómetros, de cabo de fibra ótica a renovar.

Na sua resposta, apresente um grafo que resulte do método descrito e que permita identificar as ligações a renovar.

Como interpretar. Vizinho mais próximo a partir de $P4$, sem repetir postos.

• I — posto $P4$ (posto inicial)
• II — posto $P6$, distância 180
• III — posto $P5$, distância 185
• IV — posto $P3$, distância 355
• V — posto $P2$, distância 95
• VI — posto $P1$, distância 185

$180 + 185 + 355 + 95 + 185 = 1000 \text{ km}$

A quantidade mínima de cabo a renovar é 1000 km.

Em cada uma das opções, A, B, C e D, apresenta-se um esquema, sob a forma de grafo, que representa um jardim. Em cada grafo, os vé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 não estavam ligados. Graças a este novo caminho, é agora possível iniciar e terminar um percurso num mesmo canteiro, percorrendo todos os caminhos, incluindo o novo, sem repetir nenhum deles.

Qual das opções representa o jardim onde trabalha o Rui, antes da construção do novo caminho?

Como interpretar. Depois de acrescentar uma aresta, todos os vértices têm de ficar com grau par. Isso só acontece se o grafo tiver exatamente dois vértices de grau ímpar e esses dois ainda não estiverem ligados entre si.

Para que seja possível iniciar e terminar um percurso num mesmo canteiro, percorrendo todos os caminhos, incluindo o novo, sem repetir nenhum deles, tem que ser possível definir um circuito euleriano, o que só acontece se todos os vértices tiverem grau par.

Assim, o único grafo que permite criar um circuito acrescentando uma única aresta, ligando vértices ainda não ligados, é o grafo da opção (C), acrescentando a aresta que liga os vértices A e F, tornando todos os vértices de grau par.

Na opção (A) acrescentar uma única aresta não permite que todos os vértices tenham grau par; na opção (B) acrescentar uma aresta a ligar os vértices de grau ímpar cria dois circuitos independentes; e na opção (D) os vértices de grau ímpar já estão ligados por uma aresta.

Opção: (C)

No parque municipal de Avelares, vão ser instalados oito bebedouros em locais previamente selecionados, designados por A, B, C, D, E, F, G e H, que serão interligados através de uma canalização.

Na tabela seguinte, apresenta-se o comprimento, em metros, das ligações que é possível estabelecer entre os diversos locais.

De modo a minimizar o custo da canalização, construiu-se um grafo, aplicando o método que a seguir se descreve.

• Seleciona-se a ligação de menor comprimento (se houver mais do que uma, escolhe-se ao acaso uma delas).
• Em seguida, seleciona-se, de entre as ligações restantes, a de menor comprimento, desde que esta não leve à formação de um ciclo.
• Termina-se quando todos os locais onde serão instalados bebedouros estiverem ligados.

Determine o comprimento total da canalização.

Na sua resposta, apresente o grafo que resulta da aplicação do método descrito.

Como interpretar. É o algoritmo de Kruskal: escolhem-se as arestas mais curtas que não formem ciclo, até ligar os oito locais (7 arestas).

• I — aresta F–G, comprimento 412 (menor comprimento)
• II — aresta B–E, comprimento 446
• III — aresta A–B, comprimento 500
• IV — aresta A–G, comprimento 502
• V — aresta B–C, comprimento 505
• VI — aresta D–G, comprimento 721 (não se consideram as arestas A–C e E–F, porque formam ciclos)
• VII — aresta D–H, comprimento 952 (não se consideram as arestas C–G, B–G, A–E e C–E porque formam ciclos)

$412 + 446 + 500 + 502 + 505 + 721 + 952 = 4038 \text{ m}$

O comprimento total da canalização é 4038 metros.

A Elsa, que em 2018 fez um Interrail, relatou à Maria a sua viagem, explicando-lhe também algumas dificuldades na sua organizaçã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 Áustria, a França, a Itália e a Suíça e que, em cada país, iriam apenas a uma cidade.

Na tabela seguinte, apresentam-se as distâncias, em quilómetros, entre as cidades que o grupo considerou mais atrativas e os países a que pertencem.

Os amigos acordaram que o percurso a realizar seria definido partindo de um grafo no qual duas cidades são interligadas se nã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 três arestas do percurso que está a ser definido não se encontram num mesmo vértice e não permitindo que se fechem percursos sem que todos os vé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 ordenação das arestas selecionadas pelo algoritmo descrito, um grafo que resulte da aplicação do algoritmo e um percurso que o grupo de amigos da Elsa poderá ter definido.

Como interpretar. Além das duas restrições habituais, há uma terceira: como se visita uma só cidade por país, não se podem ligar duas cidades do mesmo país nem incluir ambas no percurso.

• I — aresta Munique–Salzburgo, peso 140 (menor peso; não se considera a aresta Milão–Veneza, porque pertencem ao mesmo país)
• II — aresta Milão–Zurique, peso 280
• III — aresta Munique–Zurique, peso 340
  (não se considera Munique–Viena, porque iria interligar Salzburgo e Viena, pertencentes ao mesmo país)
  (não se considera Salzburgo–Zurique, porque três arestas se iriam ligar no vértice Zurique)
  (não se considera Salzburgo–Veneza, porque iria interligar Veneza e Milão, pertencentes ao mesmo país)
  (não se considera Munique–Milão, porque três arestas se iriam ligar no vértice Munique)
  (não se considera Munique–Veneza, porque três arestas se iriam ligar no vértice Munique)
  (não se considera Salzburgo–Milão, porque iria fechar um percurso sem incluir o vértice Paris)
  (não se considera Veneza–Zurique, porque três arestas se iriam ligar no vértice Zurique)
  (não se considera Viena–Veneza, porque já foram selecionados vértices destes dois países)
  (não se considera Paris–Zurique, porque três arestas se iriam ligar no vértice Zurique)
  (não se considera Viena–Zurique, porque três arestas se iriam ligar no vértice Zurique)
  (não se considera Munique–Paris, porque três arestas se iriam ligar no vértice Munique)
• IV — aresta Paris–Milão, peso 850 (não se considera Viena–Milão, porque três arestas se iriam ligar no vértice Milão)
• V — aresta Salzburgo–Paris, peso 980

Paris → Milão → Zurique → Munique → Salzburgo → Paris (o mesmo percurso em sentido inverso também satisfaz as condições).

Num determinado verão, decorreram os festivais F1, F2, F3, F4, F5 e F6. Estes festivais realizaram-se ao fim de semana e tiveram, cada um, a duração de dois dias (sá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.

Indique o número mínimo de fins de semana em que os festivais podem ter decorrido.

Na sua resposta, apresente um grafo que modele a situação descrita e identifique os festivais que decorreram em simultâneo.

Como interpretar. Dois festivais ficam ligados quando algum jovem assistiu a ambos — não podem ser no mesmo fim de semana. Procuram-se pares de vértices sem aresta entre si.

Assim podemos verificar que a inexistência de arestas entre:

• os vértices F1 e F6
• os vértices F3 e F4
• os vértices F2 e F5

evidencia que estes 3 pares de festivais podem ter decorrido em simultâneo.

O número mínimo de fins de semana é 3.

Numa das alas do Centro Comercial Futuro existem 8 pontos de vigilância, designados A, B, C, D, E, F, G e H, nos quais estão instaladas câmaras de vigilância.

Pretende-se encontrar a solução mais económica para a substituição das ligações internas entre as câmaras.

A tabela seguinte apresenta o comprimento, em metros, das ligações existentes entre os pontos de vigilância.

De modo a minimizar os custos da intervenção, construiu-se um grafo, adotando-se o procedimento seguinte:

• seleciona-se a ligação de menor comprimento (se houver mais do que uma, escolhe-se ao acaso uma delas);
• em seguida, seleciona-se, de entre as ligações restantes, a de menor comprimento, desde que esta não leve à formação de um ciclo;
• termina-se quando todos os pontos de vigilância pertencerem a alguma das ligações selecionadas no grafo.

Admita que a substituição de cada metro de ligação interna tem o custo de 12 euros.

Determine o custo total da substituição.

Na sua resposta, apresente o grafo que resulta da aplicação do método descrito.

Como interpretar. Kruskal: sete arestas (oito vértices menos um), sempre as mais curtas que não fechem ciclo.

• I — aresta B–F, comprimento 14 (menor comprimento)
• II — aresta C–F, comprimento 15
• III — aresta E–F, comprimento 16
• IV — aresta D–G, comprimento 18 (não se considera a aresta B–E, porque forma um ciclo)
• V — aresta A–D, comprimento 20
• VI — aresta D–E, comprimento 22 (não se considera a aresta A–B, porque forma um ciclo; não se considera a aresta B–C, porque forma um ciclo)
• VII — aresta E–H, comprimento 30

$14 + 15 + 16 + 18 + 20 + 22 + 30 = 135 \text{ m}$

$135 \times 12 = 1620 \text{ euros}$

O custo total da substituição é 1620 €.

O Clube de Colecionadores possui um espaço próprio para exposições.

Na figura seguinte, apresenta-se uma planta simplificada do referido espaço, que é composto por um Á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 Á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 não podia ser posto em prática, e como o espaço será alvo de remodelação, o presidente decidiu que uma das intervenções a levar a cabo seria eliminar uma das portas existentes ou acrescentar uma nova porta para viabilizar o seu objetivo.

Indique, justificando, qual terá sido a intervençã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 situação descrita.

Como interpretar. O objetivo é um circuito de Euler. Com exatamente dois vértices de grau ímpar, acrescentar uma porta entre eles torna ambos pares — e resolve o problema.

• Átrio — grau 4
• Sala 1 — grau 2
• Sala 2 — grau 2
• Sala 3 — grau 2
• Sala 4 — grau 3
• Sala 5 — grau 3
• Sala 6 — grau 2

O presidente do Clube pretendia definir um percurso, com início e fim no Átrio, cruzando todas as portas e entrando em todas as salas, sem cruzar nenhuma porta mais de uma vez, o que corresponde à definição de um circuito de Euler. Tal só será possível se todos os vértices tiverem grau par, o que não acontece neste caso, porque existem dois vértices com grau ímpar: S4 (grau 3) e S5 (grau 3).

O presidente terá acrescentado uma porta entre as salas 4 e 5: assim, S4 e S5 passam a ter grau 4, todos os vértices ficam com grau par e passa a ser possível definir circuitos de Euler.

Uma empresa foi convidada a participar num certame. Para expor os seus produtos, terá de montar uma banca, sendo necessário levar a cabo diversas tarefas. O diretor de operações da empresa fez a lista dessas tarefas, desde que se inicia a montagem da banca até tudo estar concluído.

A tabela seguinte apresenta o tempo necessário para executar cada tarefa (Duração), em minutos, e, quando é o caso, quais as tarefas que devem ser previamente concluídas (Tarefas precedentes).

Determine o tempo mínimo necessário, em minutos, para executar todas as tarefas que compõem a montagem da banca.

Na sua resposta, apresente um grafo que modele a situação descrita.

Como interpretar. O tempo mínimo é o da sequência mais longa de tarefas encadeadas: as tarefas não encadeadas decorrem em paralelo.

Assim podemos verificar que podem ocorrer quatro sequências de tarefas:

• T1 → T2 → T4 → T6, com um tempo associado de $3+10+12+5 = 30$ min
• T1 → T2 → T5 → T6, com um tempo associado de $3+10+15+5 = 33$ min
• T1 → T3 → T4 → T6, com um tempo associado de $3+15+12+5 = 35$ min
• T1 → T3 → T5 → T6, com um tempo associado de $3+15+15+5 = 38$ min

Como, em cada uma das sequências de tarefas, as tarefas não referidas podem decorrer simultaneamente, o tempo mínimo necessário corresponde ao da sequência com maior duração.

O tempo mínimo é 38 minutos.

Admita que, no distrito de Castelo Branco, se pretende adotar uma nova tecnologia na iluminação de estradas. Na tabela seguinte, apresenta-se a extensão, em quilómetros, das estradas onde se poderá adotar esta tecnologia.

Não sendo viável, por razões económicas, adotar esta tecnologia em todas as estradas, decidiu-se, numa fase inicial, proceder à sua adoção somente em algumas delas.

Para a seleção das estradas recorreu-se ao algoritmo seguinte.

• Constrói-se um grafo, cujos vértices representam as localidades, selecionando-se, sucessivamente, as menores extensões de estradas entre elas, tendo-se em conta que:
  • se a aresta a que corresponde a extensão selecionada levar à formação de um circuito, essa aresta não deve ser considerada;
  • caso contrário, essa aresta deve ser considerada.
• O algoritmo termina quando, no grafo, o número de arestas é igual ao número de vértices menos um.

Determine, nestas condições, o número de quilómetros de estrada que o projeto de iluminação deve contemplar na sua fase inicial. Na sua resposta, apresente o grafo que resulta da aplicação do algoritmo, indicando o peso de cada aresta.

Como interpretar. Kruskal com cinco vértices: para em quatro arestas.

• I — aresta BL, ponderação 39
• II — aresta LA, ponderação 51 (não se considera a aresta BA, porque forma um circuito)
• III — aresta BO, ponderação 68 (não se considera a aresta LO, porque forma um circuito)
• IV — aresta OT, ponderação 112

Observando o grafo, temos que o número de vértices é 5, o número de arestas é $4 = 5-1$, e a ponderação total é:

$39 + 51 + 68 + 112 = 270$

O projeto deve contemplar 270 km de estrada na fase inicial.

Na preparação da sua digressão pelas ilhas do arquipélago dos Açores, a companhia de teatro optou por apresentar a peça somente nas ilhas com, pelo menos, 6000 habitantes.

Na tabela seguinte, está registado o número de habitantes em cada uma das ilhas.

Fonte: Censos 2011

De modo a minimizar o custo das deslocações aéreas, foram analisados os preços das ligações aéreas diretas, existentes entre as diferentes ilhas, a que a companhia de teatro poderá recorrer.

Na figura seguinte, estão indicadas essas ligações aéreas diretas entre as ilhas do arquipélago dos Açores e o respetivo custo, por pessoa.

A companhia de teatro optou por começar a digressão na ilha do Faial, pretendendo terminá-la noutra ilha.

De modo a minimizar o custo das viagens, aplicou o método que a seguir se descreve.

• Seleciona-se a ilha seguinte, tendo em conta que:
  • deverá corresponder à viagem de preço mais baixo;
  • se houver duas ilhas para as quais seja possível viajar pelo mesmo preço, a seleção é aleatória.
• Procede-se como foi indicado no ponto anterior, não se repetindo nenhuma ilha e terminando depois de serem visitadas todas as ilhas incluídas na digressão.

Determine o custo mínimo em deslocações aéreas de cada elemento da companhia de teatro na sua digressão pelo arquipélago dos Açores, respeitando as condições definidas.

Na sua resposta, apresente um grafo ponderado que resulte da aplicação do método descrito e a ordem pela qual a companhia de teatro visitará as ilhas.

Como interpretar. Excluem-se as ilhas com menos de 6000 habitantes (Santa Maria, Graciosa, Flores e Corvo) e aplica-se o vizinho mais próximo a partir do Faial.

• Faial – Terceira (86 €)
• Terceira – São Jorge (61 €)
• São Jorge – São Miguel (92 €)
• São Miguel – Pico (92 €)

$86 + 61 + 92 + 92 = 331 \text{ €}$

O custo mínimo é de 331 € por elemento da companhia.

Mariana decidiu viajar até Praga e, a partir daí, visitar outras capitais europeias, regressando a essa primeira cidade no final da visita.

As capitais que pretende visitar, além de Praga, são Berlim, Bratislava, Varsóvia e Viena.

Para planear as suas férias, Mariana utilizou a tabela seguinte, que apresenta as distâncias, em quilómetros, entre as referidas capitais.

Com base na informação apresentada e num mapa da Europa semelhante ao que se apresenta na figura seguinte, Mariana construiu um grafo em que duas capitais são interligadas, desde que os países a que pertencem façam fronteira entre si.

O seu percurso será 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 três arestas do percurso que está a ser definido não se encontram num mesmo vértice e não permitindo que se fechem percursos sem que todos os vértices sejam incluídos.

Apresente um percurso possível, definido por Mariana, com início e fim em Praga.

Na sua resposta, apresente um grafo semelhante ao que Mariana construiu, a ordenação das arestas selecionadas pelo algoritmo descrito e um percurso que Mariana poderá ter definido.

Como interpretar. Só se ligam capitais cujos países fazem fronteira (é o que o mapa serve para determinar); depois aplica-se o algoritmo da aresta de menor peso.

• I — aresta Bratislava–Viena, ponderação 80 (a aresta com menor peso)
• II — aresta Praga–Viena, ponderação 305
• III — aresta Berlim–Praga, ponderação 349
• IV — aresta Berlim–Varsóvia, ponderação 572
• V — aresta Bratislava–Varsóvia, ponderação 673

(não se considera a aresta Bratislava–Praga, porque fecharia um percurso sem incluir o vértice Berlim, nem a aresta Berlim–Varsóvia... — mais precisamente, não se considera nenhuma aresta que feche o percurso antes de todos os vértices estarem incluídos)

Praga → Berlim → Varsóvia → Bratislava → Viena → Praga (o mesmo percurso em sentido inverso também satisfaz as condições).

Na figura seguinte, está representada a planta do recinto de um dos cinemas onde decorre o CineJov.

O recinto é composto por cinco salas, numeradas de 1 a 5, e por uma Zona Exterior, num total de seis espaços. Todas as salas têm um único acesso à Zona Exterior e todas têm comunicação com, pelo menos, uma outra sala, como se observa na figura seguinte.

No final do dia, um funcionário faz uma inspeção completa ao recinto, respeitando as seguintes condições:

• passa por todas as portas;
• começa e termina na Sala 1.

Para realizar esta inspeção, o funcionário pode sair das diferentes áreas do recinto e nelas voltar a entrar as vezes que considerar necessárias. Com base na sua experiência, afirma que é impossível fazer a inspeção completa ao recinto, passando uma única vez por cada uma das portas.

Justifique que o funcionário tem razão e identifique a porta pela qual terá necessariamente de passar duas vezes.

Na sua resposta, apresente um grafo que modele a situação descrita.

Como interpretar. A porta a repetir é justamente a que liga os dois vértices de grau ímpar: retirando-a, todos ficam com grau par.

• Sala 1 — grau 3
• Sala 2 — grau 2
• Sala 3 — grau 2
• Sala 4 — grau 2
• Sala 5 — grau 4
• Zona Exterior — grau 5

Como se tentou encontrar um percurso que começa e termina no mesmo vértice (Sala 1), e utiliza cada aresta (porta) uma única vez, estamos a tentar encontrar um circuito de Euler, o que só é possível se todos os vértices tiverem grau par, o que não acontece neste caso, porque existem dois vértices com grau ímpar: Sala 1 (grau 3) e Zona Exterior (grau 5). Ou seja, o funcionário tem razão.

A porta a percorrer duas vezes é a que liga a Sala 1 à Zona Exterior.

A associação de estudantes está a preparar um pedipaper que engloba seis postos de controlo, designados por $C_1$, $C_2$, $C_3$, $C_4$, $C_5$ e $C_6$.

Na tabela seguinte, estão indicadas as distâncias, em metros, entre diferentes postos de controlo.

A associação de estudantes decidiu que o pedipaper se iniciaria no posto de controlo $C_5$ e terminaria num outro posto de controlo.

Além disso, para definir o percurso, a associação de estudantes optou por utilizar o método seguinte.

• Seleciona-se o posto de controlo seguinte, tendo em conta que:
  • deve ser o mais próximo possível;
  • se houver dois postos à mesma distância, a seleção é aleatória.
• Procede-se como foi indicado no ponto anterior, não se repetindo nenhum posto de controlo, e terminando depois de serem visitados todos os postos de controlo.

Determine o comprimento do percurso, respeitando as condições definidas pela associação de estudantes.

Na sua resposta, apresente um grafo ponderado que modele a situação descrita na tabela anterior e a ordem de visita dos postos de controlo.

Como interpretar. Vizinho mais próximo a partir de $C_5$; o percurso é aberto (não regressa a $C_5$).

Iniciando o pedipaper no posto de controlo $C_5$ e aplicando o algoritmo, temos a seguinte sequência de visita aos postos de controlo:

$C_5 \to C_1 \to C_2 \to C_3 \to C_6 \to C_4$

$302 + 160 + 253 + 267 + 294 = 1276 \text{ m}$

O comprimento do percurso é 1276 metros.

As seis diversões mais procuradas da zona Studiospeed estão representadas na figura seguinte pelas letras D1, D2, D3, D4, D5 e D6.

As linhas representam as ligações existentes entre essas diversões. O comprimento de cada ligação está indicado junto da linha que a representa.

Uma empresa de eletricidade pretende renovar a rede de cabos elétricos, aproveitando algumas destas ligações. De modo a minimizar a quantidade de cabo utilizado, aplica-se o método que a seguir se descreve.

• Escolhe-se, ao acaso, uma das seis diversões e, de entre as ligações a essa diversão, seleciona-se a ligação de menor comprimento.
• Seleciona-se a ligação de menor comprimento de entre as ligações a qualquer uma das duas diversões escolhidas para uma diversão ainda não selecionada.
• Seleciona-se a ligação de menor comprimento de entre as ligações a qualquer uma das diversões escolhidas para uma diversão ainda não selecionada.
• Repete-se o ponto anterior até todas as diversões terem sido selecionadas.

Determine a quantidade mínima, em metros, de cabo elétrico que é necessário instalar para que as seis diversões recebam energia elétrica.

Na sua resposta, apresente um grafo que resulte da aplicação do método descrito e que permita identificar as ligações utilizadas, e a quantidade mínima, em metros, de cabo elétrico que é necessário instalar.

Como interpretar. É o algoritmo de Prim: parte-se de um vértice e junta-se sempre a ligação mais curta que alcança uma diversão ainda não selecionada.

• I — diversão D1
• II — aresta D1–D2, ponderação 360
• III — aresta D2–D3, ponderação 302
• IV — aresta D2–D6, ponderação 308
• V — aresta D3–D4, ponderação 480
• VI — aresta D4–D5, ponderação 286

(a seleção de outra diversão na fase inicial do algoritmo não altera a árvore abrangente mínima obtida)

$360 + 302 + 308 + 480 + 286 = 1736 \text{ m}$

São necessários, no mínimo, 1736 metros de cabo elétrico.

As instalações do TPT estão distribuídas por cinco edifícios: E1, E2, E3, E4 e E5.

As distâncias mínimas, em metros, entre cada dois edifícios estão registadas na tabela seguinte.

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, começou por ordenar, de forma crescente, as distâ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 método.

• Representou a primeira aresta do grafo correspondente à menor das distâncias entre os edifícios.
• Representou as restantes arestas, selecionando sucessivamente as menores distâncias, garantindo que três delas não se encontrassem num mesmo vértice e que não se fechassem percursos sem que todos os vértices estivessem incluídos.

Apresente um possível percurso final definido pelo estafeta, com início e fim no edifício principal (E3).

Na sua resposta, apresente a ordenação, de forma crescente, das distâncias registadas na tabela anterior e um grafo semelhante ao que terá sido construído pelo estafeta.

Como interpretar. Algoritmo da aresta de menor peso para obter um circuito de Hamilton pelos cinco edifícios.

Ordenando as distâncias entre os cinco edifícios registadas na tabela, temos:

$109_{\,E3-E5} \lt 125_{\,E1-E4} \lt 151_{\,E2-E3} \lt 166_{\,E1-E2} \lt 169_{\,E2-E5} \lt 206_{\,E1-E3} \lt 207_{\,E3-E4} \lt 264_{\,E2-E4} \lt 287_{\,E1-E5} \lt 309_{\,E4-E5}$

• I — aresta E3–E5
• II — aresta E1–E4
• III — aresta E2–E3
• IV — aresta E1–E2
  (não se considera a aresta E2–E5, porque fecharia um percurso sem que todos os vértices estivessem incluídos)
  (não se consideram as arestas E1–E3 e E3–E4, porque se encontrariam três arestas no vértice E3)
  (não se consideram as arestas E2–E4 e E1–E5, porque se encontrariam três arestas nos vértices E2 e E1, respetivamente)
• V — aresta E4–E5

Um percurso possível é E3 → E5 → E4 → E1 → E2 → E3.

No Encontro Desportivo Internacional, existem atletas que estão inscritos em mais do que uma modalidade. Para que todos consigam realizar um treino de adaptação ao estádio onde se irão realizar as provas, vai ser criado um horário com blocos de utilização das instalações. De cada bloco deverão fazer parte as modalidades nas quais não haja atletas inscritos simultaneamente.

A constituição de cada bloco será definida considerando os dados da tabela seguinte, na qual o símbolo ✗ indica as modalidades que podem ser inseridas num mesmo bloco.

Determine, tendo em conta as condições dadas, o número mínimo de blocos que será necessário constituir, de modo que todos os atletas possam realizar o treino de adaptação em todas as modalidades em que estão inscritos.

Na sua resposta, apresente um grafo que modele a situação e identifique as modalidades que constituem cada um dos blocos.

Como interpretar. Atenção ao sentido da tabela: aqui a aresta representa compatibilidade (modalidades que podem ficar no mesmo bloco), ao contrário dos exercícios de escalonamento anteriores.

Assim temos que devem ser construídos blocos para as seguintes modalidades:

• modalidade E (não é compatível com qualquer outra);
• modalidades B e G;
• modalidades H e D;
• modalidades A, C e F.

É necessário constituir, no mínimo, quatro blocos.

Na figura seguinte, apresenta-se um mapa do recinto do MaréFest no qual estão representadas as infraestruturas $I_1$, $I_2$, $I_3$, $I_4$, $I_5$, $I_6$ e $I_7$, ligadas entre si através de troços pedonais.

Considera-se troço pedonal a ligação entre duas infraestruturas adjacentes, isto é, o percurso que pode ser usado para ir de uma dessas infraestruturas à outra sem passar por mais nenhuma.

Um vigilante do recinto pretende vistoriar as condições de segurança de todos os troços pedonais, iniciando e terminando a sua vistoria junto da mesma infraestrutura. Observando o mapa, conclui que não será possível, nestas condições, percorrer todos os troços pedonais sem repetir nenhum.

Apresente uma sugestão de um único troço pedonal a repetir pelo vigilante, que lhe permita percorrer todos os troços, iniciando e terminando a vistoria junto da mesma infraestrutura, sendo o número de troços a percorrer o menor possível.

Na sua resposta, apresente um grafo que modele o mapa do recinto com as infraestruturas, de $I_1$ a $I_7$, e com os troços pedonais, e uma justificação da veracidade da conclusão do vigilante.

Como interpretar. Com dois vértices de grau ímpar, duplicar a aresta que os une torna todos os graus pares — e é a repetição mínima.

Determinando o grau de cada vértice, temos:

Vértices	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$
Grau	4	2	4	2	3	2	3

Desta forma, como existem dois vértices com grau ímpar (os vértices $I_5$ e $I_7$), o grafo não admite circuitos de Euler, ou seja, circuitos que percorram todas as arestas, percorrendo cada aresta uma única vez. No contexto da situação descrita significa que não é possível percorrer todos os troços pedonais sem repetir nenhum iniciando e terminando a vistoria junto da mesma infraestrutura, ou seja, a conclusão do vigilante é verdadeira.

O troço a repetir é o que une as infraestruturas $I_5$ e $I_7$: duplicando essa aresta, todos os vértices ficam com grau par e passa a existir um circuito de Euler.

A companhia de aviação ASA5 opera nos aeroportos nacionais.

O diretor de operações de terra da companhia de aviação ASA5 fez uma lista das tarefas efetuadas entre a aterragem de um certo avião e uma nova descolagem.

A tabela seguinte apresenta o tempo necessário para concretizar cada tarefa (Duração) e, quando existem, as tarefas que devem ser previamente concluídas (Tarefa(s) precedente(s)).

Há tarefas que se podem realizar em simultâneo, por exemplo, enquanto decorre o Desembarque de passageiros (DP), pode estar a realizar-se a Descarga de bagagem (DB).

Determine o tempo mínimo, em minutos, necessário para realizar todas as tarefas que antecedem uma nova descolagem (D) desse avião da ASA5, nas condições previstas na tabela anterior.

Na sua resposta, apresente um grafo que represente a situação, incluindo o significado dos elementos (arestas e vértices) que o constituem, e as possíveis sequências de concretização das tarefas e a respetiva duração.

Como interpretar. O tempo mínimo é o da sequência mais longa; as restantes decorrem em paralelo.

Assim podemos verificar que podem ocorrer quatro sequências de tarefas:

• DP → LC → RA → D, com um tempo associado de $14+12+4 = 30$ minutos
• DP → EP → D, com um tempo associado de $14+20 = 34$ minutos
• DB → EP → D, com um tempo associado de $2+20 = 22$ minutos
• DB → CB → D, com um tempo associado de $2+16 = 18$ minutos

O tempo mínimo é 34 minutos.

O Sr. Pereira é motorista da empresa PTM.

Num certo dia, o Sr. Pereira tem de passar nas cidades A, B, D e E, não necessariamente por esta ordem, partindo da sede da empresa, localizada na cidade C, e regressando ao local de partida. Nesse percurso, não pode passar pela mesma cidade mais do que uma vez.

Na tabela seguinte, estão assinaladas com o símbolo ✓ as ligações rodoviárias existentes entre as cidades. O símbolo ✗ significa que não existe ligação rodoviária entre as cidades.

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

• alternativa 1: passar pela cidade A e só 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 razão? Justifique, apresentando um grafo que modele a situação descrita, e identifique todos os percursos possíveis para cada uma das alternativas.

Como interpretar. Procuram-se todos os circuitos de Hamilton com início e fim em C, e depois filtram-se os que respeitam cada alternativa.

Identificando todos os percursos possíveis em cada alternativa, temos:

• alternativa 1:
  • C → B → A → E → D → C
  • C → D → A → E → B → C
• alternativa 2:
  • C → D → E → A → B → C
  • C → D → A → E → B → C

Como em ambas as alternativas é possível definir o mesmo número de percursos (dois percursos em cada alternativa), o Sr. Pereira não tem razão.

Uma agência de viagens, sediada no concelho de Avelares, organiza e vende, através da Internet, percursos de autocarro entre várias cidades europeias.

Para organizar um percurso que passe por Amesterdão, Berlim, Munique, Paris e Viena, um funcionário da agência começou por registar, na tabela seguinte, as distâncias mínimas, em quilómetros, entre cada duas cidades.

De forma a minimizar os custos operacionais, o funcionário definiu, atravé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 três arestas do percurso que está a ser definido não se encontram num mesmo vértice e não permitindo que se fechem percursos sem que todos os vértices sejam incluídos;
• apresentar um percurso pretendido conforme o vértice de partida escolhido.

Apresente um percurso possível, com início e fim em Amesterdão, de acordo com o procedimento utilizado pelo funcionário da agência.

Na sua resposta, apresente o grafo usado, indicando os pesos de cada aresta, e um percurso que o funcionário poderá ter definido.

Como interpretar. Algoritmo da aresta de menor peso, com as duas restrições habituais.

• I — aresta M–V (435 km)
• II — aresta A–P (501 km)
• III — aresta B–M (604 km)
• IV — aresta A–B (663 km)
  (não se considera a aresta B–V, porque se encontrariam três arestas no vértice B)
  (não se consideram as arestas A–M e M–P, porque se encontrariam três arestas no vértice M)
  (não se considera a aresta B–P, porque se encontrariam três arestas no vértice B)
  (não se considera a aresta A–V, porque se encontrariam três arestas no vértice A)
• V — aresta P–V (1236 km)

A → P → V → M → B → A (o mesmo percurso em sentido inverso também satisfaz as condições).

O Francisco reside na vivenda A, em Penha Alta, e dá apoio domiciliário a residentes em quatro vivendas, B, C, D e E.

Na tabela seguinte, estão registadas as distâncias mínimas, em metros, entre as cinco vivendas: A, B, C, D e E.

De modo a determinar a distância mínima a percorrer na visita aos residentes a quem dá apoio domiciliário, o Francisco aplica o algoritmo seguinte.

• Define-se A como ponto de partida.
• Seleciona-se a vivenda mais próxima e estabelece-se a ligação entre as duas tendo em conta que, se houver duas vivendas à mesma distância, a escolha é aleatória. Essa ligação é o caminho a percorrer entre as duas vivendas.
• Procede-se como foi indicado no ponto anterior, nã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 aleatória, quando existem duas vivendas à mesma distância, pode levar o Francisco a percorrer uma distância maior do que seria necessário para visitar os residentes a quem dá apoio domiciliário.

Como interpretar. A partir de A há um empate: B e D estão ambos a 100 m. Basta desenvolver os dois circuitos e comparar as distâncias totais.

Assim, temos que a distância total de cada percurso é:

• Percurso A → B → C → E → D → A: $100+100+140+110+100 = 550$ metros
• Percurso A → D → E → B → C → A: $100+110+110+100+110 = 530$ metros

Logo, a escolha aleatória pode levar o Francisco a percorrer uma distância maior do que seria necessário, se optar pela vivenda B na primeira escolha.

O conselho diretivo de uma faculdade pretende instalar cabo de fibra ótica a ligar sete pavilhões: A1, A2, A3, A4, A5, A6 e A7.

Na tabela seguinte, encontram-se registadas algumas distâncias mínimas, em metros, entre os pavilhões.

A instalação de cabo de fibra ótica custa 3,40 euros por metro.

De modo a minimizar o custo da instalação do cabo de fibra ótica, a ligação entre os pavilhões foi feita recorrendo-se ao algoritmo seguinte.

• Ordenam-se as distâncias registadas na tabela anterior, pela ordem crescente da sua grandeza, indicando-se, para cada distância, o par de pavilhões que lhe corresponde.
• Constrói-se um grafo, cujos vértices representam os pavilhões, selecionando-se, sucessivamente, as distâncias menores e tendo-se em conta que, se a aresta a que corresponde a distância selecionada não levar à formação de um circuito, essa aresta deve ser considerada; caso contrário, essa aresta não deve ser considerada.
• O algoritmo termina quando, no grafo, o número de arestas é igual ao número de vértices menos um.

Determine, nestas condições, o custo mínimo da instalação do cabo de fibra ótica.

Na sua resposta, deve aplicar o algoritmo, indicar o número mínimo de metros de cabo de fibra ótica necessários e calcular o custo mínimo da instalação.

Como interpretar. Kruskal com sete vértices: termina em seis arestas.

Ordenando as distâncias entre os sete pavilhões registadas na tabela, temos:

$100_{\,A3-A5} \lt 150_{\,A3-A4} \lt 190_{\,A2-A3} \lt 200_{\,A2-A5} \lt 220_{\,A4-A5} = 220_{\,A5-A6} \lt 240_{\,A4-A6} \lt 340_{\,A2-A6} \lt 350_{\,A1-A7} \lt 500_{\,A1-A2} \lt 650_{\,A6-A7} \lt 730_{\,A1-A6}$

• I — aresta A3–A5 (100 m)
• II — aresta A3–A4 (150 m)
• III — aresta A2–A3 (190 m) (não se consideram as arestas A2–A5 e A4–A5, porque levariam à formação de circuitos)
• IV — aresta A5–A6 (220 m) (não se consideram as arestas A4–A6 e A2–A6, porque levariam à formação de circuitos)
• V — aresta A1–A7 (350 m)
• VI — aresta A1–A2 (500 m)

Como o número de arestas selecionadas é igual ao número de vértices menos um ($7-1 = 6$), o algoritmo termina.

$100 + 150 + 190 + 220 + 350 + 500 = 1510 \text{ metros}$

$1510 \times 3{,}40 = 5134 \text{ euros}$

O custo mínimo da instalação é 5134 €.

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 e apresentar uma conclusão.

Como interpretar. A opção 1 é o vizinho mais próximo; a opção 2 é o algoritmo da aresta de menor peso. Compara-se o total de cada uma.

Aplicando o algoritmo indicado na opção 1, obtemos o seguinte percurso:

Amarante $\xrightarrow{61}$ Porto $\xrightarrow{70}$ Braga $\xrightarrow{117}$ Lamego $\xrightarrow{62}$ Viseu $\xrightarrow{107}$ Amarante

Aplicando o algoritmo indicado na opção 2, a ordenação das distâncias entre as cidades é:

$61_{\,A-P} \lt 62_{\,L-V} \lt 70_{\,B-P} \lt 71_{\,A-L} \lt 74_{\,A-B} \lt 75_{\,P-V} \lt 106_{\,P-L} \lt 107_{\,A-V} \lt 117_{\,B-L} \lt 130_{\,B-V}$

• I — Amarante–Porto (61 km)
• II — Lamego–Viseu (62 km)
• III — Braga–Porto (70 km)
• IV — Amarante–Lamego (71 km)
  (não se considera o par Amarante–Braga porque Amarante apareceria três vezes)
  (não se consideram os pares Porto–Viseu, nem Porto–Lamego, porque Porto apareceria três vezes)
  (não se considera o par Amarante–Viseu porque Amarante apareceria três vezes)
  (não se considera o par Braga–Lamego porque Lamego apareceria três vezes)
• V — Braga–Viseu (130 km)

Amarante $\xrightarrow{61}$ Porto $\xrightarrow{70}$ Braga $\xrightarrow{130}$ Viseu $\xrightarrow{62}$ Lamego $\xrightarrow{71}$ Amarante

• Opção 1: $61+70+117+62+107 = 417$ km
• Opção 2: $61+70+130+62+71 = 394$ km

O Luís não tem razão: o percurso obtido pela opção 2 é o que tem um número inferior de quilómetros.

Um grupo de professores de Educação Física do agrupamento de escolas de Pontes de Cima pretende promover hábitos de vida saudáveis. Para a concretizaçã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.

No grafo, os vértices A, B, C, D, E, F e G representam os postos de visita obrigatória. Cada aresta representa um trajeto direto que liga dois desses postos.

Mostre que não é possível organizar um percurso para essa caminhada que cumpra, em simultâneo, as seguintes condições:

• passar por todos os postos representados no grafo da figura anterior, começando e terminando no posto A;
• percorrer uma só vez cada trajeto direto representado;
• percorrer todos os trajetos diretos representados.

Um arquiteto organizou o recinto destinado à realização de uma conferência internacional de arte (figura seguinte). O recinto tem os seguintes espaços: auditório, cantina, espaço de debate, exposição, pátio e teatro.

Todos os espaços têm, pelo menos, uma porta.

Ao analisar o esquema desenhado pelo arquiteto (figura anterior), uma funcionária comentou que, caso se mantivesse o número de portas, não conseguiria efetuar uma ronda ao recinto começando e terminando essa ronda na cantina, percorrendo todas as portas e passando por cada porta uma única vez.

A funcionária pretendeu, então, encontrar uma solução que lhe permitisse efetuar essa ronda percorrendo todas as portas e passando o menor número de vezes possível por cada porta.

Determine, justificando, uma solução que permita satisfazer a pretensão da funcionária.

Na sua resposta, deve apresentar um grafo que modele a situação descrita, apresentar o significado dos elementos, arestas e vértices, que constituem o grafo, e apresentar, justificando, uma solução.

Como interpretar. Com quatro vértices de grau ímpar, é preciso duplicar duas arestas que os emparelhem — cada duplicação corresponde a passar duas vezes por essa porta.

• P — Pátio: grau 5
• E — Exposição: grau 3
• D — Espaço de debate: grau 4
• C — Cantina: grau 3
• A — Auditório: grau 4
• T — Teatro: grau 3

A funcionária não consegue efetuar uma ronda ao recinto começando e terminando essa ronda na cantina, percorrendo todas as portas e passando por cada porta uma única vez porque este objetivo corresponde a encontrar um circuito de Euler, o que só é possível se todos os vértices tiverem grau par, o que não acontece neste caso, porque existem quatro vértices com grau ímpar: E, C e T (todos com grau 3) e P (com grau 5).

Assim, a solução para o problema da funcionária passa por duplicar arestas que permitam obter um grafo conexo com todos os vértices com grau par, por exemplo duplicando as arestas PE e CT (assinaladas a tracejado na figura seguinte), o que corresponde a passar nessas duas portas, por duas vezes, ficando desta forma todos os vértices com grau par:

Uma possibilidade é $C \to T \to A \to P \to E \to D \to C \to P \to E \to A \to D \to P \to T \to C$ (o mesmo percurso em sentido inverso também satisfaz as condições).

Na aldeia de Xisto, vai realizar-se uma minimaratona.

Na figura seguinte, encontra-se o grafo que serve de modelo ao percurso da minimaratona.

No grafo, o vértice $B$ representa o ponto de partida e de chegada, e os vértices $A$, $C$, $D$, $E$ e $F$ representam postos de distribuição de água.

Cada aresta representa um trajeto direto que liga dois postos de distribuição de água ou um posto de distribuição de água ao ponto de partida.

Os organizadores da corrida decidiram que todos os participantes tinham de passar por todos os trajetos diretos, sem repetirem nenhum.

O Carlos, um dos organizadores da corrida, observou o grafo e afirmou:

«É impossível passar por todos os trajetos diretos sem repetir nenhum. Para garantir que os participantes passam por todos os trajetos diretos, é necessário admitir duplicações de trajetos diretos já existentes.»

Justifique a veracidade da afirmação, e apresente no grafo um par de duplicações de trajetos diretos que permita garantir que os participantes passam por todos os trajetos diretos.

Como interpretar. Quatro vértices de grau ímpar exigem duas duplicações.

O Carlos observou que é impossível passar por todos os trajetos diretos sem repetir nenhum, porque este objetivo corresponde a encontrar um circuito de Euler, o que só é possível se todos os vértices tiverem grau par, o que não acontece neste caso, porque existem quatro vértices com grau ímpar: A, B e C (todos com grau 3) e D (com grau 5).

Assim, a solução para o problema passa por duplicar arestas que permitam obter um grafo conexo com todos os vértices com grau par, por exemplo duplicando as arestas AB e CD (assinaladas a tracejado na figura seguinte), o que corresponde a percorrer estes dois trajetos por duas vezes, ficando desta forma todos os vértices com grau par:

• A — grau 4
• B — grau 4
• C — grau 4
• D — grau 6
• E — grau 2
• F — grau 2

Duplicando os trajetos AB e CD, todos os vértices ficam com grau par e passa a ser possível percorrer todos os trajetos.

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, estão indicadas as distâncias, em quilómetros, entre A, B, C, D e F.

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.

Uma semana antes do início do serviço de transporte, é feito o anúncio seguinte.

«Se a estrada que liga a aldeia A à aldeia B estiver intransitável, é necessário percorrer mais quilómetros para utilizar um percurso alternativo.»

Justifique a veracidade ou a falsidade da informação, aplicando o algoritmo acima descrito aos dois casos:

• a estrada que liga A a B está transitável;
• a estrada que liga A a B está intransitável.

Na figura seguinte, encontra-se o grafo que serve de modelo à volta utilizada pelo camião da empresa do Miguel, para efetuar a distribuição de congelados pelos supermercados que fornece. No grafo, o vértice A representa a sede da empresa do Miguel, e os vértices B, C, D e E representam os supermercados. Cada aresta representa um trajeto direto que liga dois supermercados, ou que liga um supermercado à sede da empresa do Miguel.

O Miguel elaborou uma lista com as voltas de distribuição, que começam e terminam na sede da sua empresa, visitando todos os supermercados, e não repetindo nenhum deles. Para o Miguel, o que importa é o número de quilómetros percorridos, por isso, é indiferente, por exemplo, percorrer ABCDEA ou percorrer AEDCBA.

46.1. Num determinado dia, o camião deve visitar, em primeiro lugar, o supermercado representado por D, visitando depois os restantes, e não repetindo nenhum deles, antes de regressar à sede da empresa.

Identifique todas as voltas possíveis para esse dia.

46.2. Mostre que o grafo da figura anterior admite, exatamente, doze voltas distintas, que podem fazer parte da lista do Miguel.

46.1 — Voltas que começam em D

Como interpretar. Como o grafo é completo, depois de A → D restam $3! = 6$ ordens possíveis para B, C e E.

Volta	Sequência
1	A → D → B → C → E → A  (ADBCEA)
2	A → D → B → E → C → A  (ADBECA)
3	A → D → C → B → E → A  (ADCBEA)
4	A → D → C → E → B → A  (ADCEBA)
5	A → D → E → B → C → A  (ADEBCA)
6	A → D → E → C → B → A  (ADECBA)

São seis as voltas possíveis para esse dia.

46.2 — As doze voltas distintas

Como interpretar. Contam-se todos os circuitos com início e fim em A e, no fim, divide-se por 2, porque cada volta e a sua inversa são, para o Miguel, a mesma volta.

Assim, podemos ver que existem $1\times 4\times 3\times 2\times 1\times 1 = 24$ percursos diferentes, mas como metade dos percursos corresponde à outra metade percorridos por ordem inversa, o número de voltas que podem fazer parte da lista do Miguel é:

$\dfrac{24}{2} = 12$

O grafo admite, exatamente, doze voltas distintas.

Na figura seguinte, encontra-se o grafo que serve de modelo aos percursos utilizados pela RecSol, uma empresa de recolha de resíduos sólidos. Cada vértice do grafo representa um local de recolha de resíduos sólidos, e cada aresta representa uma estrada que liga dois desses locais.

Na tabela seguinte, encontram-se registadas as distâncias mínimas, em metros, entre cada dois locais de recolha de resíduos sólidos, representados pelos vértices do grafo da figura anterior, quando se percorrem as estradas representadas pelas arestas do mesmo grafo.

47.1. O Antó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 pretensões do António ser satisfeitas, em simultâneo? Justifique a sua resposta.

47.2. A RecSol vai ligar todos os locais de recolha de resíduos sólidos com um cabo de fibra ótica, utilizando algumas das estradas representadas no grafo da figura anterior.

De modo a usar a menor extensão de cabo de fibra ótica, a empresa contactou dois especialistas em instalação de fibra ótica, o João e o José.

O João afirma, sem recurso a nenhum método, que a ligação que requer menos cabo é {(A,B), (F,G), (B,F), (B,E), (C,E), (C,D)}.

O José propõe uma ligação apoiando-se no uso do algoritmo seguinte.

Indique qual das duas propostas deve escolher a empresa, de modo a usar a menor extensão de cabo de fibra ótica.

Na sua resposta, deve determinar o número de metros da proposta do João, aplicar ao grafo o algoritmo proposto pelo José, determinar o número de metros da proposta do José e apresentar uma conclusão sobre a escolha da empresa.

O António é carteiro. Habitualmente, organiza o percurso antes de iniciar a distribuição das encomendas. Certo dia, o António decidiu fazer um grafo ponderado (figura seguinte), com as distâncias a cada um dos locais de entrega das encomendas desse mesmo dia.

No grafo da figura seguinte, os seis vértices representam a estação de correios (C), a escola (E), o ginásio (G), o restaurante (R), a fábrica (F) e a associação desportiva (A). Cada aresta do grafo representa um trajeto direto entre dois locais já referidos. A ponderação de cada aresta representa a distância, em metros, entre os locais considerados.

O António pretende partir da estação de correios, (C), passar por todos os outros locais representados, nos quais tem de entregar encomendas nesse dia, não mais do que uma vez por cada um deles, e regressar depois à estação de correios, percorrendo o número mínimo de metros.

Defina um percurso que satisfaz o que o António pretende e indique o número de metros que ele tem de percorrer.

Como interpretar. Como não é preciso usar todos os trajetos — basta passar por todos os locais — pode suprimir-se a aresta que liga os dois vértices de grau ímpar.

Como o António pretende encontrar um percurso que começa e termina no mesmo vértice (C), e percorrer o número mínimo de metros, não é necessário utilizar todos os trajetos. Como o grafo tem dois vértices com grau ímpar, C (grau 3) e E (grau 3), suprimindo a aresta (C,E), estes dois vértices também ficam com grau par e assim podemos obter um circuito de Euler, como indicado na figura ao lado.

C $\xrightarrow{923}$ F $\xrightarrow{895}$ G $\xrightarrow{250}$ A $\xrightarrow{700}$ E $\xrightarrow{700}$ R $\xrightarrow{250}$ C

(o mesmo percurso em sentido inverso também satisfaz as condições do António)

$923 + 895 + 250 + 700 + 700 + 250 = 3718 \text{ m}$

O António tem de percorrer 3718 metros.

A empresa Silva-Filhos dedica-se à limpeza de estradas. A empresa está sediada no distrito de Viseu.

Na figura seguinte, encontra-se o grafo que serve de modelo ao circuito utilizado pela empresa ao efetuar a limpeza das estradas.

Cada vértice do grafo representa uma localidade, e cada aresta representa uma estrada que liga duas localidades.

Considere a afirmação:

«Não é possível limpar todas as estradas representadas no grafo da figura anterior, percorrendo cada estrada uma e uma só vez, se o camião de limpeza partir de Beselga e regressar a Beselga. Mas, é possível alterar esta situação.»

Justifique a veracidade da afirmaçã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 só vez, partindo de Beselga e regressando a Beselga.

Como interpretar. Dois vértices de grau ímpar: acrescentar uma aresta entre eles (duplicando a estrada que os liga) resolve.

Não é possível limpar todas as estradas representadas no grafo partindo e terminando de Beselga, percorrendo todas as estradas uma e uma só vez porque este objetivo corresponde a encontrar um circuito de Euler, o que só é possível se todos os vértices tiverem grau par, o que não acontece neste caso, porque existem dois vértices com grau ímpar: Penedono e Resende (ambos com grau 3).

Assim, é possível alterar a solução se acrescentar uma aresta que corresponde à duplicação da aresta Penedono–Resende, o que corresponde a passar nesta estrada, por duas vezes, como se apresenta na figura seguinte.

Como estes dois vértices passam a ter grau 4, obtém-se um grafo conexo com todos os vértices de grau par, onde é possível definir circuitos de Euler com início e fim em Beselga.

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 seguinte, 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.

50.1. Mostre 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 anterior;
• percorrer, uma e uma só vez, cada trajeto representado;
• percorrer todos os trajetos representados.

50.2. Considere, 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 anterior.

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.

Determine o preço mínimo, em euros, que o comprador paga por cada transporte.

Na sua resposta deve 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, e calcular o preço a pagar pelo menor circuito.

50.1 — Impossibilidade do circuito

Não é possível organizar um circuito que permita que um camionista da GNC percorra uma e uma só vez cada trajeto assinalado no grafo porque este objetivo corresponde a encontrar um circuito de Euler, o que só é possível se todos os vértices do grafo tiverem grau par, o que não acontece neste caso, porque existem vértices com grau ímpar: Faro (grau 1), Évora, Vila Real e Porto (todos com grau 3).

50.2 — Preço mínimo

Como interpretar. Constroem-se todos os circuitos com início e fim em Sines. Como cada circuito e o seu inverso têm a mesma extensão, os seis circuitos correspondem a três extensões distintas.

Como os seis circuitos possíveis correspondem apenas a três pares, respetivamente percorridos pela ordem inversa, temos que o menor circuito tem a extensão de 1262 km.

Como o preço do transporte cobrado pela empresa GNC aos clientes é de € 2,00 por quilómetro e a empresa faz um desconto de 8%, o preço a pagar pelo menor circuito é:

$1262 \times 2 \times 0{,}92 = 2322{,}08 \text{ €}$

O preço mínimo por transporte é 2322,08 €.

Uma Câmara Municipal elaborou um contrato com a empresa FUTUROLIMPO, empresa especializada na recolha seletiva de resíduos.

Na figura seguinte, apresenta-se um «mapa» de uma zona residencial desse município, que possui oito espaços de recolha seletiva de resíduos (ecopontos). Os oito ecopontos estão representados por $E_1$, $E_2$, $E_3$, $E_4$, $E_5$, $E_6$, $E_7$ e $E_8$.

Designa-se por «troço de rua» a ligação entre dois ecopontos adjacentes, isto é, o percurso que se efetua para ir de um desses ecopontos ao outro sem passar por mais nenhum.

51.1. Considere que o camião de recolha seletiva de resíduos que passa por essa zona residencial inicia o seu percurso no ecoponto $E_4$ e que o termina no ecoponto $E_2$.

Admita que, em cada troço de rua, o camião pode estacionar junto de cada ecoponto, independentemente do sentido de circulação.

Indique um percurso, de $E_4$ a $E_2$, para que o camião possa recolher os resíduos de todos os ecopontos, passando por cada um deles uma única vez.

Apresente o percurso na forma de uma sequência, utilizando as designações dos ecopontos.

51.2. Os moradores da mesma zona residencial reclamaram das condições de alguns troços de rua de acesso aos ecopontos. A Câmara Municipal decidiu enviar um funcionário especializado, para inspecionar as condições dos mesmos.

Admita que o funcionário decidiu iniciar e terminar as suas inspeções junto do mesmo ecoponto. No entanto, ao analisar o «mapa» da zona em causa, concluiu que, para concretizar essa decisão, não tinha possibilidade de inspecionar todos os troços de rua, passando por cada um deles uma única vez. Por isso, de forma a rendibilizar o tempo da inspeção, procurou encontrar um percurso cujo número de troços de rua a percorrer fosse o menor possível, garantindo o início e o fim da inspeção junto do mesmo ecoponto.

Num pequeno texto:

• indique, justificando, a razão que levou o funcionário a concluir da impossibilidade de inspecionar todos os troços de rua, passando por cada um deles uma única vez, tendo em conta que ele pretende iniciar e terminar a inspeção junto do mesmo ecoponto;
• indique, ainda, um percurso que se inicie e termine no ecoponto $E_2$ e que permita ao funcionário inspecionar todos os troços de rua, sendo o número de troços de rua a percorrer o menor possível.

Comece, obrigatoriamente, por modelar, através de um grafo, o «mapa» da zona residencial apresentado, considerando que os vértices representam os ecopontos e que as arestas representam os troços de rua.

51.1 — Percurso de E₄ a E₂

Como interpretar. Passar por todos os ecopontos uma única vez é um caminho de Hamilton de $E_4$ a $E_2$.

$E_4 \to E_5 \to E_6 \to E_1 \to E_7 \to E_8 \to E_3 \to E_2$

51.2 — Inspeção de todos os troços

Como interpretar. Agora é preciso percorrer todas as arestas: é um circuito de Euler. Como $E_2$ e $E_8$ têm grau ímpar e não estão diretamente ligados, duplicam-se duas arestas que os liguem através de $E_3$.

• $E_1$ — grau 2
• $E_2$ — grau 3
• $E_3$ — grau 4
• $E_4$ — grau 2
• $E_5$ — grau 4
• $E_6$ — grau 6
• $E_7$ — grau 4
• $E_8$ — grau 3

A impossibilidade de inspecionar todos os troços de rua, passando por cada um deles uma única vez corresponde a encontrar um circuito de Euler, o que só é possível se todos os vértices do grafo tiverem grau par, o que não acontece neste caso, porque existem vértices com grau ímpar: $E_2$ e $E_8$ (ambos com grau 3).

Como não existe uma aresta que ligue os vértices $E_2$ e $E_8$, podemos duplicar, por exemplo, as arestas ($E_2$, $E_3$) e ($E_3$, $E_8$), mantendo a paridade do grau do vértice $E_3$, como se representa na figura ao lado.

$E_2 \to E_4 \to E_5 \to E_2 \to E_3 \to E_7 \to E_3 \to E_8 \to E_7 \to E_1 \to E_6 \to E_5 \to E_8 \to E_3 \to E_2$

O António vive em Lisboa 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 assistência aos seus clientes. A partir da próxima semana, vai começar a dar também assistência a clientes de duas cidades espanholas, Sevilha e Cáceres. Está neste momento a organizar um plano do percurso pelas quatro cidades: partindo de sua casa, passa uma única vez por cada uma das quatro cidades e volta de novo a casa.

Pretende, também, percorrer o mínimo de quilómetros possível. Na tabela seguinte, estão referidas as distâncias, em quilómetros, entre aquelas cidades.

52.1. Desenhe um grafo ponderado que sirva de modelo às várias hipóteses de percurso possíveis. Como peso, atribua a cada aresta a distância, em quilómetros, a ela associada.

52.2. O António está convencido de que, se tiver de visitar, em primeiro lugar, o cliente de Coimbra, percorrendo depois as restantes cidades, antes do regresso a Lisboa, o percurso mais curto, nas condições a que está sujeito, consiste em seguir de Coimbra para Faro e só depois visitar as cidades espanholas, antes do regresso a Lisboa.

Numa composição, justifique se o António tem razão.

Deve incluir, obrigatoriamente, na sua composição:

• o número total de circuitos que obedecem aos critérios definidos;
• a identificação de todos os percursos possíveis, bem como a distância percorrida em cada um deles;
• a conclusão final, identificando o percurso de extensão mínima.

52.1 — Grafo ponderado

52.2 — O percurso mais curto

Como interpretar. Fixado Coimbra em primeiro lugar, restam $3! = 6$ ordens para as outras três cidades. Basta calcular as seis distâncias.

Designando Lisboa por Lx, Coimbra por Cb, Faro por Fr, Cáceres por Cc e Sevilha por Sv, podemos identificar todos os percursos possíveis com início e final em Lisboa visitando em primeiro lugar Coimbra:

Assim temos que, no total, existem $1\times 3\times 2\times 1\times 1 = 6$ circuitos que obedecem aos critérios definidos.

Destes apenas dois estão de acordo com o critério definido pelo António, cujas distâncias percorridas são 1814 km e 1423 km.

Podemos observar que existe um circuito que visita primeiro as cidades espanholas, e só depois Faro, que permite obter uma distância percorrida de 1291 km, portanto sem cumprir o critério definido pelo António mas com uma distância total inferior:

Lisboa → Coimbra → Cáceres → Sevilha → Faro → Lisboa (1291 km)

Assim, concluímos que o António não tem razão.

Alguns visitantes menos civilizados do Parque da Pena, em Sintra, têm por hábito deitar para o chão sacos de plá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 existente nos caminhos duma zona do Parque.

Na figura seguinte, está um mapa dessa zona do Parque da Pena. Os cruzamentos dos caminhos estã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 assinalados, recolhendo o lixo, e regressa ao ponto A.

53.1. O grupo de jovens tem de percorrer pelo menos um caminho, mais do que uma vez.

Justifique esta afirmação, começando por modelar, por meio de um grafo, o mapa da zona do Parque da Pena representado na figura.

53.2. Indique um percurso em que o número de caminhos percorridos mais do que uma vez seja o menor possível.

Dê a sua resposta na forma de uma sequência de letras, de acordo com a sequência de cruzamentos do percurso por si escolhido.

53.3. Na obra de Joseph Malkevitch, Modelos de Grafos, pode ler-se: «A ideia chave na modelação matemática consiste em tomar a situação original e simplificá-la de tal modo que fiquemos com uma nova visão sobre o problema original.»

Elabore uma composição onde desenvolva a ideia expressa, nesta frase, por Joseph Malkevitch. Baseie-se no modelo que considerou nas alíneas anteriores ou num exemplo à sua escolha, que integre a utilização de grafos.

Nessa composição deve referir:

• o porquê da necessidade de simplificar a realidade;
• o porquê da necessidade de distinguir o essencial do acessório;
• os aspetos que foram simplificados, relativamente à situação original.

53.1 — Porque é necessário repetir um caminho

• A — grau 3
• B — grau 4
• C — grau 4
• D — grau 4
• E — grau 4
• F — grau 3

Logo, como o grupo de jovens que parte do ponto A, percorre todos os caminhos assinalados e regressa ao ponto A, tem de percorrer pelo menos um caminho, mais do que uma vez, porque percorrer todos os caminhos, uma única vez corresponde a encontrar um circuito de Euler, o que só é possível se todos os vértices tiverem grau par, o que não acontece neste caso, porque existem dois vértices com grau ímpar: A e F (ambos com grau 3).

53.2 — Percurso com o mínimo de repetições

Assim um percurso em que o número de caminhos percorridos mais do que uma vez seja o menor possível, consiste em percorrer o caminho que liga o cruzamento A ao cruzamento F, por duas vezes, tornando assim par o grau de todos os vértices do grafo.

$A \to C \to D \to E \to F \to A \to B \to C \to D \to E \to B \to F \to A$

53.3 — Composição

A realidade depende e incorpora detalhes que podem ser simplificados ou ignorados, sem perda de informação relevante, e cuja desvalorização pode resultar em situações mais abstratas, mas mais fáceis de analisar.

Neste processo de simplificação é importante garantir que não são omitidos, simplificados ou ignorados detalhes relevantes, sob pena de comprometer a análise e a adequação da solução encontrada para a situação específica que se pretende estudar.

Nesta situação em particular, no mapa (situação original) existem informações que não são relevantes para a solução, como a localização dos lagos, da fonte, da estufa, ou da tapada. A omissão destes dados não compromete a adequação da solução, porque apenas se centra na quantidade de caminhos e dos cruzamentos que cada caminho liga, sendo estas as informações que não podem ser simplificadas ou omitidas no processo de modelação.