Estruturas de Dados - Grafos (Parte 3)

Prévia do material em texto

Grafos 3, cont.
Estrutura de Dados
Prof. Carla Koike
   
Caminhos mais curtos
● Muitas das aplicações de grafos necessitam encontrar o 
caminho mais curto entre dois vértices de um grafo 
ponderado
● Busca em largura obtém o caminho mais curto entre dois 
vértices, se todos os arcos tiverem o  mesmo peso
● O caminho mais curto entre dois vértice é um subgrafo, tal 
que seus vértices são os vértices alcançáveis do vértice 
origem, o subgrafo forma uma árvore cuja raiz é o vértice 
origem e para todos os vértices,  o caminho simples da 
origem até esse vértice é o caminho mais curto
   
Dijkstra – Algoritmo mais Utilizado
● Escolhido um vértice como raiz da busca, este 
algoritmo calcula o custo mínimo deste vértice 
para todos os demais vértices do grafo.
●  O algoritmo pode ser usado sobre grafos 
orientados, ou não, e admite que todas as 
arestas possuem pesos não negativos (nulo é 
possível).
   
Dijkstra
Seja G(V,A) um grafo orientado e s um vértice de G:
1. Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da 
busca) e infinito às demais estimativas;
2. Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o 
vértice que precede t no caminho de custo mínimo de s para t);
3. Enquanto houver vértice aberto:
          * seja k um vértice ainda aberto cuja estimativa seja a menor dentre 
todos os vértices abertos;
          * feche o vértice k
          * Para todo vértice j ainda aberto que seja sucessor de k faça:
               ­ some a estimativa do vértice k com o custo do arco que une k a j;
               ­ caso esta soma seja melhor que a estimativa anterior para o vértice 
j, substitua­a e anote k como precedente de j.
   
Dijkstra
Seja G(V,A) um grafo orientado e s um vértice de G:
1. Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da 
busca) e infinito às demais estimativas;
2. Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o 
vértice que precede t no caminho de custo mínimo de s para t);
   
...
3. Enquanto houver vértice aberto:
          * seja k um vértice ainda aberto cuja estimativa seja a menor dentre 
todos os vértices abertos;
          * feche o vértice k
         * Para todo vértice j ainda aberto que seja sucessor de k faça:
               ­ some a estimativa do vértice k com o custo do arco que une k a j;
               ­ caso esta soma seja melhor que a estimativa anterior para o vértice 
j, substitua­a e anote k como precedente de j.
       
   
...
3. Enquanto houver vértice aberto:
          * seja k um vértice ainda aberto cuja estimativa seja a menor dentre 
todos os vértices abertos;
          * feche o vértice k
         * Para todo vértice j ainda aberto que seja sucessor de k faça:
               ­ some a estimativa do vértice k com o custo do arco que une k a j;
               ­ caso esta soma seja melhor que a estimativa anterior para o vértice 
j, substitua­a e anote k como precedente de j.
       
   
...
3. Enquanto houver vértice aberto:
          * seja k um vértice ainda aberto cuja estimativa seja a menor dentre 
todos os vértices abertos;
          * feche o vértice k
         * Para todo vértice j ainda aberto que seja sucessor de k faça:
               ­ some a estimativa do vértice k com o custo do arco que une k a j;
               ­ caso esta soma seja melhor que a estimativa anterior para o vértice 
j, substitua­a e anote k como precedente de j.
       
   
...
3. Enquanto houver vértice aberto:
          * seja k um vértice ainda aberto cuja estimativa seja a menor dentre 
todos os vértices abertos;
          * feche o vértice k
         * Para todo vértice j ainda aberto que seja sucessor de k faça:
               ­ some a estimativa do vértice k com o custo do arco que une k a j;
               ­ caso esta soma seja melhor que a estimativa anterior para o vértice 
j, substitua­a e anote k como precedente de j.
       
   
...
3. Enquanto houver vértice aberto:
          * seja k um vértice ainda aberto cuja estimativa seja a menor dentre 
todos os vértices abertos;
          * feche o vértice k
         * Para todo vértice j ainda aberto que seja sucessor de k faça:
               ­ some a estimativa do vértice k com o custo do arco que une k a j;
               ­ caso esta soma seja melhor que a estimativa anterior para o vértice 
j, substitua­a e anote k como precedente de j.
       
   
Usando Grafos na Análise de Circuitos 
Elétricos
● A análise de circuitos elétricos com vários 
componentes passa pela construção de um sistema 
de equações lineares
● Para a análise utiliza­se:
– As equações básicas dos componentes (resistores, 
capacitores e indutores) 
– As leis de Kirchhoff para malhas de corrente e tensão
● Uma forma alternativa é representar o circuito por um 
grafo e determinar as equações a partir do grafo.
   
Construindo o Grafo de um Circuito
Os nós do grafo são os pontos de 
conexão, e os arcos são os 
componentes.
Orientação do arco segue orientação 
da corrente (do + para o ­)
   
Árvores do Circuito
Árvore: conjunto de ramos 
que conecta todos os nós 
sem formar ciclos
(Por ex., árvores geradoras 
mínimas)
   
Cortes Fundamentais
● Cortes realizados em um dos ramos da árvore 
do circuito
● Cada corte define uma das equações de 
análise nodal de Kirchhoff 
● N nós no grafo ⇒ N­1 ramos na árvore ⇒ N­1 
Cortes fundamentais ⇒ N­1 Equações
   
