G2-Distribuicao fisica

Prévia do material em texto

conceitos básicos
notação . G = (v , E)
↓
nós
↳ outras
outras
arcos
N : número
total de nós Grand (w) = número
de arestas
m : número total que o nó
arestas
possuí .
Soma dos graus = 2.m aresta paralela : duas aresta
que alugam o mesmo mar
m≤ nln - 1) / 2 de áreas
para grafo simples .
Matriz de adjacências
matriz NXN com Auv= 1- se 1mV ) Ú uma aresta .
→ Representações dos nós com suas arestas
/
* se tem nó =L
* se não , igual a zero
lista de adjacências
↳ lista de vizinhos de cada oártias
1 2 o 3 Ba
2
1- o 3 o 4 o 5 Vhs
3 1- ° 2 o 5 o 1- o 8 La
4 2 ° 5 LA
5 2 ° 3 o 4 o 6 Mg
6 5 24
+ 3 o 8 Me
8
3 o + Mh
matriz de incidência
→ Representação de uma matriz mata as arestas
→ dica : siga a ordem dos nós
, como 11,2 , 3 . .
. ) ou
( a
, b , C . . . )
uma coluna para cada aresta
↓
El
definição : um caminho é simples se todos os vértices
são distintos .
definição : um grupo não -orientado ú conexo
se para
cada par de Áreas m e v
,
existe um caminho
entre U e v
.
caso contrário
,
eu é desconexo :
L
/ \
conexo : E
1- /existe
caminho em
todos os nós .
Ciclo : quando
"
fecha
"
um caminho, e retornou
para o primeiro nó .
[ex : cicloÊ : I - 2 - a - 5 - 3- 1]
a distância entre vértices s e t em um grato ↳ é o
número de armas Écaminho mais curto
entre s e t em G.
e
número
destameia ( 1, a ) = z
de arestas !
distância (6,3 ) = 2
distância 17,8 ) = 1-
um grato navio orientado á uma
árvore se ú conexo e não contém nem acho .
Teorema : Seja ↳ um grato não orientado
com
N árticos . Quaisquer duas afirmações abaixo
implicam na ircrira
:
° G ú conexo
° ti não contém um ciclo
◦ G possuí n - 1- arestas
ponto de articulação : um área nú chamado de
ponto de articulação se quando
removido ( junto com suas
arestas adjacentes ) , aumenta
o
número do componentes
conexas de G.
definição : um grato completou aquele em que todos
os pares de árticos são adjacentes .
Algoutimos
◦ Díjkstrou : menor caminho entre 2 vértices .
condições de parada pode ser autuada para
encontrar o menor caminho de 1 oúrt.us
fonte fixo a todos os outros .
o Floyd : menor caminho entre Todos vértices .
Algorítimo de tsijkstra
S A B e D t
O L
,
X 1,0 1,8 1,0 tio
O 5,5 5,4 5,10 t
, X t
,
X
\ B O B ,
5 B
,
/ O B
,
9 B
,
o
→ + ^
A O Ait Af A
,
X → +5
C O 47 0,10 → +7
D DA → + +
t
5 a 7 7 9
atgohmo de Floyd
1º passo : construir a "matriz de distância "
-
A B e D
a
|
O •
_ .
. .
B
- - . O - .
_
.
}
→ se não houver
distância = O
À =
e . . . .
. O - _ .
D
-
- - - - - - O . .
matriz distância
2º posso calcular a matriz D+
.
-
A B e D
◦ }
mantém a coluna A , e
:| :BD =
e
a linha A w as de zero .
O temos que, = A u
-
verimar a condição :
dij > dikt dkj 4
sim , dit = dik + dfg
não
,
mantem - se
árvore geradora de custo mínimo
definição de árvore de cobertura mínima
* árvore geradora cuja soma do comprimento de seus
arcos é mínima em G (Nsa ) .
Algoritmos :
Plum : Ideal quando o número de arestas é
muito superior ao número de vértices ( gratos densos )
Kruskal : Ideal quando o número de arestas não
é muito alto ( grafos esparsos ) , o que costuma ser
o caso mais comum .
algoritmo de Pnim :
a árvore geradora é construída a partir de um
arco pelo acréscimo de novos arcos , aumentando - se
ahhrhescênáa inicial até que Odos os nós sejam
incluídos .
Passo 1- : Fixar um nó arbitrariamente e escolher
o arco de comprimento mínimo nele incidente que
o liga ao nó adjacente mais
próximo .
passo 2 : se Ídolos os nós da rede estiveremconectados
pare , caso contrário prossiga .
passo 3 : Identificar o nó que possa ser ligado
da norma mais econômica aos já
existentes na
ahbovuscêmeia , juntando o arco
correspondente
à formação . volte ao passo 2 .
7
A D
2
a
5 Obs : ligar
ç
2
° B a
T Todos os nós
+
3
de maneira
4 +
c
^
E
econômica,
sem se importar
A D
5
2 2 com ciclos !
O B 1
T
y
3
C
E
Algoritmo de Kruskaf
O algoritmo pode desenvolver várias arhourcên -
cias simultaneamente até que uma só árvore
inclua Todos os rios .
Algoritmo :
passo 1- : Ordenar por ordem vuercmtr os arcos
do genaro de acordo com as suas distâncias
.
nosso 2 : Tomar os primeiros n - 1 arcos que
não formam acho
, com os outros já escolhidos
na árvore , onde n é o número de nós .
O algoritmo Termina quando tiverem sido
selecionados os n - 1- arcos da árvore ou
quando Tuitarem sido examinados iodo os
arcos da rede .
Observação :
* Ordene as arestas
* Ordene as arestas de acordo c/ seus custos
* não pode formar ciclos
* tem que passar por todos os nós .
* outrorio de desempate ,
ordem crescente do
alfabeto .
a.6 7
A D
ato
52
42
ano T
1-
O
5 az B
7
aalz1-
4 as
ar
a}
art ^ E
C
ano 95 ao Art aa a} 97 AO az Am 92 ab
1- 1- 2 2 3 4 a 4 5 5 7 t
ato 7
A D
app
52
ora
42
ano T
O
5 az B
+
+
aalz
4 a} ar
a}
e
art ^ E
ano 95 ao Art aa a} 97 as az Am 92 ab
1- 1- 2 2 3 ^ a 4 5 5 7 t
✗ x x x x x
Ap - Aq - as _ aq _ ano _ aq
A D
gato
2
aq
2
ano T
1-
O ☐
aaiz1-
as
e
E
Função Objetivo :
- minimização dos custos totais de distribuiçãoincluindocustos puros ( capital dos oráculos , salários ,
despesas de linchamento , seguros , taxas ,
etc )
e custos variáveis ( custos do oráculo
dnemdintrs
da distância percorrida)
- minimização da distância total percorrida .
- minimização do número írotal de veículos
- maximização da punção de utilidade ( nível
de
serviço e/ou prioridades dos clientes ) .
método de Roteirização
heurística do vizinho mais próximo :
I - inicie em uma cidade qualquer
2- Repita
3- siga para a cidade
mais próxima
d- até que todas as cidades estejam
visitadas
5- Retorne à primeira cidade
Custo = 1- + 3 t 2 t 2 + 2 + 2 = 12
C + d t e t t t B + a