Aula 18Mai2015 CaminhoMinimo

1) Os caminhos que levam à Região Norte do Brasil são problemáticos em função da quantidade e qualidade das estradas. Ela possui uma grande bacia hidrográfica, o que impede a construção de estradas em alguns trechos. Um atleta da UPIS deseja fazer o percurso de bicicleta da cidade de Goiás até a cidade de Boa Vista, ambas indicadas na figura abaixo. Os parâmetros numéricos referem-se às distâncias entre os nós. Determine a menor distância que esse aventureiro deverá percorrer para atingir o seu objetivo.

2) Em uma aplicação na área de biologia, tem-se a imagem mostrada na figura (a), abaixo, como sendo as células de um vírus ofensivo ao ser humano. Um parâmetro importante aos pesquisadores é a distância máxima entre células. Ela fornece uma ideia da velocidade de reprodução e transmissão do vírus. Após a modelagem desta imagem através de grafos, obteve-se a imagem da figura (b). Os pesos das arestas foram calculados segundo dados estatísticos de cada uma das células, proximidade, tipo de célula, etc. Na tentativa de descobrir a maior distância entre células existentes na imagem, os pesquisadores precisam calcular a distância entre os nós 10 e 4 e depois entre os nós 3 e 5..

3) Seja o mapa, com algumas das cidades do estado de São Paulo, mostrado abaixo e uma tabela de distâncias.

(a) Calcule a distância e o menor caminho entre as cidades de Araçatuba e Ourinhos.
(b) Com a privatização das estradas, praças de pedágio foram construídas em todas as rodovias. Nas rodovias de comprimento inferior a 100km o pedágio custa R$4,00; caso contrário, o pedágio tem valor de R$5,00. Apresente a solução tal que além do cálculo da distância e o caminho mínimo, também seja determinado o gasto com pedágio.

Araçatuba
P. Venc.
P. Prud.
Tupã
Marília
Assis
Bauru
Ourinhos
Araçatuba
-
150
-
90
110
-
160
-
P. Venc.
150
-
40
95
-
-
-
-
P. Prud.
-
40
-
85
-
105
-
-
Tupã
90
95
85
-
60
80
-
-
Marília
110
-
-
60
-
85
65
80
Assis
-
-
105
80
85