Kaavion purkaminen

Graafin avautuminen on funktio , joka on määritelty suunnatun graafin kärkien yli ja joka täyttää joukon ehtoja.

Määritelmä. Funktiota kutsutaan suunnatun graafin yleistetyksi ( tiukkaksi ) avautumiseksi, jos epäyhtälö , joka kulkee pisteestä toiseen, on tosi . $\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}))$

Tiukan avautumisen mielenkiintoinen ominaisuus on, että se määrittää kaavion porrastetun rinnakkaisen muodon , ja tällaisen NPF:n tasot ovat avautumisen tasopintoja.

Tiedetään, että millä tahansa algoritmin fragmentilla on ainakin yksi paloittain lineaarinen yleistetty avautuminen .

Algoritmigraafin tiukkoja ja yleisiä avauksia käytetään algoritmin tehokkaaseen rinnastukseen V. V. Voevodinin menetelmän mukaisesti .