Как раскрасить график

Question

У меня есть вопрос, описанный ниже:

Напишите прологическую программу, которая раскрашивает график. Цвета определяются предикатом color/1, а график - границей /2. Вы должны написать предикатную раскраску (Coloring), которая находит раскраску узлов 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].

Напишите цвет предиката ниже.

На самом деле, я только начинаю заниматься этой практикой. Так что понятия не имею. Я думаю, что четырех цветов будет достаточно, чтобы раскрасить график. Может быть, кто-то задал похожий вопрос. Когда у меня появятся идеи, я опубликую их быстро.

Answer 1

Вам нужно знать имена узлов. Один из способов сделать это - использовать setof / 3:

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

X ^ Y означает, что X и Y должны использоваться в поиске, но не для результата.

Теперь мы создали список ассоциаций Node/Color, используя предикат 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))).

Я забыл сказать, что Пролог с его возвратом делает свою работу!