G rafos - FEUPrcamacho/cadeiras/cpa/acetatos/grafos-2.pdf · G rafos - 9 Execu o no grafo de exem...

Grafos 1

Grafos

❏ Grafo G = (V, E)• V — conjunto de vértices• E — conjunto de arestas (ou arcos)

cada aresta é um par de vértices (v, w), em que v, w ∈ V

se o par for ordenado, o grafo é dirigido, ou digrafo

um vértice w é adjacente a um vértice v se e só se (v, w) ∈ E

num grafo não dirigido com aresta (v, w) e, logo, (w, v) w é adjacente a v e v adjacente a w

as arestas têm por vezes associado um custo ou peso

1 2

3 4 5

6 7

1 2

3 4 5

6 7

G1= (Cruzamentos, Ruas) G2 = (Cidades, Estradas)

Grafos 2

Mais definições❏ caminho — sequência de vértices v1, v2, …, vn tais que (vi, vi+1) ∈ E, 1≤ i <n

• comprimento do caminho é o número de arestas, n1 se n = 1, o caminho reduzse a um vértice v1; comprimento = 0

• anel — caminho v, v ⇒ (v, v) ∈ E , comprimento 1; raro

• caminho simples — todos os vértices distintos excepto possivelmente o primeiro e o último

❏ ciclo — caminho de comprimento ≥ 1 com v1 = vn• num grafo não dirigido requerse que as arestas sejam diferentes

• DAG — grafo dirigido acíclico❏ conectividade

• grafo não dirigido é conexo sse houver um caminho a ligar qualquer par de vértices• digrafo com a mesma propriedade — fortemente conexo

• digrafo fracamente conexo — não fortemente conexo; grafo subjacente conexo❏ densidade

• grafo completo — existe uma aresta entre qualquer par de nós• grafo denso — |E| = Θ(V2)

• grafo esparso — |E| = Θ(V)

Grafos 3

Representação❏ matriz de adjacências

• a[u][v] = 1 sse (u, v) ∈ E• elementos da matriz podem ser os pesos (sentinelas indicam não aresta)• apropriada para grafos densos• 3000 cruzamentos e 12 000 troços de ruas (4 por cruzamento)

9 000 000 de elementos na matriz!

1 2 3 4 5 6 71 0 1 1 1 0 0 02 0 0 0 1 1 0 03 0 0 0 0 0 1 04 0 0 1 0 0 1 15 0 0 0 1 0 0 16 0 0 0 0 0 0 07 0 0 0 0 0 1 0

Grafos 4

Lista de adjacências❏ estrutura típica para grafos esparsos

• para cada vértice, mantémse a lista dos vértices adjacentes• vector de cabeças de lista, indexado pelos vértices• espaço é O(|E| + |V|)• pesquisa dos adjacentes em tempo proporcional ao número destes

❏ grafo não dirigido: matriz simétrica; lista com o dobro do espaço

21

2

3

4

5

6

7

34

54

6

6 37

74

6

Grafos 5

Ordenação topológica

• impossível se o grafo for cíclico• não é necessariamente única

(1 2 5 4 3 7 6) ou (1 2 5 4 7 3 6) no exemplo anterior❏ algoritmo simples:

descobrir um vértice sem arestas de chegada

imprimir o vértice

eliminálo e às arestas que dele saem

repetir o processo no grafo restante• Indegree(v) — é o número de arestas (w, v)

• passagem sequencial do vector é O(|V|); com |V| chamadas: tempo é O( |V|2 )

Ordenação dos vértices de um DAG tal que, se existe um caminho de v para w, então v aparece antes de w

Grafos 6

Versão ineficientevoid topsort()throws CycleFound{

Vertex v, w;for(int conta = 0; conta <= NUM_VERTEX; conta ++){

v = novo_Vertice_Indegree_Zero();if( v == null )

throw new CycleFound()v.topNum = conta;for each w adjacent to v

w.indegree;}

}

Grafos 7

Refinamento da ordenação topológica

❏ melhoria: em cada iteração, colocar numa fila (ou pilha) os vértices com indegree=0

• em cada passo, é retirado da fila um qualquer dos vértices presentes

• ao actualizar o indegree na lista de adjacências do vértice a eliminar colocamse na fila os que passam a ter indegree=0

• inicialização põe na fila os vértices com indegree=0 à partida

• tempo de execução O(|E| + |V|)

o corpo do ciclo de actualização do indegree é executado no máximo uma vez por aresta

as operações na fila são executadas no máximo uma vez por vértice

a inicialização leva um tempo proporcional ao tamanho do grafo

Grafos 8

Algoritmo refinado

void topsort ()throws CycleFound{

int counter = 0;Vertex v, w;Queue q;

q= new Queue();for each vertex vif ( v.indegree == 0 )

q.enqueue( v );

while( !q.isEmpty() ){

v = q.dequeue();v.topNum = ++counter;

for each w adjacent to vif( w.indegree == 0 )q.enqueue( w );

}if( counter != NUM_VERTEX )

throw new CycleFound(); }

