Форум программистов, компьютерный форум, киберфорум
Наши страницы
Prolog
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.58/12: Рейтинг темы: голосов - 12, средняя оценка - 4.58
blackdevill
0 / 0 / 0
Регистрация: 28.05.2010
Сообщений: 5
1

Поиск эйлеровых циклов

02.06.2011, 12:04. Просмотров 2494. Ответов 6
Метки нет (Все метки)

Требуется написать программу, реализующую поиск эйлеровых циклов в графе. Программа должна быть представленна на Prolog и Haskel.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2011, 12:04
Ответы с готовыми решениями:

Поиск циклов в графе. Поиск центра взвешенного графа
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать...

Поиск циклов в графе
Как узнать что граф имеет цикл?

Поиск циклов в графе
Подскажите, пожалуйста, какие идеи нужно применять к данной задаче

Поиск циклов в орграфе
Добрый день! Помогите, пожалуйста, разобраться с задачей. Имеется ориентированный граф....

Поиск Ф-циклов в графе
Нужно вывести на печать все фундаментальные циклы графа. Мой код выводит правильно(судя по данному...

6
emppu2007
90 / 90 / 6
Регистрация: 04.05.2011
Сообщений: 171
02.06.2011, 14:05 2
Лучший ответ Сообщение было отмечено как решение

Решение

Вот прога, ДОКАЗЫВАЮЩАЯ, что граф на самом деле Эйлеров, ну и между прочим находящая в нём Эйлеров цикл:
Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
domains 
  Ребро = ребро(integer,integer)
  Цикл = Ребро*
  database - граф 
  ребро(integer,integer)
  predicates
  nondeterm эйлер(integer,integer,integer,Цикл,Цикл)
  nondeterm получить_факт(Ребро)
  длина(Цикл,integer)
  принад(Ребро,Цикл)
  nondeterm путь(integer,integer)
goal
  findall(Ребро,получить_факт(Ребро),Рёбра),
  длина(Рёбра,Длина),
  ребро(А,Б),
  эйлер(А,Б,Длина,[ребро(А,Б)],Цикл).
clauses
  эйлер(А,А,1,Цикл,Цикл):-!.
  эйлер(А,Б,Длина,Стек,Цикл):-
    путь(Б,В),not(принад(ребро(Б,В),Стек)),Длина1=Длина-1,
    эйлер(А,В,Длина1,[ребро(Б,В)|Стек],Цикл).
 
получить_факт(ребро(А,Б)):-ребро(А,Б).
 
длина([_|Рёбра],Длина):-!,длина(Рёбра,Длина1),Длина=Длина1+1.
длина([],0).
 
принад(Ребро,[Ребро|_]):-!.
принад(ребро(А,Б),[ребро(Б,А)|_]):-!.
принад(Ребро,[_|Путь]):-принад(Ребро,Путь).
 
путь(А,Б):-ребро(А,Б).
путь(А,Б):-ребро(Б,А).
 
ребро(1,2).
ребро(1,3).
ребро(1,4).
ребро(1,5).
ребро(1,6).
ребро(1,7).
ребро(2,3).
ребро(4,5).
ребро(6,7).
Найдено 72 решения, вот последнее:
Prolog
1
2
3
Цикл=[ребро(1,6),ребро(2,1),ребро(3,2),ребро(1,3),ребро(4,1),
      ребро(5,4),ребро(1,5),ребро(7,1),ребро(6,7)]
72 Solutions
Так как использовался стек, то запись цикла представлена в обратном порядке. Кому надо - можете реверснуть список.

А вот прога, находящая максимальный Эйлеров цикл в не Эйлеровом графе (если конечно этот цикл в нём есть):
Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
domains 
  sl=symbol* 
  predicates 
  nondeterm a(symbol,symbol) 
  nondeterm b(symbol,symbol) 
  nondeterm цикл(symbol,symbol,sl,sl,integer,integer) 
  принадл(symbol,symbol,sl) 
  длиннее(symbol,integer) 
 
clauses 
  a(a,b). a(b,c). a(d,c). a(d,f). a(f,c). a(a,c). 
 
b(X,Y):- a(X,Y); a(Y,X). 
 
цикл(X0,X,V,L,D,Di):- b(X,Y),not(принадл(X,Y,V)),D1=D+1, 
   цикл(X0,Y,[Y|V],L,D1,Di). 
цикл(X,_,[X|V],[X|V],Di,Di):-Di>1. 
 
принадл(X,Y,[X,Y|_]):- !. 
принадл(X,Y,[Y,X|_]):- !. 
принадл(X,Y,[_|T]):- принадл(X,Y,T). 
 
длиннее(X,D):- a(X,Y),цикл(X,Y,[Y,X],_,1,D1),D<D1,!. 
goal 
  a(A,B),цикл(A,B,[B,A],Цикл,1,D),not(длиннее(A,D)).
3
m1ss_marple
0 / 0 / 0
Регистрация: 22.12.2012
Сообщений: 2
25.12.2012, 16:35 3
И никто не сказал "Спасибо"!!!!
0
Vityok
0 / 0 / 1
Регистрация: 02.01.2012
Сообщений: 23
14.10.2013, 00:07 4
я скажу большое спасибо))) мне как раз нужна эта тема)))
0
nickmk
1 / 1 / 0
Регистрация: 21.10.2013
Сообщений: 22
25.10.2013, 22:13 5
emppu2007, Скажи пожалуйста, в каком это прологе можно запустить эту программу, и как?
0
emppu2007
90 / 90 / 6
Регистрация: 04.05.2011
Сообщений: 171
29.10.2013, 18:21 6
nickmk, прошу прощения, что отвечаю лишь спустя несколько дней. Бываю на форуме нечасто.
Код, который я приложил, предназначен для Visual и Turbo-прологов. Если оставить только секцию Clauses - будет идеально работать в SWI.
0
Raideres
1 / 1 / 2
Регистрация: 29.10.2009
Сообщений: 211
07.11.2013, 10:56 7
Нужно вывести Эйлеров цикл в неориентированном графе (Turbo Prolog)
0
07.11.2013, 10:56
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 10:56

№1 Как преобразовать, чтобы решить с помощью эйлеровых интегралов
как преобразовать,чтобы решить с помощью эйлеровых интегралов? \int_{0}^{3} dx/\sqrt{x^{2}*(3-x)}

№2 Как преобразовать, чтобы решить с помощью эйлеровых интегралов
как преобразовать,чтобы решить с помощью эйлеровых интегралов? \int_{-\propto }^{\propto...

Задача поиск вложенных циклов while
Помогите с задачей. Нужно найти максимальное количество вложенных циклов while. Даны два...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru