ciklikusság-vágóhalmaz

Kapcsolódó fogalmak: 
kényszerkielégítési probléma (CSP)
Rövid szöveges bemutatás: 
A fogalmat a bonyolult kényszerkielégítési problémák megoldására alkalmazzuk. Az ilyen problémákat a jobb szemléltetés érdekében gráfként is ábrázolni szokták. A gráfban az egyes élek kényszereket jelentenek az egyes csomópontok között. Az ilyen problémák megoldására létezik egy általános algoritmus, de ahhoz a gráfnak egy fának kell lennie. A ciklikusság-vágóhalmaz módszerénél kiválasztjuk azokat a csomópontokat a gráfból, melyek törlésével egy fát kapunk, a kiválasztott csomópontok halmaza lesz a ciklikusság-vágóhalmaz. A kiválasztott csomópontok értékét rögzítjük, és a kiválasztott értékékeket kivesszük a gráf maradék részére alkalmazható értékei közül. Így a fára talált megoldás konzisztens lesz a ciklikusság-vágóhalmazzal. Miután megoldottuk a fára problémát újra visszarakjuk a kivett csomópontokat és a teljes feladatot megoldottuk.