kényszerhipergráf

Kapcsolódó fogalmak: 
kényszerkielégítési probléma (CSP)
Rövid szöveges bemutatás: 
A kényszerhipergráf egy olyan gráf melyekben kényszereket tudunk jelölni. A gráfnak a csomópontjai tartalmazzák az egyes változókat melyekre a kényszerek és a keresett eredmény vonatkozik és a csomópontokat összekötő élek jelölik a kényszereket. A gráfban háromféle csomópont van reprezentálva, az egyik fajta jelöli a változókat a másik a kényszereket, a harmadik pedig az eredményt. Pontosan ebben fog eltérni a hipergráf a sima kényszergráftól, mert itt háromféle csomópontot is lehet jelölni. A kényszercsomópont egyfajta gyűjtőpontnak is felfogható. Ide van bekötve minden olyan változónak a csomópontja amelyre kényszer vonatkozik az adott eredményhez kapcsolódóan. Ilyenkor az élek jelölik ki, hogy melyik kényszercsomópont melyik változócsomópontra vonatkozik. Egy ilyen típusú gráf a képen látható.