Resolução dos Exercícios do dia 14/05/2003
Última alteração: 19/05/2003
Redator: Carlos R. Senna (022.248)
Nesta Ata estão as resoluções dos exercícios:
22.1-6 (pg. 422 [1])
22.2-6 (pg. 428 [1])
22.2-7 (pg. 428 [1])
22.1-6 Quando uma representação de matriz de adjacências é usada, a maioria dos algoritmos de grafos exige o tempo Ômega(V2 ) , mas existem algumas exceções. Mostre que detectar se um grafo orientado G contém um depósito universal – um vértice com grau de entrada |V| - 1 e grau de saída 0 – é uma operação que pode ser realizada no tempo O(V), dada uma matriz de adjacências para G.
Resolução: (apresentada pelo aluno Guilherme)
Um depósito universal (ou um sumidouro como foi chamado em aula), é um vértice onde todas as arestas chegam e nenhuma sai. A matriz de adjacências que representa um grafo que contém um sumidouro, terá a linha relativa a esse vértice totalmente preenchida com zeros e a coluna totalmente preenchida com uns, exceto na diagonal.
|
|
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
0 |
1 |
0 |
0 |
|
2 |
0 |
0 |
1 |
0 |
1 |
|
3 |
0 |
0 |
0 |
0 |
0 |
|
4 |
0 |
0 |
1 |
0 |
0 |
|
5 |
0 |
0 |
1 |
0 |
0 |
O algoritmo a seguir usa essa característica para encontrar o sumidouro.
SUMIDOURO(M, n)2 // Procura por um candidato a sumidouro 1 i <- 1 3 for j <- 1 to n do 4 if M(i, j) = 1 then 5 i <- j // candidato i falhou, tenta novo candidato j 6 // Verifica a coluna do candidato (diagonal = 0 resto = 1) 7 for k <- 1 to n do 8 if M(k, i) = 0 and k <> j then 9 return 0; // Não achou sumidouro 10 // Verifica a linha do candidato (totalmente preenchida com zeros) 11 for a <- 1 to n do 12 if M(i, a) = 1 then 13 return 0; // Não achou sumidouro 14 return i; // Posição do sumidouro
(Início) Existem dois tipos de lutadores: "bons sujeitos" e "maus sujeitos". Entre qualquer par de lutadores profissionais pode ou não haver uma rivalidade. Suponha que temos n lutadores profissionais e temos uma lista de r pares de lutadores para os quais existem rivalidades. Dê um algoritmo de tempo O(n + r) que determine se é possível designar alguns dos lutadores como bons sujeitos e os restantes como maus sujeitos, de tal forma que a rivalidade ocorra em cada caso entre um bom sujeito e um mau sujeito. Se for possível realizar tal designação, seu algoritmo devia produzi-la.
Resolução: (apresentada pelo aluno André)
A solução é baseada numa busca em largura num grafo onde cada profissional será um vértice, e a rivalidade uma aresta ligando os vértices. Ao longo da busca, os vértices são marcados com um estado (e[v]) que pode ser BOM ou MAU, sendo que cada vértice novo recebe o estado contrário ao de seu pai na árvore produzida pela busca. A origem da busca será "um bom sujeito". Caso uma aresta de retorno leve a um vértice do mesmo estado, não se pode fazer a atribuição.
BOMMAU( G )
1 for cada vértice u pertencente V[G] do 2 cor[u] <- BRANCO 3 e[u] <- NIL 4 5 for cada vértice s pertencente V[G] do 6 if cor[s] = BRANCO then 7 cor[s] <- CINZA 8 e[s] <- BOM 9 Q <- vazio 10 ENQUEUE(Q, s) 11 while Q <> vazio do 12 u <- DEQUEUE(Q) 13 if e[u] = BOM then 14 estado <- MAU 15 else estado <- BOM 16 for cada v <- Adj[u] do 17 if cor[v] = BRANCO then 18 cor[v] <- CINZA 19 e[v] <- ESTADO 20 ENQUEUE(Q, v) 21 else if e[u] = e[v] then 22 return FALSE 23 cor[u] <- PRETO 24 return TRUE
(Início)
22.2-7 O diâmetro de uma árvore T = (V, E) é dado por
max sigma(u, v); (onde sigma é a distância do caminho mais curto desde de u até v) u,v e V
isto é, o diâmetro é a maior de todas as distâncias de caminhos mais curtos na árvore. Forneça um algoritmo eficiente para calcular o diâmetro de uma árvore e analise o tempo de execução de seu algoritmo.
Resolução: (apresentada pelo aluno Bruno)
A solução proposta é usar o algoritmo BFS (pag. 423 [1]), a partir de qualquer vértice para encontrar o último vértice, e executar novamente BFS a partir desse vértice para encontrarmos o diâmetro da árvore.
Diâmetro = dBFS(G, dBFS(G,s)) usando a versão modificada abaixo.
dBFS(G, s)
1 for cada vértice u pertencente a V[G] - {s}
2 do cor[u] <- BRANCO
3 d[u] <- infinito
4 pi[u] <- NIL
5 cor[s] <- CINZA
6 d[s] <- 0
7 pi[s] <- NIL
8 Q <- vazio
9 ENQUEUE(Q, s)
10 while Q <> vazio
11 do u <- DEQUEUE(Q)
12 for cada v <- Adj[u]
13 do if cor[v] = BRANCO
14 then cor[v] <- CINZA
15 d[v] <- d[u] + 1
16 pi[v] <- u
17 ENQUEUE(Q, v)
18 cor[u] <- PRETO
19 return u;
Ficou pendente a prova sobre essa solução proposta. Uma solução parcial de Ricardo e Daniele segue.
Suponha, sem perda de generalidade, que o diâmetro da árvore seja a distância entre os nós u e v. Então, há 2 casos possíveis de ocorrer na escolha do nó inicial para se executar a 1ª BFS: 1º) esse nó escolhido estar nesse caminho entre u e v; 2º) esse nó escolhido não estar nesse caminho entre u e v;
No 1º caso: Seja s esse nó pertencente ao caminho u e v. Então ao rodar a BFS com raiz em s termos que o nó mais distante de s encontrado pela execução do alg. BFS será, ou o nó u, ou o nó v (já que eles são as extremidades de um caminho mais longo). Suponha que o nó v tenha sido o nó mais distante encontrado (ou seja, o caminho de s para v é maior ou igual ao caminho de s para u. Nota: o contrário também poderia ocorrer sem perda de generalidade). Logo, ao rodar uma segunda vez o BFS, agora considerando como raiz o nó v, será encontrado o caminho mais longo (caminho de v para u).
Prova: suponha que existisse um caminho mais longo de s para v (por exemplo, até um nó v'), então esse caminho seria o escolhido durante a execução da primeira BFS. Logo, estou dizendo que existe um caminho de s até v' que é maior do que o caminho de s até v. Logo, o caminho mais longo existente na árvore seria um caminho de u até v' o que contradizeria a minha hipótese de que um caminho mais longo é aquele entre os nós u e v ! Consequentemente, se eu der a sorte de selecionar um nó pertencente ao caminho mais longo, obrigatoriamente, na segunda vez que executar o BFS estarei executando-o sobre uma das folhas de um caminho mais longo da árvore !
No 2º caso: Seja s' um nó não pertencente ao caminho mais longo da árvore (caminho de u até v). Rodando o alg. de BFS com raiz em s' teremos a seguinte situação: um caminho de s' até s (um nó pertencente ao caminho mais longo) mais um caminho de s até u ou v. Consequentemente, a segunda execução da BFS iniciará em um nó folha pertencente ao caminho mais longo e encontrará o caminho mais longo da árvore.
Prova: Basta provar que um caminho com raiz em s CRUZARÁ o caminho mais longo (caminho u até v), pois a partir desse ponto (nó s) o caminho escolhido pela BFS será o mesmo do apresentado no 1º caso. Isso é verdade por definição no alg. BFS, já que em algum ponto o alg. de BFS com raiz em s' atingirá o nó s !
(Início)
[1] Livro Texto adotado:
Cormen, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos: teoria e prática. Tradução da 2ª edição americana Teoria e Prática. 2002.