Aula número 4 - 10/10/2000
Maria da Piedade Rafael Ferradeira
Conteúdos trabalhados na aula:
- Exemplo
Applet para Ordenação
Toplógica
Um DAG é um grafo direccionado acíclico ,ou seja, orientado sem ciclos.
Um grafo dirigido G = (V,E) é acíclico se uma travessia em profundidade de G não indica nenhum arco para trás.
Vejamos o exemplo de um DAG:
Se considerarmos uma árvore onde a raiz corresponde a um vértice só com saídas e as folhas a vértices só com entradas, podemos verificar que neste caso não estamos na presença de uma árvore porque um filho pode ter vários pais (exemplo: como acontece com o vértice 5). Também não é exactamente um grafo pois não contém ciclos. Assim, podemos dizer que um DAG é qualquer coisa entre uma árvore e um grafo, que pode também, conter pesos (no exemplo: X0, X1, X2, ......).
Os DAG podem representar:
Pré-requisitos
Jogos
Os DAG podem ser ordenados utilizando a topologia associada:
Por exemplo:
As redes de actividades não podem ter ciclos, pois o que se pretende é criar uma rede onde cada tarefa deve executar-se sempre até ao fim. Por essa razão utilizam-se os DAG para criar uma rede de actividades. Passemos então a uma exemplo prático, para melhor compreender do que se trata.
Exemplo: Temos então uma rede de actividades num processo industrial. Podemos representá-la da seguinte forma:
Estamos agora na presença de um DAG, o qual representa um processo industrial onde cada actividade é representada por um vértice (A1, A2,...,A7), e os pesos correspondem ao tempo necessário para executar uma tarefa(2h, 1h, 4h,...). Desta forma, não é possível começar uma nova tarefa sem que a tarefa que lhe precede esteja terminada. Por exemplo, se quisermos chegar à tarefa A7 precisamos de 3 entradas (*) e o tempo necessário para o fazer será 3h. Importa assim referir que para uma fase ser activa, precisamos sempre do peso máximo e não do peso mínimo. Como podemos observar no DAG anterior, o peso máximo para chegar à actividade A7 é 11 (caminho a vermelho), ou seja, é a soma dos pesos desde a source até à folha, a qual chamamos de caminho crítico.
Imaginemos que temos uma expressão matemática:( ( ( x + y ) * ( a - b ) ) / ( ( x + y ) * ( c - d ) ) ), dentro de um ciclo, o compilador não vai estar a construir a expressão inteira a cada iteração. Para isso vai construir uma árvore onde a cada iteração apenas mudam as folhas, ou seja cria uma árvore de avaliação para todos os valores.
A função prefixa da árvore ficará da seguinte forma: / * * + x y - a b + x y - c d O que dará origem à seguinte árvore:
O DAG pode ser utilizado para optimizar esta árvore, indo buscar o eixo do fluxo máximo:
A ordenação topológica consiste em ordenar os vértices de um grafo acíclico G=(V,E) de forma que, se existe um caminho do vértice v para o vértice u, então v aparece antes de u na ordenação. De notar que uma ordenação topológica não é única e que ela não é possível se o grafo possuir ciclos.
Um exemplo comum de problemas de ordenação topológica, é a confecção de dicionários, onde desejamos que uma palavra B cuja definição dependa da palavra A, apareça depois de A no dicionário.
Uma forma simples de resolver esse problema é a utilização de uma versão do algoritmo de busca em profundidade que imprime o vértice antes de retornar a chamada. Obteremos assim os vértices em ordem topológica invertida:
Para verificar que esse algoritmo funciona, é só ver o que acontece quando chega ao final de uma recursão, no momento que ele imprime o vértice. Nesse caso, ele já foi o mais longe possível a partir do vértice inicial (isso é uma característica do algoritmo de busca em profundidade). Seja x o último vértice desse caminho. Não existe vértice v tal que x<v, porque se for o caso o algoritmo continuaria a busca no mínimo até v . Portanto, de todos os próximos vértices que serão imprimidos, nenhum sucede a v na ordem, e obteremos uma ordem topológica invertida.
Vamos então fazer a ordenação topológica do seguinte DAG:
Vamos executar o algoritmo DFS, o que nos dará a ordem de visita de cada vértice:
O objectivo é rescrever o DAG de forma linear, de maneira a termos os arcos todos na mesma direcção:
Há que ter em atenção que a ordenação topológica não é única, existe mais de uma forma de escrever um grafo por ordem topológica. No entanto, para realizarmos o algoritmo vamos ter que usar o DFS, sendo o resultado armazenado numa lista.
Algoritmo:
Para n vértices, qual será o tempo necessário para fazer o DFS em função de n?
R: Para todos os vértices (n), temos que verificar todos os arcos (x). Assim, a complexidade é n + x.
No pior caso, a complexidade são combinações de n 2 a 2 :
Caminho crítico (Tempo máximo)
Peso do caminho crítico (caminho máximo da entrada até à saída):
Explicação do max:
Por exemplo:
Para um nó u, o T(u) é definido como: max (t (v) + t (v -> u), ou seja:
max ( T(v1) + peso (u, v1), T(v2) + peso (u, v2), T(v3) + peso (u, v3))
O seguinte applet permite construir um DAG fazendo os nós e as respectivas ligações entre eles.
Este applet encontra-se disponível no seguinte endereço:
http://www.educa.fmf.uni-lj.si/www375/2000/Algoritmi/Java-examples/GraphD/GraphD.html
Outro applet disponível, sobre ordenação topológica:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic30/#JavaApplet
