Begränsningsgraf
Inom begränsningstillfredsställelseforskning inom artificiell intelligens och operationsforskning används begränsningsgrafer och hypergrafer för att representera relationer mellan begränsningar i ett problem med begränsningstillfredsställelse . En begränsningsgraf är ett specialfall av en faktorgraf , som tillåter förekomsten av fria variabler.
Begränsningshypergraf
Restriktionshypergrafen för ett problem med begränsningstillfredsställelse är en hypergraf där hörnen motsvarar variablerna och hyperkanterna motsvarar begränsningarna. En uppsättning hörn bildar en hyperedge om motsvarande variabler är de som förekommer i någon begränsning.
Ett enkelt sätt att representera begränsningshypergrafen är att använda en klassisk graf med följande egenskaper:
- Vertices motsvarar antingen variabler eller begränsningar,
- en kant kan bara ansluta en variabel vertex till en constraint-vertex, och
- det finns en kant mellan en variabel-vertex och en constraint-vertex om och endast om motsvarande variabel förekommer i motsvarande restriktion.
Egenskaper 1 och 2 definierar en tvådelad graf . Hypergrafen återvinns genom att definiera hörnen som variabla hörn och hyperkanterna som uppsättningarna av variabla hörn kopplade till varje begränsningspunkt.
Primal begränsningsgraf
Den primära begränsningsgrafen eller helt enkelt primalgrafen (även Gaifman-grafen ) för ett problem med begränsningstillfredsställelse är grafen vars noder är variablerna för problemet och en kant förenar ett par variabler om de två variablerna förekommer tillsammans i en begränsning.
Den primära begränsningsgrafen är i själva verket den primära grafen för begränsningshypergrafen.
Graf med dubbla begränsningar
Uppsättningen av variabler som är involverade i en begränsning kallas begränsningsomfånget . Den dubbla begränsningsgrafen är grafen där hörnen alla är begränsningsomfång involverade i problemets begränsningar, och två hörn är sammankopplade med en kant om motsvarande omfång har gemensamma variabler.