Lista Pesquisa Operacional Dijkstra

Prévia do material em texto

Instituto de 
 
Curso: Ciência da Computação 
Professor(a): Flávio Henrique Batista de Souza
Aluno(a): 
CONTEÚDO: Aulas 14 e 15 
1 - Defina 
a – Quais as duas observações com relação ao algoritmo de Dijkstra?
b – Qual a definição de Caminho (ou canal) em grafos?
c – O que é uma árvore (em grafos)? 
d – Defina e descreva graficamente o que é um ciclo Hamiltoniano
e – Defina e descreva graficamente o que é um ciclo Euleriano
 
 
2 - Dado o Grafo: 
 
a) Demonstre a Matriz de Adjacências;
 
b) Demonstre a Matriz de Custos;
 
c) Demonstre o Caminho mínimo até z
 
3 Uma pequena parte do mapa de Belo Horizonte é utilizado por um representante comercial, que 
utiliza em seu iPad, um aplicativo baseado em Dijkstra que é previamente programado com esses 
bairros que foram tomados como os pontos de referênci
foram condicionados aos arcos se baseiam na multiplicação do 
congestionamento de tráfego, ou seja, o peso total 
ijct DPP ×= , onde ijD é a distância entre um nó 
ex.: 
kmD aAltoBarrocCalafate 8, = 
Supondo que cP =4: 
3284 ==×= xDPP ijct 
cP é condicionado à seguinte tabela, de acordo com a intensidade do congestionamento analisado 
pelo próprio representante: 
 
Instituto de Engenharia e Tecnologia – IET 
 Disciplina: Pesquisa Operacional
Flávio Henrique Batista de Souza Avaliação: Lista de Exercícios 
Turma: Data: ____/____/17 Valor
Quais as duas observações com relação ao algoritmo de Dijkstra? 
Qual a definição de Caminho (ou canal) em grafos? 
Defina e descreva graficamente o que é um ciclo Hamiltoniano 
Defina e descreva graficamente o que é um ciclo Euleriano 
 
Demonstre a Matriz de Adjacências; 
Demonstre a Matriz de Custos; 
mínimo até z 
Uma pequena parte do mapa de Belo Horizonte é utilizado por um representante comercial, que 
utiliza em seu iPad, um aplicativo baseado em Dijkstra que é previamente programado com esses 
bairros que foram tomados como os pontos de referência, ou como nós (ou vértices). Os pesos que 
foram condicionados aos arcos se baseiam na multiplicação do cP , que é o peso atribuído ao índice de 
congestionamento de tráfego, ou seja, o peso total tP de cada arco de A é: 
é a distância entre um nó i e um nó j , onde ji ≠ . 
é condicionado à seguinte tabela, de acordo com a intensidade do congestionamento analisado 
Horário 
cP 
8:00 3 
10:00 1 
15:00 2 
18:00 3 
 
Pesquisa Operacional 
Lista de Exercícios 3 
Valor: 4 pts Nota: 
Uma pequena parte do mapa de Belo Horizonte é utilizado por um representante comercial, que 
utiliza em seu iPad, um aplicativo baseado em Dijkstra que é previamente programado com esses 
a, ou como nós (ou vértices). Os pesos que 
, que é o peso atribuído ao índice de 
 
 
é condicionado à seguinte tabela, de acordo com a intensidade do congestionamento analisado 
 
Solucione, demonstrando para cada situação (lembre-se de avaliar os pesos *SEMPRE*): 
 
• A Matriz de Custo; 
• Grafo Correspondente 
• O caminho mínimo (Dijkstra); 
 
****considere a ordem do enunciado: nó inicial� de onde sai o representante; descreva os nós restantes na 
seqüência em que são apresentados no enunciado; nó final�destino do representante**** 
 
Situação - Terminada a reunião com seu cliente no Calafate, o representante sai às 10:00hs para buscar um 
documento importante no Bairro Salgado Filho, onde ele considera as opções dos bairros Nova Suíça e Jardim 
América. 
• A Matriz de Custo; 
Matriz Com o custo REAL (avaliando os pesos) 
• Grafo Correspondente 
(Em sala) 
• O caminho mínimo (Dijkstra); 
 Passo 1 Passo 2 Passo 3 Passo 4 
Cal 
 
NS 
 
JÁ 
 
SF 
 
 
 
 
 
4 – O Router 1, utilizando o OSPF, pretende transmitir um pacote até o Router X de destino (e gerar um mapa de 
comunicação com custo mínimo durante o processo), considerando uma rede com os seguintes roteadores e links: 
5 km 
7 km 
3 km 
8 km 10 km 
9 km 
7 km 
2 km 
7 km 
3 km 
8 km 
7 km 
4 km 
2 km 
12 km 
13 km 
12 km 
16 km 
5 km 
7 km 
3 km 
3 km 
 
 
Note que os links possuem pesos. Esses Pesos são avaliados de acordo com um critério que considera a velocidade do 
link entre os nós, o custo financeiro da operadora para utilizar o link e um fator multiplicador. Entre os roteadores 5 
e 6 houve um rompimento de fibra, o que elimina o link entre eles (ENTÃO CUIDADO COM O CÁLCULO). 
Roteador Passo 1 Passo 2 Passo3 Passo4 Passo 5 Passo 6 Passo 7 Passo 8 
Router 1 
 Router 2 
 Router 3 
 Router 4 
 Router 5 
 Router 6 
 Router 7 
 Router X