グラフがあり、グラフ内で 2 つの異なるクリークを見つけたいとします。クリークは、すべてが接続されているグラフ頂点のサブセットです。クリークサイズ 3 の 2 つのクリーク (a,b,c) および (b,c,d) を含むグラフの例:
edge(a,b). edge(a,c). edge(b,c). edge(d,c). edge(d,b).
vertex(X;Y) :- edge(X,Y).
2 つのクリークを取得するのはかなり簡単です。
#const cs=3. % cliquesize
cs{clique1(X) : vertex(X)}cs.
:- clique1(X), clique1(Y), X!=Y, not edge(X,Y), not edge(Y,X).
cs{clique2(X) : vertex(X)}cs.
:- clique2(X), clique2(Y), X!=Y, not edge(X,Y), not edge(Y,X).
#show clique1/1.
#show clique2/1.
与えます：
Answer: 1
clique2(d) clique1(a) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 2
clique2(d) clique1(d) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 3
clique2(a) clique1(a) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 4
clique2(a) clique1(d) clique2(b) clique2(c) clique1(b) clique1(c)
SATISFIABLE
これは次のように解釈できます。
Answer 1: (a,b,c), (b,c,d)
Answer 2: (b,c,d), (b,c,d)
Answer 3: (a,b,c), (a,b,c)
Answer 4: (b,c,d), (a,b,c)
しかし、両方のクリークが異なるかどうかをテストするにはどうすればよいでしょうか? 私は試した
differ() :- clique1(X), clique2(Y), X!=Y.
:- not differ().
しかし、これは出力には影響しません。2 つのクリークが異なるかどうかをテストするにはどうすればよいですか?
今、私はこの解決策を見つけました:
differ() :- clique1(X), vertex(X), not clique2(X).
:- not differ().
動作しますが、2行必要なのが好きではありません。どうすればそれを1つの制約に入れることができますか?