Prolog实现图顶点度数统计及单顶点度数≥3的判定方法

首先通过:- dynamic edge/2声明动态谓词edge/2，该谓词仅用于表征图中两个顶点之间存在连边关系，示例边事实定义如下：

edge(a, b). 
edge(c, d). 
edge(r, c). 
edge(c, t). 
edge(a, t). 

判定规则 #

需要实现的查询判定逻辑满足以下要求：

• 判断当前图中是否存在度数大于等于3的顶点
• 满足度数≥3的顶点必须有且仅有一个
• 如果图中存在2个及以上度数≥3的顶点，查询返回no
• 如果图中不存在度数≥3的顶点，查询同样返回no

实现代码 #

由于edge/2存储的是无向连边关系，计算度数时需要同时统计两个方向的连边，同时做去重处理避免重复计数：

% 计算指定顶点的无向度数
degree(Node, Deg) :-
    findall(Neighbor, (edge(Node, Neighbor); edge(Neighbor, Node)), Neighbors),
    sort(Neighbors, UniqueNeighbors),
    length(UniqueNeighbors, Deg).

% 核心查询谓词：有且仅有一个度数≥3的顶点时返回yes
has_exactly_one_high_degree_node :-
    findall(Node, (degree(Node, D), D >= 3), HighDegreeNodes),
    sort(HighDegreeNodes, UniqueHighNodes),
    length(UniqueHighNodes, 1).

使用说明 #

• 直接在Prolog交互环境中调用has_exactly_one_high_degree_node.即可得到查询结果
• 针对上文给出的示例边集，各顶点度数分别为：a(2)、b(1)、c(3)、d(1)、r(1)、t(2)，仅c点度数≥3，查询会返回yes
• 如果修改边集后存在0个或≥2个度数≥3的顶点，查询返回no

内容的提问来源于stack exchange，提问作者Michael