图是序言中的树吗

Question

我正在学习 Prolog，我有这段代码可以确定图形是否为树。如果没有循环并且边缘连接，则图是树。

我的问题是：如何获得解决方案？

例如这张图？

Graph = [a-b, b-c, b-d, c-d] 我想弄清楚它是如何工作的。

stree(Graph,Tree):-
  subset(Graph, Tree),
  tree(Tree),
  covers(Tree, Graph).

tree(Tree):-
   connected(Tree),
   not hasacycle(Tree).

connected(Graph):-
   not(node(A, Graph),node(B,Graph), 
   not path(A,B,Graph,_)).

hasacycle(Graph):-
   adjacent(Node1,Node2,Graph), 
   path(Node1,Node2,Graph,[Node1,X,Y|_]).

covers(Tree,Graph):-
  not(node(Node,Graph),
  not node(Node,Tree)).

subset([],[]).
subset([X|Set],subset):-
 subset(Set,subset).
subset([X|Set],[X|subset]):-
 subset(Set, subset).

Answer 1

直接回答您的问题

您询问了如何在 Prolog 中检查一个图是否为树，特别针对您的示例图：

test.pl:

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

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

adjacent(X,Y,Graph) :-
  (edge(X,Y,Graph) ; edge(Y,X,Graph)).

travel(A,B,PathSuffix,Path,Graph) :-
  adjacent(A,B,Graph),
  Path = [B|PathSuffix].

travel(A,B,PathSuffix,Path,Graph) :-
  adjacent(A,C,Graph),
  C \== B,
  \+ member(C,PathSuffix),
  travel(C,B,[C|PathSuffix],Path,Graph).

path(A,B,Path,Graph) :-
  travel(A,B,[A],ReversedPath,Graph),
  reverse(ReversedPath,Path).

connected(Graph) :-
  not((
    node(A,Graph),
    node(B,Graph),
    not(path(A,B,_,Graph))
  )).

hascycle(Graph) :-
   node(A,Graph),
   node(B,Graph),
   adjacent(A,B,Graph), 
   path(A,B,[A,_,_|_],Graph).

tree(Graph) :-
   connected(Graph),
   not(hascycle(Graph)).

$ swipl
?- [test].
?- tree(graph1).
false.

图的结构编码在原子 node 和 edge 中。

path规则基于此this example。

规则 connected、hascycle 和 tree 对应于您程序中的规则。

注意大写标识符是变量：Graph 是变量，而 graph1 是常量。

对您的代码的评论

您提供的代码存在多个问题：

它不能用 SWI Prolog 8.0.1 编译。我不得不用 not(A) 替换 not A 的未加括号的用法。此外，我不得不将 not(A,B) 形式的用法替换为 not((A,B))。如果您的程序为您编译，请指定您使用的是哪个 Prolog compiler/interpreter。

您的代码不包含 path 的定义，请参阅上面链接的示例。

您的代码包含附加规则 stree，据推测检查 Tree 是否是 Graph 的 spanning tree，以及辅助规则 cover 和 subset.

subset 的定义完全被打破：除了 subset([],[]) 基本情况外，它是不可满足的，因为作为参数传递的 subset 是常量，而不是变量.我想你反而想要一个 subgraph(G1,G2) 规则，它检查 G1 的每个节点都是 G2 的节点，并且 G1 中的每对相邻节点在 G2 中也是相邻的。

图是序言中的树吗

Is the graph a tree in prolog

tree

graph-theory

prolog

直接回答您的问题

对您的代码的评论