Caminho crítico

                   

Considere que tenhamos uma rede R(V,A), ou seja, um grafo orientado, sem laços e valorado, que contém exatamente uma fonte e um sumidouro. Nesta rede, os vértices representem eventos, os arcos representem atividades e os valores associados aos arcos representem a duração das atividades.

A disposição dos eventos (vértices) e das atividades (arcos) no grafo exprimem uma relação de dependência: um evento não ocorre antes que todas as atividades a ele imediatamente precedentes (arestas incidentes) sejam encerradas; de forma similar, uma atividade não pode ser iniciada antes que ocorra o envento que representa o início da atividade.

Nesta rede, o interesse maior é o de determinar o(s) caminho(s) do vértice inicial ao vértice final cuja soma das durações das atividades seja máxima. Este(s) caminho(s) é chamado de caminho crítico. Considerando, contudo, que i representa o evento inicial e que j representa o evento final de uma atividade i,j, alguns informações importantes que podem ser observadas na rede são:

ti,j duração da atividade i,j
TMCEi tempo mais cedo no evento i
TMTEi tempo mais tarde no evento i
FEi folga no evento i   FEi = TMTEi - TMCEi
TMCAi,j tempo mais cedo de conclusão da atividade i,j TMCAi,j =  TMCEi  +  ti,j
TMTAi,j tempo mais tarde de início da atividade i,j TMTAi,j = TMTEj - ti,j
FLAi,j folga livre da atividade i,j FLAi,j = TMCEj - TMCAi,j
FTA folta total FTA = FEj + FLAi,j