kényszerterjesztése

Kapcsolódó fogalmak: 
kényszerkielégítési probléma (CSP)
Rövid szöveges bemutatás: 
A kényszerterjesztést a kényszer kielégítési problémák megoldásának alapstruktúrája. Ebben a módszerben egy változó lehetséges értékeit nem csak a kényszerek korlátozzák és a kiinduló tartomány. Ebben az esetben extra korlátozásra kerül sor egy másik változó által. Tehát ilyenkor adott egy változó melynek értékadása korlátozza a vele kapcsolatban álló másik változó lehetséges érték készletét. Például, ha adott egy gráf színezési feladat, ahol a csomópontok egy csoportja csak {kék; zöld} színű lehet és belőlük él vezet egy olyan csomópont halmazba, melynek értéke csak {zöld} lehet, akkor a kényszerterjesztés esetében, az első csoportban csak kék színű csomópont lehet, mert akkor lehet konzisztens szín hozzárendelést biztosítani a második csoporthoz. Ha az első csoport valamelyik tagja zöld, akkor nem létezik konzisztens hozzárendelés a második csoporthoz a kényszerek terjesztése miatt.