如何为图表着色

我有一个问题描述如下：如何为图表着色

写一个prolog程序，为图表着色。颜色由颜色/ 1谓词定义，图由条边/ 2定义。您必须编写谓词着色（着色），查找图的节点node_1，...，node_n的着色。着色列表 [node_1/color_1，...，node_n/color_m]其中color_1，...，color_m是颜色，满足每条边的节点具有不同颜色的属性。

让我们看一个例子。让颜色和边缘成为下面的谓词。

% 2 colors 
color(blue). 
color(red). 
% the edges 
edge(1,2). 
edge(1,3). 
edge(2,4). 
edge(5,2).

对于该数据，满足着色（C）。一种解决方案是

C = [ 1/blue, 2/red, 3/red, 4/blue, 5/blue].

在下面写下谓词颜色。

其实我只是开始做这个练习。所以我不知道。我认为四种颜色就足以为图表着色。也许有人问过类似的问题。当我有一些想法时，我会尽快发布。

来源

2013-07-29 user2585677

我投票结束这个问题作为题外话，因为它显然是家庭作业，没有显示学生的努力，也没有询问他们__现有执行中的_specific_问题。 – Mogsdad

您需要知道节点的名称。一种方式做到这一点是SETOF/3使用：

setof(Node,X^Y^(edge(Node, X); edge(Y,Node)), LN)

X^Y表示X和Y必须在搜索中使用而不是结果。

现在我们使用谓词set_color（List_of_nodes，List_of_association）构建关联节点/颜色的列表。

一个空的节点列表给出了一个空关联列表！现在

set_color([], [])

，工艺流程：

% we work with the current element of the list of nodes 
set_color([H | T], [H/C | TC]) :- 
    % we create the association for the rest of the list 
    set_color(T, TC), 
    % we choose the color 
    color(C), 
    % we check that two adjacent nodes of different colors 
    forall(member(Node/Color, TC), 
      ( (edge(Node, H) -> Color \= C; true), 
      (edge(H, Node) -> Color \= C; true))).

所以，你得到：

% 2 colors 
color(blue). 
color(red). 
% the edges 
edge(1,2). 
edge(1,3). 
edge(2,4). 
edge(5,2). 

coloring(L) :- 
    setof(Node,X^Y^(edge(Node, X); edge(Y,Node)), LN), 
    set_color(LN, L). 


set_color([], []). 

set_color([H | T], [H/C | TC]) :- 
    set_color(T, TC), 
    color(C), 
    forall(member(Node/Color, TC), 
      ( (edge(Node, H) -> Color \= C; true), 
      (edge(H, Node) -> Color \= C; true))).

我忘了说，Prolog的，其回溯做工作！

来源

2013-07-29 11:40:12 joel76

如何为图表着色

回答

相关问题