制約グラフ

人工知能やオペレーションズリサーチにおける制約充足問題の研究では、制約充足問題における制約間の関係を表すために、制約グラフやハイパーグラフが用いられる。制約グラフは、自由変数の存在を許容する因子グラフの特殊なケースである。

制約充足問題の制約ハイパーグラフは、頂点が変数に対応し、ハイパーエッジが制約に対応するハイパーグラフである。対応する変数が何らかの制約に現れる場合、頂点の集合はハイパーエッジを形成する。^{[ 1 ]}

制約ハイパーグラフを表現する簡単な方法は、以下の特性を持つ古典的なグラフを使用することです。

1. 頂点は変数または制約に対応し、
2. エッジは変数頂点と制約頂点のみを接続することができ、
3. 変数頂点と制約頂点の間にエッジが存在するのは、対応する変数が対応する制約に含まれる場合に限る。

特性1と特性2は二部グラフを定義する。ハイパーグラフは、頂点を変数頂点として定義し、ハイパーエッジを各制約頂点に接続された変数頂点の集合として定義することによって復元される。

制約充足問題の主制約グラフ、または単に主グラフ（ガイフマングラフとも呼ばれる）は、問題の変数をノードとし、制約内で2つの変数が一緒に出現する場合にエッジで2つの変数を結ぶグラフである。^{[ 1 ]}

主制約グラフは、実際には制約ハイパーグラフの 主グラフである。

制約に関係する変数の集合を制約スコープと呼びます。双対制約グラフは、頂点が問題の制約に関係するすべての制約スコープであり、対応するスコープが共通の変数を持つ場合に2つの頂点が辺で接続されるグラフです。^{[ 1 ]}