- - - - CENAPAD-MGCO

A seguir: Regra da Equidade Acima: The Drinking Philosophers Problem Anterior: Modificando o Grafo de

Regra da Aciclicidade

Regra da Aciclicidade :
se um grafo de precedências é acíclico, ele permanece acíclico se todas as arestas incidentes em um nó são dirigidas a êle numa ação atômica

Prova: suponha que o grafo resultante de uma operação como esta sobre o nó i contenha um ciclo.

• Se este ciclo não contém i, ele já existia, o que contraria a nossa hipótese
• Se este ciclo contém i estamos também diante de uma impossibilidade, pois todas as arestas incidentes em i estão dirigidas a ele.