Demucron algoritmusa

A Demukron -algoritmus egy algoritmus a topológiai rendezés problémájának megoldására , vagyis a gráf csúcsainak szintjeik szerinti rendezésére egy kontúr nélküli irányított gráf esetében . A gráf csúcsainak szintjei a bemenetektől ezekhez a csúcsokhoz vezető maximális útvonalak hosszának tekinthetők.

Megfogalmazás

A Demukron algoritmusának fő ötlete az, hogy szekvenciálisan távolítsa el a gráfból, kezdve a bemenetektől, a csúcsoktól és az azokból kimenő ívektől [1] .

Jegyzetek

  1. Discrete Mathematics, 2006 , p. 351.

Irodalom