Exercícios: Aplicações

A Câmara Municipal de Guimarães quer inspecionar a iluminação de Natal de todas as ruas do centro histórico. Num mapa simplificado, os cruzamentos são os vértices {A, B, C, D, E, F} e as ruas são as arestas AB, BC, CD, DE, EF, FA, AC, AE e CE.

1. a) Determina o grau de cada vértice.
2. b) É possível fazer um percurso que comece e termine no mesmo cruzamento e percorra cada rua exatamente uma vez? Justifica com a condição de Euler.
3. c) Indica um percurso nessas condições com início no cruzamento A.

No Parque da Cidade do Porto, um lago artificial tem duas ilhas, X e Y. As ilhas e as margens Norte (N) e Sul (S) estão ligadas por pontes de madeira: duas pontes entre N e X, uma ponte entre X e Y, duas pontes entre Y e S e uma ponte entre N e S.

1. a) Modela a situação por um grafo em que as margens e as ilhas são vértices e as pontes são arestas. Indica o grau de cada vértice.
2. b) Mostra que não é possível fazer um passeio que atravesse cada ponte exatamente uma vez. Justifica com a paridade dos graus.
3. c) A junta de freguesia quer construir uma nova ponte de modo a tornar o passeio possível, sem obrigar a regressar ao ponto de partida. Entre que dois vértices deve construí-la? Justifica a tua escolha.

A empresa de recolha de resíduos LimpaÉvora percorre diariamente as ruas de um bairro representadas pelo grafo com vértices {A, B, C, D} e arestas AB, BC, CD, DA e AC. O armazém da empresa fica no cruzamento B.

1. a) Mostra que é possível percorrer todas as ruas exatamente uma vez, indicando onde deve começar e onde deve terminar esse percurso. Escreve um percurso nessas condições.
2. b) A carrinha tem de começar e terminar o percurso no armazém (cruzamento B). É possível fazê-lo sem repetir nenhuma rua? Justifica.
3. c) Sendo obrigatório começar e acabar em B, qual é o número mínimo de ruas que terão de ser percorridas duas vezes? Indica um percurso que atinge esse mínimo.