Grafos 9

Execução no grafo de exemploindegree anterior a cada operação dequeue

Vértice 1 2 3 4 5 6 7

v1 0 0 0 0 0 0 0

v2 1 0 0 0 0 0 0

v3 2 1 1 1 0 0 0

v4 3 2 1 0 0 0 0

v5 1 1 0 0 0 0 0

v6 3 3 3 3 2 1 0

v7 2 2 2 1 0 0 0

enqueue v1 v2 v5 v4 v3,v7 v6

dequeue v1 v2 v5 v4 v3 v7 v6

Grafos 10

Caminho mais curto

Dado um grafo pesado G = (V, E) e um vértice s, obter o caminho pesado mais curto de s para cada um dos outros vértices em G

❏ Exemplo: rede de computadores, com custo de comunicação e de atraso dependente do encaminhamento (o caminho mais curto de v7 para v6 tem custo 1)

• arestas com custo negativo complicam o problema• ciclos com custo negativo tornam o caminho mais curto indefinido (de v4 a v7 o

custo pode ser 2 ou 1 ou 7 ou …)❏ Outro exemplo: se o grafo representar ligações aéreas, o problema típico poderá ser: Dado

um aeroporto de partida obter o caminho mais curto para um destino• não há algoritmo que seja mais eficiente

a resolver este problema do que a resolver

o mais geral

1 2

3 4 5

6 7

1

2

34

5

6

101

6

2

21

Grafos 11

1 Caminho não pesado

❏ pretendese o comprimento dos caminhos: pode ser visto como um caso particular em que o peso de cada aresta é unitário

• começase por marcar o vértice inicial s com comprimento 0• sucessivamente, passase aos que lhe estão adjacentes e marcamse com

mais 1 do que o valor do caminho até ao antecedente• progridese por níveis, passando ao nível seguinte só depois de ter

esgotado o anterior❏ este tipo de pesquisa em grafos designase por pesquisa em largura

• semelhante à travessia por níveis de uma árvore❏ código usa uma tabela em que regista, para cada vértice v

a distância de cada vértice ao inicial (dist)

se o vértice já foi processado (known)

qual o antecessor no caminho mais curto (path)

Grafos 12

Evolução da marcação do grafo

v1 v2

v3 v4 v5

v6 v7

v1 v2

v3 v4 v5

v6 v7

v1 v2

v3 v4 v5

v6 v7

0 0

1

1

0

1

1

2

2 v1 v2

v3 v4 v5

v6 v7

0

1

1

2

2

3

3

Grafos 13

Algoritmo básicovoid unweighted( Vertex s){

Vertex v, w;

s.dist = 0;for(int currDist = 0; currDist < NUM_VERTEX; currDist++)

for each vertex vif( !v.known && v.dist == currDist ){

v.known = true;for each w adjacent to v

if( w.dist == INFINITY ){

w.dist = currDist + 1;w.path = v;

}}

}

Grafos 14

Eficiência do algoritmo básico

❏ tempo de execução O(|V|^2), devido aos ciclos for encaixados❏ remoção da ineficiência semelhante à da ordenação topológica

• em cada momento, só existem dois tipos de vértices não processados com

Dist ≠ ∞ os do nível corrente (dist = currDist) ainda não processados e os

adjacentes a estes já marcados no nível seguinte

(dist=currDist+1)• podiam guardarse em duas caixas diferentes mas, como só se marca o

primeiro do nível seguinte depois de ter todos os do nível corrente, basta

usar uma fila• o atributo known não é usado nesta solução

Grafos 15

Algoritmo refinado

❏ tempo de execução é O(|E| + |V|), com grafo representado por lista de adjacências

void unweighted( Vertex s){

Vertex v, w;Queue q;

q= new Queue();q.enqueue (s); s.dist = 0;

while( !q.isEmpty() ){

v = q.dequeue();v.known = true; //agora desnecessáriofor each w adjacent to v

if( w.dist == INFINITY ){

w.dist = v.dist + 1;w.path = v;q.enqueue( w );

}}}

Grafos 16

Evolução da estrutura de dados

v

v1 0 ∞ 0 0 1 v3 1 1 v3 1 1 v3

v2 0 ∞ 0 0 ∞ 0 0 2 v1 0 2 v1

v3 0 0 0 1 0 0 1 0 0 1 0 0

v4 0 ∞ 0 0 ∞ 0 0 2 v1 0 2 v1

v5 0 ∞ 0 0 ∞ 0 0 ∞ 0 0 ∞ 0

v6 0 ∞ 0 0 1 v3 0 1 v3 1 1 v3

v7 0 ∞ 0 0 ∞ 0 0 ∞ 0 0 ∞ 0 Q v3 v6, v2, v4 v2, v4v1, v6

Início Visita v3 Visita v1 Visita v6 known dv pv known dv pv known dv pv known dv pv

Grafos 17


v

v1 1 1 v3 1 1 v3 1 1 v3 1 1 v3

v2 1 2 v1 1 2 v1 1 2 v1 1 2 v1

v3 1 0 0 1 0 0 1 0 0 1 0 0

v4 0 2 v1 1 2 v1 1 2 v1 1 2 v1

v5 0 3 v2 0 3 v2 1 3 v2 1 3 v2

v6 1 1 v3 1 1 v3 1 1 v3 1 1 v3

v7 0 ∞ 0 0 3 v4 0 3 v4 0 3 v4 Q v7 (vazia)v5, v7

Visita v4 Visita v5 Visita v7 Known dv pv Known dv pv Known dv pv Known dv pv

v4, v5

Visita v2

Grafos 18

2 Caminho pesado❏ a solução é uma modificação da anterior

• cada vértice mantém uma distância ao inicial, obtida somando pesos nos caminhos

• quando se declara um vértice known , exploramse os seus adjacentes; se o caminho através deste nó é melhor que o já registado, modificase este

• distância corrente em cada vértice: a melhor usando apenas vértices já processados

• o ponto crucial: escolher para declarar known o vértice que tiver o menor custo até ao momento

• é o único cujo custo não pode diminuir

• todas as melhorias de caminhos que usam este vértice são exploradas

❏ este é um exemplo de um algoritmo ganancioso: em cada passo faz o que melhora o ganho imediato

❏ restrição: só é válido se não existirem custos negativos

❏ registase o vértice antecedente, responsável directo pelo custo estimado; seguindo a sequência recuperase o caminho mínimo

Grafos 19

Estádios do algoritmo de Dijkstra

v1 v2

v3 v4 v5

v6 v7

42

10

6

1

5

13

24

8

2

v1 v2

v3 v4 v5

v6 v7

42

10

6

1

5

13

24

8

2

v1 v2

v3 v4 v5

v6 v7

42

10

6

1

5

13

24

8

2

v1 v2

v3 v4 v5

v6 v7

42

10

6

1

5

13

24

8

2

Grafos 20

Estádios do algoritmo de Dijkstra

v1 v2

v3 v4 v5

v6 v7

42

10

6

1

5

13

24

8

2

v1 v2

v3 v4 v5

v6 v7

42

10

6

1

5

13

24

8

2

v1 v2

v3 v4 v5

v6 v7

42

10

6

1

5

13

24

8

2

v1 v2

v3 v4 v5

v6 v7

42

10

6

1

5

13

24

8

2

Grafos 21


v

v1 0 0 0 1 0 0 1 0 0 1 0 0

v2 0 ∞ 0 0 2 v1 0 2 v1 1 2 v1

v3 0 ∞ 0 0 ∞ 0 0 3 v4 0 3 v4

v4 0 ∞ 0 0 1 v1 1 1 v1 1 1 v1

v5 0 ∞ 0 0 ∞ 0 0 3 v4 0 3 v4

v6 0 ∞ 0 0 ∞ 0 0 9 v4 0 9 v4

v7 0 ∞ 0 0 ∞ 0 0 ∞ 0 0 5 v4

Início Visita v1 Visita v4 Visita v2 known dv pv known dv pv known dv pv known dv pv

Grafos 22


v

v1 1 0 0 1 0 0 1 0 0 1 0 0

v2 1 2 v1 1 2 v1 1 2 v1 1 2 v1

v3 0 3 v4 1 3 v4 1 3 v4 1 3 v4

v4 1 1 v1 1 1 v1 1 1 v1 1 1 v1

v5 1 3 v4 1 3 v4 1 3 v4 1 3 v4

v6 0 9 v4 0 8 v3 0 6 v7 1 6 v7

v7 0 5 v4 0 5 v4 1 5 v4 1 5 v4

Visita v3 Visita v7 Visita v6 known dv pv known dv pv known dv pv known dv pv

Visita v5

Grafos 23

Algoritmo de Dijkstravoid Dijkstra( Vertex s){

Vertex v, w;

s.dist = 0;for( ; ; ){

v = vertice_a_menor_distancia;if( v == null )

break;v.known = true;for each w adjacent to v

if( !w.known )if v.dist + c(v,w) < w.dist ){ w.dist = v.dist + c(v,w);w.path = v;}

}}

Grafos 24

Análise do algoritmo❏ problema: pesquisa do mínimo

• método de percorrer a tabela até encontrar o mínimo é O(|V|) em cada fase; gastase O(|V|2) tempo ao longo do processo

• tempo de corrigir a distância é constante por actualização e há no máximo uma por aresta, num total de O(|E|)

• tempo de execução fica O(|E| + |V|2) = O(|V|2)

• se o grafo for denso |E| = Θ(|V|2) e o resultado é satisfatório pois corre em tempo linear no número de arestas

• se o grafo fôr esparso |E| = Θ(|V|), o algoritmo é demasiado lento❏ melhoria: manter as distâncias numa fila de prioridade para obter o mínimo

