1

我是回答集编程的新手，可以使用一些帮助。我一直在读这个，但仍然可以使用一些帮助。我将如何使用答案集编程来判断一个图是否是强连接的？

我的头脑风暴：

  • 由节点和边（即节点（1..2）、边（1,2）和边（2,1））表示的图形。

  • 现在我需要规则 "strong() :- ......" 如果图形是强连接的，那是真的。

  • 如果您可以从任何节点开始并通过沿它们指向的方向到达任何其他节点，则图是强连接的。

  • 所以我的程序需要获取每个节点 X 并沿着有向边尝试到达每个其他节点。如果它到达每个其他节点，则为 True，否则为 False。

强的（） ：- ？

4

1 回答 1

0

首先，除非您的图形是有向的，否则您必须获得对称边：

edge(X,Y):- edge(Y,X).

然后，如果两个节点之间存在路径，则需要告诉它们已连接：

connected(X,Y):- edge(X,Y).
connected(X,Z):- edge(X,Y) ; connected(Y,Z).

现在，strong如果对于所有节点对，它们都已连接，则成立：

strong:- connected(X,Y): edge(X,_), edge(_,Y).

替代版本可能是：

not_strong:- not connected(X,Y) ; edge(X,_) ; edge(_,Y).
strong:- not not_strong.

（用 cligo 4.5.4 测试）

于 2017-01-13T11:05:49.563 回答