Desfacerea graficului

O desfășurare a unui graf este o funcție definită peste vârfurile unui graf direcționat și care satisface un număr de condiții.

Definiție. O funcție se numește desfășurare generalizată ( strictă ) a unui graf direcționat dacă inegalitatea de la până la este adevărată . $\phi (V)$ $G=(V,E)$ $\forall e\in E$ $v_{1}$ $v_{2}$ $\phi (v_{1})\leq \phi (v_{2})(\phi (v_{1})<\phi (v_{2}))$

O proprietate interesantă a unei desfășurări stricte este aceea că definește o formă paralelă în trepte a graficului , iar nivelurile într-un astfel de NPF sunt suprafețele de nivel ale desfășurării.

Se știe că orice fragment al algoritmului are cel puțin o desfășurare generalizată liniară pe bucăți .

Desfăşurările stricte şi generalizate ale graficului algoritmului sunt folosite pentru paralelizarea eficientă a algoritmului conform metodei lui V. V. Voevodin .