eficientemente O(log |V|), com uma operação deleteMin• como as distâncias vão sendo alteradas no processo e a operação de Busca é

ineficiente nas filas de prioridade, podese meter na fila mais do que um elemento para o mesmo vértice, com distâncias diferentes, e ter o cuidado, ao apagar o mínimo, de verificar se o vértice já está processado

O(|E| log |V|) actualização dos pesos com operação decreaseKey na filaO(|V| log |V|) percorrer os vértices com operação deleteMin para cada

Tempo de execução total: O(|E| log |V|)

Grafos 25

3 Arestas com custos negativos

❏ Algoritmo de Dijkstra não funciona• custo ao longo de um caminho não é monótono• depois de se marcar um vértice como processado pode aparecer um caminho mais

longo mas com custo inferior

❏ Combinar os algoritmos para os caminhos pesado e sem peso• usar uma fila; colocar o vértice inicial• em cada passo

retirar um vértice v da fila para cada vértice w adjacente a v tal que dist(w) > dist(v) + cost(v, w) ⇒ actualizar

dist(w), path(w) e colocar w na fila, se lá não estiver manter uma indicação de presença na fila

Grafos 26

Exemplo: custos negativos1 2

3 4 5

6 7

2

5

24

2

6

101

8

2

41

0

1

2

1 2

3 4 5

6 7

2

5

24

2

6

101

8

2

41

0

1

2

1 2

3 4 5

6 7

2

5

24

2

6

101

8

2

41

3

9 5

3

0

0

2

1 2

3 4 5

6 7

2

5

24

2

6

101

8

2

41

2

8 4

2

Achar os caminhosde menor custo acomeçar em 1.

Dijkstra vértice 2 nãoaltera nada …

seria necessário rever 4e propagar as alterações;piora o tempo …

pretendido:

Grafos 27

Algoritmo com custo negativo• pode ser necessário

processar cada vértice mais do que uma vez (max: |V|)

• actualização pode ser executada O(|E|.|V|), usando listas de adjacência

void weightedNegative( Vertex s){

Vertex v, w;Queue q;

q = new Queue();q.enqueue (s);while( !q.isEmpty() ){

v = q.dequeue();

for each w adjacent to vif v.dist + c(v,w) < w.dist )

{ w.dist = v.dist + c(v,w);w.path = v;

if(w not in q) )q.enqueue(w);

}}

}

• ciclo de custo negativo ⇒ algoritmo não termina

• teste de terminação: algum vértice sai da fila mais do que |V|+1 vezes

Grafos 28

4 Grafos acíclicos❏ simplificação do algoritmo de Dijkstra

• exigência de selecção, em cada passo, do vértice mínimo é dispensável• nova regra de selecção: usar a ordem topológica• um vértice processado jamais pode vir a ser alterado: não há ramos a entrar• não é necessária a fila de prioridade• ordenação topológica e actualização das distâncias combinadas numa só passagem

❏ aplicações em processos não reversíveis• não se pode regressar a um estado passado (certas reacções químicas)• deslocação entre dois pontos em esqui (sempre descendente)

❏ aplicações de Investigação Operacional• modelar sequências de actividades em projectos• grafos nóactividade

nós representam actividades e respectiva duração

arcos representam precedência (um arco de v para w significa que a actividade em w só pode ser iniciada após a conclusão da de v) ⇒ acíclico

Grafos 29

Grafos NóActividade

Qual a duração total mínima do projecto?

Quais as actividades que podem ser atrasadas e por quanto tempo (sem aumentar a duração do projecto)?

A(3)

D(2)

E(1)

C(3)

B(2)

F(3)

G(2)

K(4)

H(1)início fim

Nó: actividade e tempo associadoArco: precedência

Grafos 30

Reformulação em Grafo NóEvento

nó = evento

arco = actividade

• evento: fim de actividade

• reformulação introduznós e arcos extra para garantir precedências

6

5

4

7’

8’

9

10’1 6’

3

2

10

7

8

A/3

B/2

C/3

E/1

D/20

0

0

0

0

0

F/3

G/2

0

00

H/1

Nó: evento completar actividadeArco: actividade

K/4

Grafos 31

Menor Tempo de Conclusão

• menor tempo de conclusão ⇔ caminho mais comprido do evento inicial ao nó• problema (se grafo não fosse acíclico): ciclos de custo positivo• adaptar algoritmo de caminho mais curto• MTC(1) = 0

MTC(w) = max( MTC(v) + c(v,w) )(v, w) ∈ E

6

5

4

7’

8’

9

10’1 6’

3

2

10

7

8

A/3

B/2

C/3

E/1

D/20

0

0

0

0

0

F/3

G/2

0

00

H/1

MTC : usar ordem topológica

0

3

2 3 7

6

5

6

5

9

7

9 10

K/4

3

Grafos 32

Último Tempo de Conclusão

