2

我需要定义一个谓词 acyclic/1 ，它将一个图作为输入并确定该图是否是非循环的。所以根据我的理解 

graph1(a,b).
graph1(b,c). 
graph1(c,a).

将返回 no 和

graph2(a,b).
graph2(b,c).

将返回是

我做了一个谓词来确定图中的 2 个节点是否连接，如果连接，它们将返回是。

isConnected(X,Y) :- a(X,Z), isConnected(Z,Y).

有没有办法可以使用它来确定图形是否是非循环的？

我不想使用任何预定义的谓词。

4

2 回答 2

2

使用closure0/3：

:- meta_predicate acyclic(2).
:- meta_predicate cyclic(2).

acyclic(R_2) :-
   \+cyclic(R_2).

cyclic(R_2) :-
  closure0(R_2, X0,X),
  call(R_2, X,X0).

?- acyclic(graph2).
true.

?- acyclic(graph1).
false.

cyclic/1如果存在以下情况则成功：

  1. X0从到的无环连接X，因此：

    closure0(R_2, X0,X)或更详细地说：

    call(R_2, X0,X1), call(R_2, X1,X2), call(R_2, X2,X3), ..., call(R_2, Xn,X)X0,X1,...,Xn所有成对 不同

  2. 一个边缘回来

    call(R_2, X,X0).

所以这是一个循环。换句话说，循环图是包含至少一个循环的图。而那个循环由一个非循环部分加上一个边缘向后组成。并且只有这个边缘使这成为一个循环。

于 2014-11-16T21:47:59.277 回答
0

您的递归谓词 isConnected/2 错过了基本情况：

isConnected(X,Y) :- graph1(X,Y).

（当然，假设我们正在检查 graph1）。

无论如何，您不能使用 isConnected/2，因为 Prolog 将在循环图上循环。

于 2014-11-16T23:16:00.357 回答