Deseja-se tratar o problema de ocorrência de deadlocks em um sistema multiprocessador para computação paralela e distribuída. Para isto, cada elemento processador (EP) do sistema multiprocessador mantém um grafo local de dependência entre os processos. Nesse grafo, os vértices representam os processos Pk e existe uma aresta direcionada (Pi, Pj) entre o processo Pi e o processo Pj, se Pi espera por um recurso que está ocupado por Pj. Suponha que, em um determinado instante de tempo, os grafos em dois dos EPs sejam:
I) Grafo de dependência de EP1: Conjunto de vértices {P1, P2, P3, P5}, Conjunto de arestas {( P2, P1), (P2, P3), (P5, P1)}
II) Grafo de dependência de EP2: Conjunto de vértices {P2, P3, P4, P5}, Conjunto de arestas {( P3, P4), (P4, P2), (P5, P4)}
A análise desses dois grafos indica que:
