구속조건 그래프

인공지능과 운영연구의 제약만족도 연구에서는 제약만족도 문제에서 제약만족도 간의 관계를 나타내는 제약만족도 그래프와 하이퍼그래프를 사용한다.제약 조건 그래프는 자유 변수의 존재를 허용하는 요인 그래프의 특별한 경우다.

제약 하이퍼그래프

제약조건 만족도 문제의 제약조건 하이퍼그래프는 정점이 변수에 대응하고, 축약성은 제약조건에 대응하는 하이퍼그래프다.정점 집합은 해당 변수가 어떤 제약조건에서 발생하는 변수일 경우 혼합체를 형성한다.^[1]

제약 조건 하이퍼그래프를 나타내는 간단한 방법은 다음과 같은 속성이 있는 클래식 그래프를 사용하는 것이다.

1. 정점은 변수나 제약조건에 해당된다.
2. 가장자리는 변수 쌍곡선만 제약 조건 쌍곡선에 연결할 수 있으며
3. 해당 변수가 해당 제약조건에서 발생하는 경우에만 변수-제곱과 제약 조건-제곱 사이에 에지가 있다.

속성 1과 2는 초당적 그래프를 정의한다.하이퍼그래프는 꼭지점을 변수-수직으로 정의하고, 확성기는 각 제약조건-버텍스에 연결된 변수-수직 집합으로 정의하여 복구한다.

원시 제약 조건 그래프

제약조건 만족도 문제의 원시적 제약조건 그래프 또는 단순 원시 그래프(게이프만 그래프)는 두 변수가 제약조건에서 함께 발생할 경우 가장자리가 한 쌍의 변수와 결합하는 그래프다.^[1]

원시 구속조건 그래프는 사실 구속조건 하이퍼그래프의 원시 그래프다.

이중 구속조건 그래프

제약조건과 관련된 변수 집합을 제약조건 범위라고 한다.이중 제약 조건 그래프는 문제의 제약 조건과 관련된 모든 제약 조건 범위인 그래프로, 해당 범위가 공통 변수를 가질 경우 두 개의 정점이 에지로 연결된다.^[1]

참조