• último tempo de conclusão: mais tarde que uma actividade pode terminar sem comprometer as que se lhe seguem

• UTC(n) = MTC(n)UTC(v) = min( UTC(w) c(v w) )

(v, w) ∈ E

UTC : usar ordem topológica inversa

6

5

4

7’

8’

9

10’1 6’

3

2

10

7

8

A/3

B/2

C/3

E/1

D/20

0

0

0

0

0

F/3

G/2

0

00

H/10

3

2 3 7

6

5

6

5

9

7

9 10

K/4

3

0

3

4

6

6

5

6

7

9

9

9

9 104

valores calculados em tempo linear mantendo listas de adjacentes e de precedentes dos nós

Grafos 33

Folgas nas actividades

• folga da actividadefolga(v,w) = UTC(w)MTC(v)c(v,w)

6

5

4

7’

8’

9

10’1 6’

3

2

10

7

8

A/3/0

B/2/2

C/3/0

E/1/2

D/2/1

F/3/0

G/2/2

H/1/00

3

2 3 7

6

5

6

5

9

7

9 10

K/4/2

3

0

3

4

6

6

5

6

7

9

9

9

9 104

Caminho crítico: só actividades de folga nula (há pelo menos 1)

Grafos 34

Problemas de fluxo numa rede

Modelar fluxos conservativos entre dois pontos através de canais com capacidade limitada

1 Fluxo num arco não pode ultrapassar a capacidade

2 Soma das entradas num nó igual à soma das saídas

Exemplos• abastecimento de líquido

ponto a ponto• tráfego entre dois pontos

s: fonte; t: poço

distribuição de fluxo pelos arcos arbitrária, desde que respeite as setas

a b

dc

s

t

3 2

1

3 4 2

2 3

a b

dc

s

t

3 2

0

2 1 2

2 3

Grafos 35

Fluxo máximo: 1ª abordagem❏ algoritmo simples de aproximações sucessivas baseado em

• G ➤ grafo base de capacidades• Gf ➤ grafo auxiliar de fluxos

inicialmente fluxos iguais a 0 no fim, fluxo máximo

• Gr ➤ grafo residual (auxiliar) capacidade disponível em cada arco (= capacidade fluxo) capacidade disponível = 0 — eliminar arco saturado

❏ método de calcular o fluxo máximo entre s e t• em cada iteração, seleccionase um caminho em Gr entre s e t (de acréscimo) —

algoritmo não determinístico• valor mínimo nos arcos desse caminho = quantidade a aumentar a cada um dos

arcos respectivos em Gf• recalcular Gr• termina quando não houver caminho de s para t

Grafos 36

Exemplo: estado inicial

a b

dc

s

t

3 2

1

3 4 2

2 3

a b

dc

s

t

0 0

0

0 0 0

0 0

a b

dc

s

t

3 2

1

3 4 2

2 3

G Gf Gr

Grafos 37

Exemplo: 1ª iteração

a b

dc

s

t

3 2

1

3 4 2

2 3

a b

dc

s

t

0 2

0

0 0 2

0 2

a b

dc

s

t

3

1

3 4

2 1

G Gf Gr

Grafos 38


a b

dc

s

t

3 2

1

3 4 2

2 3

a b

dc

s

t

2 2

0

2 0 2

2 2

a b

dc

s

t

1

1

1 4

1

G Gf Gr

Grafos 39


a b

dc

s

t

3 2

1

3 4 2

2 3

a b

dc

s

t

3 2

0

2 1 2

2 3

a b

dc

s

t

1

1 3

G Gf Gr

Grafos 40

Algoritmo não garante fluxo óptimo❏ critério ganancioso de selecção do caminho: escolher o que dê maior fluxo

caminho s, a, d, t (3 unidades de fluxo) ➤ algoritmo termina sem obter o máximo

exemplo de algoritmo ganancioso que falha

a b

dc

s

t

3 2

1

3 4 2

2 3

a b

dc

s

t

3 0

0

0 3 0

0 3

a b

dc

s

t

2

1

3 1 2

2

Grafos 41

Algoritmo determinísticopermitir que o algoritmo mude de ideias

• para cada arco (v,w) com fluxo f(v,w) no grafo de fluxos acrescentase um arco (w,v) no grafo residual com capacidade f(v,w)

corresponde a deixar devolver fluxo para trás (nunca fica globalmente negativo, contra o arco)

podem existir arcos em sentidos opostos; podem existir ciclos• se as capacidades forem números racionais, o algoritmo termina com máximo• se as capacidades forem inteiros e o fluxo máximo f

bastam f estádios (fluxo aumenta pelo menos 1 por estádio) tempo de execução ( caminho mais curto não pesado ) é O(f. |E| ) ➤ mau

• evitar o problema escolher caminho que dá maior aumento de fluxo semelhante ao problema do caminho pesado mais curto (pequena alteração a Dijkstra) fluxo máximo em O(|E| log capMax) (capMax = capacidade máxima de um arco) cada cálculo de um aumento em O(|E| log |V|) (Dijkstra) global: O(|E|^2 log |V| log capMax)

