Вывести вершины, не соединенные ребрами

      Комментарии к записи Вывести вершины, не соединенные ребрами отключены

Помечено: ,

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 1 месяц назад.

  • Автор
    Сообщения
  • #1840

    questioner
    Участник

    Нужна ваша помощь. Необходимо, чтобы выдавались вершины, которые не соединены ребрами, а у меня получилось написать только чтоб соединенные выдавал. Не могли бы вы подправить?

    reb(a,1,2).
    reb(b,2,3).
    reb(c,1,3).
     
    ver(1).
    ver(2).
    ver(3).
    ver(4).
     
    poisk(A,Res):-
      setof(B,dost(A,B,1),Res).
    dost(_,_,0):-
      !,false.
    dost(A,B,_N):-
      reb(Reb,A,B);
      reb(Reb,B,A).
    dost(A,C,N):- 
      N1 is N-1,
      dost(A,B,N1),!,
      dost(B,C,N1).

  • #1841

    Нужно вывести все пары вершин, между которыми нет пути или просто найти изолированные вершины графа (т.е. вершины нулевой степени)?

    Поиск пар вершин:

    nonadjacency(A, B):-
        ver(A), ver(B), \+reb(_, A, B).

    Пролог — это язык очень близкий к математике. Поэтому такие утверждения записываются очень просто и лаконично. В этом утверждении мы просим его найти вершины A и B такие, что нет дуги из A в B.
    Если граф неориентированный, то можно написать так:

    nonadjacency(A, B):-
        ver(A), ver(B), \+(reb(_, A, B);reb(_, B, A)).

    Тут мы просим машину логического вывода найти такие вершины A и B, что нет ни дуги из A в B, ни дуги из B в A. Хотя я думаю, что лучше описать правило edge следующим образом:
    edge(A, B):- reb(_, A, B); reb(_, B, A).

    И вызывать его вместо reb — это более гибкое решение.
    Правило nonadjacency возвращает вам пару вершин. Получить все можно при помощи следующего запроса:

    ?- nonadjacency(A, B), write((A, B)), nl, fail.
    1,1
    1,4
    1,5
    1,6

    Либо с использованием стандартного предиката findall:

    ?- findall((A, B), nonadjacency(A, B), L), write(L), nl.
    [ (1,1), (1,4), (1,5), (1,6), (1,7), (2,2), (2,5), (2,6), (2,7), (3,3), (3,4), (3,6), (3,7), (4,1), (4,3), (4,4), (4,6), (4,7), (5,1), (5,2), (5,5), (5,6), (5,7), (6,1), (6,2), (6,3), (6,4), (6,5), (6,6), (7,1), (7,2), (7,3), (7,4), (7,5), (7,7)]
    L = [ (1, 1), (1, 4), (1, 5), (1, 6), (1, 7), (2, 2), (2, 5), (2, 6), (..., ...)|...].

    Если же Вам требуется найти вершины, между которыми нет пути (а не ребра, как Вы описали в задании), то вместо reb в правиле edge вызывайте правило поиска пути, описанное в статье. Не важно будет это поиск в глубину или поиск в ширину.

Для ответа в этой теме необходимо авторизоваться.