Рецензия № 6
Функциональное программирование
Курсовая работа
Определение эйлерова пути на Прологе
Халипский Сергей Николаевич Специальность:230105
Зеленогорск ze072hsn 84 Форма:З
2000
Проверил Зюзьков Валентин Михайлович Оценка: не зачтена
Комментарий
Ваша курсовая работа обладает недостатком, что не позволяет считать ее выполненной.
Понятие эйлерова пути возникло в восемнадцатом столетии, когда известный математик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рисунке 1. Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра – с мостами, которыми связаны эти части.

 
gffffff
  
Рисунок 1 Модель задачи о мостах Кенигсберг Может ли пешеход обойти все мосты, пройдя по каждому из них только один раз? Эта задача увлекла великого математика и в 1736 году Эйлер доказал ее неразрешимость. Как видите в данном случае надо рассматривать и параллельные ребра – две вершины графа соединяются несколькими ребрами (граф, в котором некоторые пары вершин соединены более чем одним ребром, называется мультиграфом).
Вы рассматриваете графы без параллельных ребер. Это достаточно обременительное ограничение – в исходной задаче Эйлера о кенисбергских мостах параллельные ребра как раз были.
Как представлять такие графы? Конечно не так, как в вашей программе.
Например, для данного мультиграфа: описание вершин:
(A B С D)
описание ребер:
((A C 3) (A C 4) (A B 1) (A B 2) (A D 5) (C D 7) (B D 6)) Так как в Лиспе большие и маленькие буквы не различаются, то мы вынуждены метки ребер заменить числами:
с 3, d 4, a 1, b 2, e 5, g 7, f 6. Каждое ребро описывается списком из двух вершин и меткой ребра.
И путь, который ищет программа, должен быть представлен в виде списка меток ребер.
Например, для данного графа путь (1 2 3 4) означает путь
из вершины A в вершину B по ребру 1, потом
из вершины B в вершину A по ребру 2, потом
из вершины A в вершину C по ребру 3, потом
из вершины C в вершину A по ребру 4. Сделайте изменения в программе и протестируйте программу на графах с параллельными ребрами. |