Grafos 42

Solução óptima 1ª iteração

a b

dc

s

t

3 2

1

3 4 2

2 3

a b

dc

s

t

3 0

0

0 3 0

0 3

a b

dc

s

t

3 2

1

3 1 2

2 3

G Gf Gr

3

3 unidades de fluxo no caminho sadt

Grafos 43

Solução óptima 2ª iteração

a b

dc

s

t

3 2

1

3 4 2

2 3

a b

dc

s

t

3 2

0

2 1 2

2 3

a b

dc

s

t

3 2

1

3 3 2

2 3

G Gf Gr

1

2

2 unidades de fluxo no caminho s,b,d,a,c, t

Grafos 44

Caso difícil

s

a b

t

1

1 000 000

1 000 000

1 000 000

1 000 000

s

a b

t

1

1

1

s

a b

t

1

999 999

999 999

1 000 000

1 000 0001

1

s

a b

t

0

1

1

s

a b

t

1

999 999

999 999

999 999

999 9991

1

se se escolher passar sempre por a e por b…

1

11

1… temos 2 000 000 de iterações, em vez de 2!

Grafos 45

Árvores de expansão mínimas

Árvore que liga todos os vértices do grafo usando arestas com um custo total mínimo

• caso do grafo não dirigido

• grafo tem que ser conexo

• árvore ⇒ acíclico

• número de arestas = |V| 1

❏ exemplo de aplicação: cablamento de uma casa

vértices são as tomadas

arestas são os comprimentos dos troços

Grafos 46

Algoritmo de Prim❏ expandir a árvore por adição sucessiva de arestas e respectivos vértices

• critério de selecção: escolher a aresta (u,v) de menor custo tal que u já pertence à árvore e v não (ganancioso)

• início: um vértice qualquer

❏ idêntico ao algoritmo de Dijkstra para o caminho mais curto

• informação para cada vértice

dist(v) é o custo mínimo das arestas que ligam a um vértice já na árvore

path(v) é o último vértice a alterar dist(v)

known(v) indica se o vértice jé foi processado (isto é, se já pertence à árvore)

• diferença na regra de actualização: após a selecção do vértice v, para cada w não processado, adjacente a v, dist(w) = min{ dist(w), cost(w,v) }

• tempo de execução

O( |V|2 ) sem fila de prioridade

O( |E| log |V| ) com fila de prioridade

Grafos 47

Evolução do algoritmo de Prim

1 2

3 4 5

6 7

7

5

34

2

6

101

8

2

41

1 1

4

1 2

4

12

1 2

3 42

12

1 2

3 4

7

2

12

4

1 2

3 4

6 7

2

12

41

1 2

3 4 5

6 7

2

6

12

41

❶ ❷ ❸ ❹

❺ ❻ ❼

v known dist path1 1 0 02 1 2 13 1 2 44 1 1 15 1 6 76 1 1 77 1 4 4

últimatabela

Grafos 48

Algoritmo de Kruskal❏ analisar as arestas por ordem crescente de peso e aceitar as que não provocarem

ciclos (ganancioso)

❏ método

• manter uma floresta, inicialmente com um vértice em cada árvore (há |V|)

• adicionar uma aresta é fundir duas árvores

• quando o algoritmo termina há só uma árvore (de expansão mínima)

❏ aceitação de arestas — algoritmo de Busca/União em conjuntos

• representados como árvores

• se dois vértices pertencem à mesma árvore/conjunto, mais uma aresta entre eles provoca um ciclo (2 Buscas)

• se são de conjuntos disjuntos, aceitar a aresta é aplicarlhes uma União

❏ selecção de arestas: ordenar por peso ou, melhor, construir fila de prioridade em tempo linear e usar Apaga_Min

• tempo no pior caso O( |E| log |E| ), dominado pelas operações na fila

Grafos 49

Pseudocódigo (Kruskal)void kruskal(){

DisjSet s;PriorityQueue h;Vertex u, v;SetType uset, vset;Edge e,int edgesAccepted = 0;

h = readGraphIntoHeapArray();h.buildHeap();s = new DisjSet(NUM_VERTICES);

while(edgesAccepted < NUM_VERTICES 1 ){

e = h.deleteMin(); // e = (u,v)uset = s.find(u);vset = s.find(v);if (uset != vset) {

edgesAccepted++;S.union(uset, vset);

}}}

Grafos 50

Evolução do algoritmo de Kruskal

❶

❷ ❸

1 2

3 4 5

6 7

7

5

34

2

6

101

8

2

41

1 2

3 4 5

6 7

1 2

3 4 5

6 7

11 2

3 4 5

6 7

1

1

Grafos 51

Evolução do algoritmo de Kruskal

❹

❺ ❻

❼

1 2

3 4 5

6 7

7

5

