CT-234
Estruturas de Dados,
Dados
Análise de Algoritmos e
Complexidade Estrutural
Carlos Alberto Alonso Sanches
CT-234
9)) Algoritmos
g
em g
grafos
Tarjan, Dijkstra, Kruskal, Prim
Ideia de Tarjan
j (1972)
(
)
„
„
Durante a exploração em profundidade de um
digrafo numerar seus vértices de acordo com o
digrafo,
início e o término dessa exploração.
As diferentes situações permitem estabelecer uma
classificação dos arcos.
Exemplo
mp
expl:
p número de exploração
p
ç
Não visitado
Em exploração
comp: número de complementação
Terminado
E
4
1
6
5
A
F
D
B
1
6
A
D
2
4
7
E
8
C
B
8
3
5
2
H
C3
G7
F
H
G
Classificação
f ç dos arcos
„
Classificação do arco <v,u>:
„
„
„
„
Árvore (T): u ainda não havia sido
explorado, e será filho de v em T
(expl[u]=0)
A
Retorno (B): u é antecessor de v em
T, p
pois começou antes de v e ainda
está em exploração
(expl[u]<expl[v] e comp[u]=0)
Cruzamento (C): u está em outra
árvore ou sub-árvore, pois começou
antes de v e já foi explorado
(expl[u]<expl[v] e comp[u]>0)
Avanço (F): u é descendente de v
em T
T, pois começou depois de v e já
foi explorado
(expl[u]>expl[v] e comp[u]>0)
D
B
E
C
F
H
G
Algoritmo
Algor tmo de Tarjan
Tarjan(G) {
int ce = 0;
int cc = 0;
for v ∈ V {
expl[v] = 0;
comp[v] = 0;
}
for v ∈ V
if (expl[v] == 0)
DFST( )
DFST(v);
}
DFST(v) {
expl[v] = ++ce;
for <v,u> ∈ E
if (expl[u] == 0) {
tipo[<v,u>] = T;
DFST(u);
}
else if (expl[u] > expl[v])
tipo[<v,u>] = F;
else if (
(comp[u]
p[ ] > 0)
)
tipo[<v,u>] = C;
else tipo[<v,u>] = B;
comp[v] = ++cc;
}
Complexidade de tempo: Θ(n+m)
Exercício
„
„
Considere um grafo não orientado,
orientado sem laços
e sem arestas repetidas. Se aplicarmos nele
o algoritmo de Tarjan,
Tarjan somente haverá
arestas de árvore e de retorno.
Por que neste caso não existem arestas de
avanço e de cruzamento?
Teste de aciclicidade
„
„
„
Em certas aplicações
aplicações, como a ordenação
topológica, uma tarefa importante é o
reconhecimento de um digrafo acíclico
(conhecido como DAG).
A exploração
l
em profundidade
f d d d pode
d nos d
dar a
solução desse problema em tempo O(n+m).
Concretamente, basta uma variação do
algoritmo de Tarjan: se um arco de retorno for
encontrado durante a exploração, então o
digrafo será cíclico.
cíclico
Algoritmo
g
m
Aciclicidade(G)
( ) {
stack P;
bool aciclico = true;
int ce = 0;
int cc = 0;
for v ∈ V {
p [ ] = 0;
;
expl[v]
comp[v] = 0;
}
for v ∈ V
if (expl[v] == 0)
DFSA(v);
if (aciclico)
di
digrafo
f é acíclico
í li
else
digrafo é cíclico
}
DFSA(v) {
expl[v] = ++ce;
Arco de
push(P,v);
retorno
for <v,u>
,
∈ E
if (expl[u] == 0)
DFSA(u);
else
if (expl[u]<expl[v]
&& comp[u]==0) {
aciclico = false;
// ciclo está em P
// desde o topo até u
stop;
}
pop(P);
comp[v] = ++cc;
}
Ordenação
ç topológica
p g
„
Considere o DAG abaixo:
„
Vamos fazer
V
f
sua
exploração em
p
profundidade
dando prioridade
aos vértices de
menor valor..
m
Sequência de término
de exploração
Algoritmo
g
m
OrdemTopol(G)
O
d T
l(G) {
// supõe digrafo acíclico
int ce = 0;
int cc = 0;
for v ∈ V {
expl[v] = 0;
comp[v] = 0;
}
for v ∈ V
if (expl[v]
p
== 0)
DFSOT(v);
for v ∈ V
f[v] = n-comp[v]+1;
}
DFSOT(v)
DFSOT(
) {
expl[v] = ++ce;
for <v,u> ∈ E
if (expl[u] == 0)
DFSOT(u);
comp[v] = ++cc;
}
Usando uma pilha, seria
possível imprimir os
vértices jjá na ordem
topológica. Como?
Complexidade de tempo: Θ(n+m)
Bicoloração
ç de vértices
„
„
Vimos que um grafo G é bipartido
p
(ou bicolorido) quando existe uma
bipartição de seus vértices em subconjuntos disjuntos V1 e V2 tais que
qualquer aresta de G possui uma extremidade em V1 e outra em V2 .
Exemplo:
V1 = {0, 3, 4, 7, 10, 11}
V2 = {1, 2, 5, 6, 8, 9, 12}
„
„
„
É possível demonstrar que um grafo admite bicoloração se e somente
se não tiver ciclos de tamanho ímpar.
Uma simples variação no algoritmo de exploração em profundidade
permite encontrar uma bicoloração de um grafo, se existir.
O algoritmo
a gor tmo a segu
seguirr produz uma bicoloração
co oração (atr
(atribui
u “1” ou “2” ao
número de exploração de cada vértice) ou informa que o grafo não
pode ser bipartido.
Algoritmo
g
m
Ambos pseudocódigos retornam 0 se não existir bicoloração
TwoColor(G) {
for v ∈ V
expl[v] = 0;
for v ∈ V
if (expl[v] == 0)
if (DFSB(v,2) == 0)
return 0;
return 1;
}
DFSB(v,color)
S (
l ) {
c = (color % 2) + 1;
expl[v] = c; // troca cor
for <v
<v,u>
u> ∈ E
if (expl[u] == 0) {
if (DFSB(u,c) == 0)
return 0; }
else if (expl[u] == c)
return 0;
return 1;
}
Complexidade de tempo: O(n+m)
Componentes
mp
fortemente
f
m
conexas (SCC)
(
)
„
„
Ép
possível encontrar as componentes
p
fortemente conexas de
um digrafo através de uma variante do algoritmo de Tarjan.
Ideia:
„
„
„
„
Considere a árvore T de exploração em profundidade e a numeração
expl[v] para cada v ∈ V.
V
Os vértices que estão em exploração são empilhados (permanecerão
pilha até que
q seja
j encontrada a sua componente
p
conexa).
)
nessa p
Cada vértice v guardará CFC[v], que é o menor número de exploração
entre os vértices na pilha que atingir durante sua exploração. Desse
modo, ficará
á automaticamente associado a uma componente conexa.
Quando a exploração do vértice v terminar, se expl[v] = CFC[v] então
t d s oss vértices
todos
é ti s na pilha
ilh (desde
(d sd o ttopo até
té v)) pertencem
t
m a uma
m
mesma componente, e podem ser desempilhados.
Exemplo
mp
E
4
4 F
2
H
6
B
E
A
D
6
C
1
1
7
A
G
D 7
F
2
2
B
„
8
3
5
5
G 8
7
C 23
H
„
Importante: nem todos os
vértices de uma mesma
componente terminam com o
mesmo valor de CFC.
Exemplo: acrescente um arco
<C,A> nesse mesmo digrafo, e
visite <C,F> antes.
Algoritmo
g
m
TarjanCFC(G) {
stack P;
;
int ce = 0;
for v ∈ V
expl[v]
p
= 0;
for v ∈ V
if (expl[v] == 0)
DFSCFC(v);
}
DFSCFC(v) {
expl[v]
l[ ] = ++ce;
Arco de
d
árvore
push(P,v);
CFC[v] = expl[v];
f
for
<
<v,u>
> ∈ E
if (expl[u] == 0) {
DFSCFC(u);
CFC[v] = min{CFC[v]
min{CFC[v],CFC[u]};
CFC[u]};
}
else if (u ∈ P)
CFC[v] = min{CFC[v]
min{CFC[v],expl[u]};
expl[u]};
if (CFC[v] == expl[v])
do {
Teste em tempo
x = top(P);
constante
t t com
pop(P);
vetor de flags
} while (x != v);
}
Complexidade de tempo: Θ(n+m)
Vértices de corte
„
„
Uma variante do algoritmo de Tarjan pode encontrar os
vértices
é i
d
de corte ((ou pontos d
de articulação)
i l ã )d
de um grafo
f
G=(V,E) conexo não-orientado, sem laços ou arestas repetidas.
Ideia:
„
Desse modo, se fizéssemos uma exploração em profundidade a
partir de cada vértice do grafo, poderíamos identificar todos os
vértices de corte (no entanto, há outra solução mais eficiente)
Considere a árvore T de exploração em profundidade e a numeração
expl[v]
l[ ] para cada
d v ∈ V.
V
„
Raiz: será vértice de corte se tiver pelo menos dois filhos em T.
„
Demais vértices:
„
„
„
v será vértice de corte se tiver algum filho sem retorno para nenhum dos ancestrais
de v.
É calculado
l l d m[v]
[ ] = mín{
í { expl[v],
l[ ] expl[x]
l[ ] }}, onde
d x é um vértice
é ti que v ((ou um d
de seus
descendentes) atinge em T através de uma única aresta de retorno.
Portanto, v será vértice de corte se tiver algum filho u tal que m[u] ≥ expl[v].
Exemplo
mp
F
4
4
1
D
1
6
A
6
1
B
1
1
A
H
2
12
3
7
1
C
D
3
5
1
3
7
B
5
2
6
4
8
C
1
1
G 8
13
E
E
5
F
1
5
7
H 3
8
C e H são vértices de corte
G
8
Algoritmo
Algor tmo
TarjanVC(r) {
DFSVC(v) {
// válido se for conexo e
expl[v] = ++ce;
// não tiver laços ou
m[v] = expl[v];
// arestas repetidas
for <v,u> ∈ E
int ce = 0;
;
if (expl[u] == 0) {
for v ∈ V {
pai[u] = v;
Trata
as
arestas
de
expl[v] = 0;
nfilhos[v]++;
retorno, tanto na ida
pai[v] = null;
DFSVC(u);
como na volta
nfilhos[v] = 0;
m[v] = min{m[v],m[u]};
VC[v] = false;
}
}
else // arestas de retorno
DFSVC(r);
if(u != pai[v])
VC[r] = (nfilhos[r] > 1);
m[v] = min{m[v],expl[u]};
for v ∈ V-{r} {
}
p = pai[v];
VC[p] = VC[p] || (m[v]>=expl[p]);
}
Complexidade
p
de tempo:
p Θ(n+m)
(
)
f
for
v ∈ V
if (VC[v]) v é vértice de corte;
}
Arestas de corte
„
A identificação das arestas de corte (ou pontes) é
realizada de maneira semelhante:
„
„
„
Encontrar uma árvore
á
de exploração T, calculando as
mesmas numerações expl e m para os vértices.
É fácil constatar que nenhuma aresta de retorno dessa
exploração pode ser de corte.
Uma aresta <v,u> є T será de corte se m[u] = expl[u].
No exemplo
mp anterior
F
4
4
1
D
1
6
A
6
1
B
1
1
A
H
2
12
3
7
1
C
D
3
5
1
3
7
B
5
2
6
4
8
C
1
1
G 8
13
E
E
5
F
1
5
7
H 3
8
<C,E> e <H,G> são arestas de corte
G
8
Algoritmo
TarjanAC(r) {
// válido se for conexo e
// não
ã ti
tiver l
laços ou
// arestas repetidas
int ce = 0;
for v ∈ V {
expl[v] = 0;
pai[v] = null;
}
DFSAC(r);
}
DFSAC(v) {
expl[v] = ++ce;
m[v] = expl[v];
for
o <v,u>
,u ∈ E
if (expl[u] == 0) {
pai[u] = v;
DFSAC(u);
m[v] = min{m[v],m[u]};
if (m[u] == expl[u])
<v,u> é aresta de corte;
}
else // arestas de retorno
if(u != pai[v])
m[v] = min{m[v],expl[u]};
}
Complexidade de tempo: Θ(n+m)
Caminhos
m
mais
m
curtos
„
„
„
„
Um digrafo
g
G=(V,E), onde V = {v1, v2, ..., vn}, é chamado de
ponderado se cada arco (vi, vj) ∈ E tem um custo cij.
Distância entre dois vértices é a somatória dos custos dos
arcos de um caminho que os une.
Um problema clássico em grafos é encontrar o caminho mais
curto ou a distância mínima entre dois vértices.
E
Exemplo:
l
B
2
8
5
C
D
4
4
F
I
2
4
4
7
H
4
4
5
A
E
6
5
2
4
2
G
4
J
K
Distância mínima
entre A e K:
7+2+2+5 = 16
Uma
m condição
ç de existência
„
Considere o caminho abaixo entre i e j, e o ciclo w :
k
j
i
w
„
„
Se o comprimento de w for negativo, qual seria a distância
mínima entre i e j ?
Uma condição de existência para o caminho mais curto é que
seja elementar, isto é,
é sem ciclos em seu interior.
Grafos
f com
m arestas de mesmo
m m peso
p
„
„
„
Quando todas as arestas
têm pesos iguais, basta uma
p
alteração
ç na
simples
exploração em largura.
Afinal, os vértices vão sendo
Afinal
enfileirados seguindo a
ordem de proximidade:
portanto, basta incrementar
a distância do vértice
antecessor
antecessor.
O algoritmo de Dijkstra
generaliza
l
essa ideia.
d
BFSMinCam(r) {
q
queue q
q;
int ce = 0;
for v ∈ V - {r} {
d[v] = +∞;
expl[v] = 0;
}
expl[r] = ++ce;
d[r] = 0;
enqueue(q,r);
while (!isEmpty(q)) {
u = dequeue(q);
for <u,v> ∈ E {
if (expl[v] == 0) {
expl[v] = ++ce;
d[v] = d[u] + 1;
enqueue(q,v);
}
}
}
}
Exemplo
mp do algoritmo
g
m de Dijkstra
j
+∞
+∞
4
4
4
7
+∞
5
2
2
+∞
5
7
1
0
1
5
1
2
3
3
6
7
2
+∞
1
4
4
5
2
1
0
1
5
1
+∞
2
0
3
1
6
7
5
2
1
5
1
2
3
3
1
+∞
8
5
5 3
7
1
0
5
1
3
1
5
2
5
2
2
1
2
3
7
8
4
4
4
6
68
4
5
2
5
5
2
3
7
1
0
1
5
1
2
7
4
5
2
5 3
7
3
3
1
6
8
7
8
8
4
5 3
7
1
3
4
65
2
3
+∞
5
7
6
7
8∞
+∞
6
6
1
0
1
5
1
2
3
3
1
7
6
6
Algoritmo
g
m de Dijkstra
j
(1959)
(
)
Dijkstra(u) {
for v ∈ V – {u}
d[v] = +∞;
d[u] = 0;
S ← V;
\\ vértices com distância indefinida
while S ≠ ∅ {
selecionar j tal que d[j] == mini∈S{d[i]};
S ← S – {j}; \\ j passa a ter distância definida
for <j,w> ∈ E, onde w ∈ S
if (d[w] > d[j] + cjw) {
d[ ] = d[j] + cjw;
d[w]
pred[w] = j;
}
}
Predecessor: permite encontrar os
vértices presentes nesse caminho
Assemelha-se a uma exploração em largura
Complexidade
mp
de tempo
mp
„
„
„
Grosso modo, o algoritmo
g
de Dijkstra
j
g
gasta tempo
p
O(n2+m) = O(n2).
No entanto
N
t t é possível
í l melhorar
lh
essa complexidade
l id d
se o conjunto S for implementado com um heap de
mínimo.
í i
Nesse caso,
caso o tempo passaria a ser O((n
O((n+m)
m).log
log n):
„
„
O heap possuirá inicialmente n elementos.
No total, são realizadas n extrações de mínimo e até m
modificações de valor (será preciso manter um vetor
auxiliar que armazena a posição corrente que cada vértice
ocupa no heap).
Arcos com
m custos negativos
g
„
No grafo abaixo,
a a o, qua
qual a distância
stânc a m
mínima
n ma entre
ntr os vértices
rt c s A
C
e C?
3
A
-8
10
„
„
„
B
O algoritmo de Dijkstra daria como resposta 3,
3 mas o valor
correto é 2... Por que isso acontece?
No processo d
N
de construção
t
ã d
do caminho
i h mínimo,
í i
o algoritmo
l
it
de Dijkstra supõe que o custo acumulado sempre cresce. Isso
não ocorre se admitirmos arcos com custos negativos...
negativos
Em um algoritmo mais geral, cada vez que se altera a
distâ i até
distância
té um vértice,
é ti
também
t bé deve
d
sser recalculada
l l d a
distância até todos os seus adjacentes.
Algoritmo
g
m de Dijkstra
j
modificado
m f
Dijkstra2(u) {
for v ∈ V – {u}
d[v] = +∞;
d[u] = 0;
S ← {u};
{ }
while S ≠ ∅ {
selecionar j ∈ S;
S ← S – {j};
for <j,w> ∈ E
if (d[w] > d[j] + cjw) {
d[w]
d[
] = d[j] + cjw;
pred[w] = j;
S ← S ∪ {w};
\\ w volta para S
}
}
„
Com uma estrutura adequada para S,
S a complexidade de
tempo desse algoritmo pode ser o(n.m).
Árvore geradora
g
de custo mínimo
m m (MST)
(
)
„
„
„
Dado um grafo G=(V
G=(V,E),
E) conexo e ponderado
ponderado, com
custo associado c(e), e ∈ E, deseja-se encontrar um
subgrafo T tal que:
„
seja gerador de G (isto é, possua todos os vértices);
„
seja acíclico e conexo (isto é, uma árvore);
„
t h custo
tenha
t total
t t l c(T)
(T) = Σe∈Ec((e) que seja
j mínimo.
í i
T também
m m costuma
m ser chamado
m
de árvore de
espalhamento de custo mínimo.
Este
E
t conceito
it poderia
d i ser generalizado
li d para um grafo
f
desconexo...
Exemplo
mp
4
A
B
9
5
4
3
E
8
F
2
2
7
D
C
9
4
A
A
5
4
3
4
B
E
8
F
B
4
3
E
2
F
2
D
C
Árvore geradora
Á
d
com custo 24
D
C
Árvore geradora
Á
com custo 15
Ideia de Kruskal (1956)
(
)
„
„
Princípio: a aresta de menor custo sempre pertence
à árvore geradora de custo mínimo.
Demonstração:
„
„
„
„
Suponha, por absurdo
Suponha
absurdo, que a aresta de custo mínimo não
esteja na solução ótima.
A inserção
i
ã desta
d
aresta na solução
l ã ótima
ó i
gera um ciclo.
i l
Removendo-se a aresta de maior custo neste ciclo (que
(q
não é a inserida), obtém-se uma nova árvore geradora.
Essa nova árvore tem um custo inferior à solução ótima
inicial: contradição.
Exemplo
mp
4
B
C
4
6
7
A
Lista
ordenada
d
d
3
D
8
M
5
4
J
6
H
7
G
1
E
4
I
3
2
L
2
3
2
F
( )=7
3
10
20
c(T)
1
5
13
16
24
Componentes
{ A{{}AA
{{}A}A,
{ }A,
BB
{{}B
B,
}B
{ }B}C,
{ }C{D,
{C,
}{ CC,
E,
{D,
}C,
{F,
D,
{D
D,
E,
D,
D,
G,
E,
}{E
L,
E,
D,
E,
J,
L,
}F,
{LL
E,
LF,
EG,
}{}}L
}G,
FJ}}{J}{F}F} }
{{GF,{}J
F, }G,
{ HJ{}}G
H
{ H,
} { {I H
{}{ H
I} }}{ J
M
{ {I}{}}M
I }}{{ L
{MM
{}}M} }{ M }
e
c(e)
((D,E)
, )
1
(D,L)
2
(F,J)
2
(G,J)
2
(C,D)
3
(E,F)
3
(H,I)
3
(A,B)
4
(B,C)
4
…
…
Exemplo
mp
4
B
C
4
6
7
A
Lista
ordenada
d
d
3
D
8
M
5
4
J
6
H
7
G
1
E
4
I
3
2
L
3
2
2
F
c(T)
(T)
( ) = 33
24
28
Componentes
{ {A,A,B,B,C,C,D,D,E,E,F,F,G,
G,H,J,I,LJ,} L }
{ A, B, C, D, E, F, G, H, I, J, L, M }
{ H, I }{ M }{ M }
e
c(e)
...
...
(A,I)
4
(J,L)
X
4
(G,M)
5
(C,M)
6
(I,J)
6
(A,M)
7
(G,H)
7
(B,L)
8
Algoritmo
g
m de Kruskal
Kruskal(G) {
T ← ∅;
∅
A ← vetor com as arestas em ordem crescente de custo;
criar n componentes com os n vértices isolados;
f
for
(i
(i=1;
1 i<
i<=m && |T|<n-1;
|T|< 1 i++) {
<u,v> = A[i];
if (u e v não estão na mesma componente) {
T ← T ∪ {<u,v>};
unir as componentes que contêm u e v;
}
}
}
„
Operações
p r ç
executadas:
u
„
Ordenação de m valores
„
2m testes de componentes
„
n-1 uniões de componentes
Complexidade
mp
de tempo
mp
„
„
„
Implementação simples: utilizar um vetor de
tamanho n que indica a componente de cada vértice.
Tempo gasto:
„
Ordenação dos custos: O(m
O(m.log
log m)
„
2m testes de componentes: O(m)
„
n-1 uniões de componentes: O(n2)
T t l O(m.log
Total:
O( l m + n2)
Estrutura de dados específica
p f
„
„
„
„
„
Os vértices de cada componente são colocados em uma
estrutura de árvore e representados pela raiz.
Deste
D
st modo,
m d na
n união
niã d
de componentes,
mp n nt s a raiz
i d
da á
árvore
mais baixa torna-se filha da raiz da árvore mais alta.
Encontrar a componente de um vértice corresponde a
percorrer o caminho dele até sua raiz.
Na procura da componente de um vértice, aproveita-se o
percurso para que depois todos apontem para a raiz.
Pode-se demonstrar que as alturas dessas árvores
permanecem O(log
p
( g n).
) Na verdade,, é bem inferior a isso...
Complexidade
mp
de tempo
mp
„
„
Com essa estrutura específica:
„
Ordenação dos custos: O(m.log m)
„
2m testes de componentes: O(m.log n)
„
n-11 uniões
iõ d
de componentes:
t
Θ( )
Θ(n)
Total: O(m.log
(m g m), supondo
p
m > n.
Ideia de Prim
m (1957)
(
)
„
Inicialmente T será um vértice arbitrário de G
Inicialmente,
G.
„
Critério de inclusão de vértices e arestas em T:
„
„
„
„
Dentre todas as arestas de G incidentes em T, escolhe-se a
menor
nor custo.
de m
Essa nova aresta e seu vértice adjacente serão incluídos
em T somente se esse novo vértice ainda não estiver em T.
T
O processo termina quando T ficar com n vértices.
É preciso utilizar uma estrutura de dados que
armazene em ordem crescente de custo os vértices
ainda não incluídos na árvore.
Exemplo
mp
4
B
C
4
6
7
A
3
D
8
M
5
4
J
6
H
7
1
E
4
I
3
2
L
G
c(T) = 8
4
12
14
17
19
21
25
28
33
11
2
3
2
F
Algoritmo
g
m de Prim
m
Prim(r) {
T ← ∅;
\\ árvore de espalhamento de custo mínimo
U ← {r};
\\ vértices que já estão na árvore
while (U ≠ V) {
<u,v> = aresta de custo mínimo | u∈U e v∈V-U;
T ← T ∪ {<u,v>}; \\ aqui, T contém só arestas
U ← U ∪ {v};
}
}
„
C
Com
h
heap
d mínimo,
de
í i
pode
d ser iimplementado
l
t d em ttempo O((
O((n+m).log
) l n):
)
„
„
„
O heap possuirá apenas os vértices vizinhos da árvore em construção, cada um
com sua distância corrente ((começará
ç
com o vértice r,, com distância nula).
)
Quando um vértice é retirado desse heap, modificam-se as distâncias que seus
vizinhos têm em relação à árvore (será preciso manter um vetor auxiliar que
armazena a posição corrente de cada vértice no heap).
)
No total, são realizadas n extrações de mínimo e até m modificações de valor.
Outros p
problemas
m em
m grafos
g f
„
Vimos algumas resoluções algorítmicas eficientes de
determinados problemas em grafos.
„
„
Teste de planaridade: também pode ser realizado em tempo polinomial no
tamanho
h do
d grafo:
f algoritmos
l
i
APG
PG (Auslander,
(
l d
P
Parter e Goldstein)
G ld
i ) e LEC
(Lempel, Even e Cederbaum), com suas diferentes implementações
No entanto
entanto, na teoria de grafos há ainda muitos problemas
importantes que são intratáveis, ou seja, se desconhecem
ç
de tempo
p polinomial:
p
resoluções
„
Clique máximo
„
Coloração
„
Caixeiro viajante
„
Cobertura de vértices
„
Conjunto de vértices dominantes
„
etc.
Exercícios
„
Simular (e implementar) em diversos grafos
grafos:
„
Variantes do algoritmo de Tarjan:
„
Cl ifi
Classificação
ã de
d arcos
„
Teste de aciclidade
„
Ordenação topológica dos vértices
„
Bicoloração dos vértices
„
Determinação de componentes fortemente conexas
„
Identificação de vértices e arestas de corte
„
Algoritmo de Dijkstra (com custos não negativos)
„
Algoritmo de Kruskal
„
Algoritmo de Prim