2

グラフがあり、グラフ内で 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つの制約に入れることができますか?

4

1 に答える 1