34

2

6

101

8

2

41

1 2

3 4 5

6 7

2

1

2

1

1 2

3 4 5

6 7

2

1

2

41

1 2

3 4 5

6 7

1

2

1

1 2

3 4 5

6 7

2

6

1

2

41

Grafos 52

Pesquisa em profundidadevoid dfs( Vertex v ) //Depthfirst search

{

v.visited = true;

for each w adjacent to v

if( ! w.visited )

dfs( w );

}

Esquema básico da pesquisa em profundidade

❏ generalização da travessia em préordem

• começando num vértice v, processase v e depois atravessase recursivamente todos os vértices adjacentes a v

• executada numa árvore — visita sistemática de todos os vértices, tempo O(|E|)• executada num grafo arbitrário

— evitar os ciclos ➤ marcar os nós visitados para impedir a repetição

— grafo não dirigido/não conexo ou dirigido/não fortemente conexo: ficando vértices por visitar ➤ percorrer lista de nós até ao seguinte não marcado

Grafos 53

1 Grafos não dirigidos

A

B

C

D E

A

B

C

D E

❏ um grafo não dirigido é conexo ⇔ uma pesquisa em profundidade a começar emqualquer nó visita todos os nós

❏ começase por marcar A; 1º adjacente: B; recorre… ao processar (v,w), se w não estiver marcado acrescentase a aresta na árvore se já estiverem ambos marcados, acrescentase uma aresta de retorno (a ponteado)

que não pertence à árvore (todas as arestas do grafo estão na árvore total)❏ árvore simula a pesquisa; numeração em préordem pelas arestas da árvore dá a ordem de

marcação dos vértices

grafo árvore deexpansão emprofundidade

Grafos 54

2 Biconectividade

Grafo conexo não dirigido é biconexo se

não existe nenhum vértice cuja remoção torne o resto do grafo desconexo

❏ Aplicação rede com tolerância a falhas

❏ Pontos de articulação vértices que tornam o grafo desconexo (críticos)

❏ Algoritmo de detecção de pontos de articulação em tempo linear

• início num vértice qualquer

• pesquisa em profundidade, numerando os vértices ao visitálos — Num(v), em préordem

• para cada vértice na árvore de expansão calcular Low(v), o menor número de vértice que se atinge com zero ou mais arestas na árvore e possivelmente uma aresta de retorno (computável com travessia em pósordem)

Grafos 55

Pontos de articulação

❏ Cálculo de Low(v) primeiro para os filhos e depois para o pai

• arestas (v,w) são da árvore se Num(v) < Num(w); de retorno no caso inverso

• basta percorrer a lista de adjacências; O( |E| + |V| )

❏ Vértice v é ponto de articulação se tiver um filho w tal que Low(w) ≥ Num(v)

❏ A raiz é ponto de articulação sse tiver mais que um filho na árvore

❏ Low(v) é mínimo de• Num(v)• o menor Num(w) de todas as arestas (v,w) de retorno• o menor Low(w) de todos as arestas (v,w) da árvore

Grafos 56

Detecção de pontos de articulação

Pontos de articulação: C e D

AB

C D F

A,1/1

B,2/1

C,3/1

D,4/1 G,7/7

grafo árvores deexpansão emprofundidade

EG

E,5/4F,6/4

A,5/1

B,6/1

C,1/1

D,2/1 G,7/7

E,3/2F,4/2

v, Num(v)/Low(v)

Grafos 57

Três passagens?

• Num(v) — preordem

• Low(v) — posordem

• pontos de articulação — posordem combinados

// Atribui numero e calcula pai

// Contador global e inicializado a 1

void assignNum( Vertex v){

v.num = counter++;v.visited = true;for each w adjacent to v

if( !w.visited ){

w.parent = v;assignNum(w);

}}

// Atribui Low

// Testa Pontos de Articulação