Cortes Fundamentais ⇒ Equações
   
Cortes Fundamentais ⇒ Equações
Não é um corte fundamental, 
pois atravessa dois ramos da 
árvore, mas ainda é um corte 
válido
   
Cortes Fundamentais ⇒ Equações
i
2
 – i
3
 – i
4
 = 0
i
1
 – i
2
 = 0
i
s
 + i
4
 + i
3
 = 0
   
Cortes Fundamentais ⇒ Equações
i
2
 – i
3
 – i
4
 = 0
i
1
 – i
2
 = 0
i
s
 + i
4
 + i
3
 = 0
Quatro Variáveis e 
somente três equações.
Soma primeira, segunda e 
terceiras equações, para 
obter mais uma equação: 
a do nó 1.
   
Cortes Fundamentais ⇒ Equações
i
2
 – i
3
 – i
4
 = 0
i
1
 – i
2
 = 0
i
s
 + i
4
 + i
3
 = 0
i
2
 – i
3
 – i
4
 = 0
i
1
 – i
2
 = 0
i
s
 + i
4
 + i
3
 = 0
i
s
 + i
1
 = 0
Quatro Variáveis e 
somente três equações.
Soma primeira, segunda e 
terceiras equações, para 
obter mais uma equação: 
a do nó 1.
   
Outros Exemplos
Árvore e cortes 
   
Outros Exemplos
Árvore e cortes 
   
Outras aplicações
● Roteamento, Planejamento, Projeto de 
cabeamentos, Estrutura viária, entre muitas 
outras
● Ver link/arquivo de Aplicações Práticas no 
Moodle
   
Mapas topológicos em Robótica
   
Proximity Graphs
   
Aplicação: Escalonamento
➔ Pegar o ovo
➔ Untar a frigideira
➔ Quebrar o ovo
➔ Pegar o óleo
➔ Pôr o ovo na frigideira
➔ Retirar o ovo
➔ Esquentar o óleo
➔ Esperar o ovo fritar
Pegar o Ovo
   
Aplicação: Escalonamento
➔ Pegar o ovo
➔ Untar a frigideira
➔ Quebrar o ovo
➔ Pegar o óleo
➔ Pôr o ovo na frigideira
➔ Retirar o ovo
➔ Esquentar o óleo
➔ Esperar o ovo fritar
Pegar o Ovo Quebrar o Ovo
   
Aplicação: Escalonamento
➔ Pegar o ovo
➔ Untar a frigideira
➔ Quebrar o ovo
➔ Pegar o óleo
➔ Pôr o ovo na frigideira
➔ Retirar o ovo
➔ Esquentar o óleo
➔ Esperar o ovo fritar
Pegar o Ovo Quebrar o Ovo
Pôr o Ovo
na frigideira
   
Aplicação: Escalonamento
➔ Pegar o ovo
➔ Untar a frigideira
➔ Quebrar o ovo
➔ Pegar o óleo
➔ Pôr o ovo na frigideira
➔ Retirar o ovo
➔ Esquentar o óleo
➔ Esperaro ovo fritar
Pegar o Ovo Quebrar o Ovo
Pôr o Ovo
na frigideira
Pegar o Óleo
   
Aplicação: Escalonamento
➔ Pegar o ovo
➔ Untar a frigideira
➔ Quebrar o ovo
➔ Pegar o óleo
➔ Pôr o ovo na frigideira
➔ Retirar o ovo
➔ Esquentar o óleo
➔ Esperar o ovo fritar
Pegar o Ovo Quebrar o Ovo
Pôr o Ovo
na frigideira
Pegar o Óleo
Untar a 
frigideira
   
Aplicação: Escalonamento
➔ Pegar o ovo
➔ Untar a frigideira
➔ Quebrar o ovo
➔ Pegar o óleo
➔ Pôr o ovo na frigideira
➔ Retirar o ovo
➔ Esquentar o óleo
➔ Esperar o ovo fritar
Pegar o Ovo Quebrar o Ovo
Pôr o Ovo
na frigideira
Pegar o Óleo
Untar a 
frigideira
Esquentar
o Óleo
   
Aplicação: Escalonamento
➔ Pegar o ovo
➔ Untar a frigideira
➔ Quebrar o ovo
➔ Pegar o óleo
➔ Pôr o ovo na frigideira
➔ Retirar o ovo
➔ Esquentar o óleo
➔ Esperar o ovo fritar
Pegar o Ovo Quebrar o Ovo
Pôr o Ovo
na frigideira
Pegar o Óleo
Untar a 
frigideira
Esquentar
o Óleo
Esperar o 
Ovo Fritar
   
Aplicação: Escalonamento
➔ Pegar o ovo
➔ Untar a frigideira
➔ Quebrar o ovo
➔ Pegar o óleo
➔ Pôr o ovo na frigideira
➔ Retirar o ovo
➔ Esquentar o óleo
➔ Esperar o ovo fritar
Pegar o Ovo Quebrar o Ovo
Pôr o Ovo
na frigideira
Pegar o Óleo
Untar a 
frigideira
Esquentar
o Óleo
Esperar o 
Ovo Fritar
Retirar o Ovo
   
Aplicação: Escalonamento
Pegar o Ovo Quebrar o Ovo
Pôr o Ovo
na frigideira
Pegar o Óleo
Untar a 
frigideira
Esquentar
o Óleo
Esperar o 
Ovo Fritar
Retirar o Ovo
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33