void assignLow( Vertex v){

v.low = v.num; //regra 1for each w adjacent to v

if(w.num > v.num) //ramo árvore{

assignLow(w);if( w.low >= v.num )

System.out.println(v, “ Ponto de articulação”);

v.low = min(v.low, w.low); //regra 3}elseif ( v.parent != w ) //retorno

v.low = min(v.low, w.num); //regra 2}

Grafos 58

Uma só pesquisa em profundidade

Combina o préprocessamento e o pósprocessamento numa única passagem

// Procura Pontos de Articulação// Contador global e inicializado a 1 void findArt( Vertex v){

v.visited = true;v.low = v.num = counter++; //regra 1for each w adjacent to v

if( !w.visited ) //ramo árvore{

w.parent = v;findArt(w);if(w.low >= v.num )

System.out.println(v, “ Ponto de articulação”);

v.low = min(v.low, w.low); //regra 3}elseif ( v.parent != w ) //retorno

v.low = min(v.low, w.num); //regra 2}

Grafos 59

3 Circuitos de EulerPuzzle: desenhar as figuras abaixo sem levantar o lápis e sem repetir arestas; de

preferência, terminando no mesmo vértice em que iniciar.

Reformulação do problema em Teoria de Grafos: pôr um vértice em cada intersecção

Caminho de Euler: caminho que visita cada aresta exactamente uma vez

problema resolvido por Euler em 1736 e que marca o início da Teoria dos Grafos

Grafos 60

Solução❏ condição necessária

• circuito de Euler: número de arestas convergentes em cada vértice é par o ciclo entra tantas vezes em vértices quantas sai

• caminho de Euler: idem, excepto possivelmente em dois vértices o primeiro e o último; no caso de haver mais vértices com número

ímpar de arestas é impossível❏ condição suficiente

• se se verificarem as condições acima, então existe circuito (caminho) de Euler

❏ método: pesquisa em profundidade O(|E| + |V| )• principal problema: fazer um curtocircuito e deixar arestas de fora• correcção

procurar o primeiro vértice no caminho obtido que possua uma aresta não percorrida

lançar uma subpesquisa em profundidade inserir o resultado no caminho principal (usar lista ligada)

❏ Ciclo Hamiltoniano: ciclo simples que visita todos os vértices? (vêse depois)

Grafos 61

Exemplo de um circuito1

12

7

4 5

1198

2 3

10

6Grafo: existe caminho de Euler

1

12

7

4 5

1198

2 3

10

6Depois de fazer caminho5, 4, 10, 5

Grafos 62

Exemplo de um circuito1

12

7

4 5

1198

2 3

10

6Depois de fazer caminho5, 4, 1,3,7,4,11,10,7,9,3,4,10, 5

1

12

7

4 5

1198

2 3

10

6Depois de fazer caminho5, 4, 1, 3, 2, 8, 9, 6, 3, 7, 4, 11, 10, 7, 9, 3, 4, 10, 5

Grafos 63

4 Grafos dirigidos

❏ (também) atravessáveis em tempo linear por pesquisa em profundidade (serve para detectar se grafo é acíclico)

❏ problema: se não for fortemente conexo, pesquisa em profundidade pode não visitar todos os nós ⇒ recomeçar a pesquisa num nó não visitado (nova raiz…)

A B

D C

E

F

G

H

J I

Grafos 64

Árvore de expansão

❏ pesquisa em profundidade induz uma árvore/floresta de expansão

❏ para além das arestas genuínas da árvore, há arestas para nós já marcados

arestas de retorno para um antepassado — (A,B), (I,H)

arestas de avanço para um descendente — (C,D), (C,E)

arestas cruzadas para um nó não relacionado — (F,C), (G,F)

• alguns algoritmos necessitam de distinguir estas categorias de arestas

A

B

C F

D

E

H

J

I

G

Grafos 65

Componentes fortemente conexos❏ Método:

• pesquisa em profundidade no grafo G determina floresta de expansão, numerando vértices em pósordem

• inverter todas as arestas de G — Gr

• segunda pesquisa em profundidade, em Gr, começando sempre pelo vértice de numeração mais alta ainda não visitado

❏ cada árvore obtida é um componente fortemente conexo, i.e., a partir de um qualquer dos nós pode chegarse a todos os outros

❏ Prova• mesmo componente ⇒ mesma árvore de expansão

se dois vértices v e w estão no mesmo componente, há caminhos de v para w e de w para v em G e em Gr; se v e w não pertencerem à mesma árvore de expansão, também não estão no mesmo componente

• mesma árvore de expansão ⇒ mesmo componentei.e., há caminhos de v para w e de w para v ou, equivalentemente, se x for a raiz de uma árvore de expansão em profundidade, há caminhos de x para v e de v para x, de x para w e de w para x e portanto entre v e w

como v é descendente de x na árvore de Gr, há um caminho de x para v em Gr, logo de v para x em G; como x é a raiz tem o maior número de pósordem na primeira pesquisa; portanto, na primeira pesquisa, todo o processamento de v se completou antes de o trabalho em x ter terminado; como há um caminho de v para x, seguese que v tem que ser um descendente de x na árvore de expansão — caso contrário v terminaria depois de x; isto implica um caminho de x para v em G.

Grafos 66

Componentes fortemente conexos

A,3 B,6

D,2 C,4

E,1

F,5

G,10

H,9

J,8 I,7

Gr: obtido de G por inversão de todas as arestasNumeração: da travessia de G em pósordem

Grafos 67

Componentes fortemente conexos

A

B

C

F

D EH

J

I

G

Travessia em pósordem de GrComponentes fortemente conexos: {G}, {H, I, J}, {B, A, C, F}, {D}, {E}

G rafos - FEUPrcamacho/cadeiras/cpa/acetatos/grafos-2.pdf · G rafos - 9 Execu o no grafo de exem...

Documents

Transcript of G rafos - FEUPrcamacho/cadeiras/cpa/acetatos/grafos-2.pdf · G rafos - 9 Execu o no grafo de exem...