Write(Пройденные).
Правило 2: Если остались еще не пройденные ребра, то надо взять
ребро, исходящее из текущей вершины и не принадлежащее списку
пройденных.
Найти_путь(Текущая,Пройденные):-
длина(Пройденные,N),N<6, ребро(Ребро,Текущая,Новая),
Не_принадлежит(Ребро,Пройденные),
найти_путь(Новая,[Ребро|Пройденные]).
(предикат 'не_принадлежит' написать самостоятельно).
ЗАДАНИЕ 2.1
Напишите самостоятельно предикаты ‘длина’ и ‘не_принадлежит’. Задайте запрос на поиск эйлеровой цепи. Запрос на поиск эйлеровых цепей, начинающихся из вершины _Начальная будет иметь вид:
?-найти_путь(_Начальная,[]).
ЗАДАНИЕ 2.2
Написать программу поиска эйлеровых циклов.
ЗАДАНИЕ 2.3
Гамильтонава цепь - маршрут, в котором содержатся все вершины графа ровно один раз. Написать программу поиска гамильтоновой цепи в графе.
ЗАДАНИЕ 2.4
Гамильтонов цикл - гамильтонова цепь, у которой начальная и конечная вершины совпадают. Написать программу поиска гамильтонова цикла в графе.
ЗАДАНИЕ 2.5
Написать программу поиска всех вершин, достижимых из данной вершины. Вершина V достижима из вершины W, если существует путь из вершины W в вершину V.
|
|
ЗАДАНИЕ 2.6
Граф называют связанным, если после снятия ориентации в нем для любой пары вершин существует путь, их соединяющий. Написать программу, определяющую связан ли граф.
ЗАДАНИЕ 2.7
Решите одну из следующих задач, согласно порядковому номеру в группе:
1. Компонентой связности графа называют связанный подграф графа, не являющийся часть другого связанного подграфа. Написать программу печати компонент связанности.
2. Множество W вершин неориентированного графа G называется внешне устойчивым, если для любой вершины V1 из множества V(G)\W найдется вершина V2 из W такая, что (V1,V2) - ребро графа G. Написать программу поиска наименьшего внешне устойчивого множества графа.
3. Множество W вершин неориентированного графа G называется внутренне устойчивым, если для любой пары вершины V1 и V2 из W не существует ребра (V1,V2) в графе G. Написать программу поиска наибольшего внутренне устойчивого множества графа.
4. Построить остов в неориетированном связанном графе. Остовом называют дерево, построенное из ребер графа и содержащее все его вершины.
5. В графе, ребрам которого приписаны веса, написать программу поиска пути максимального веса, соединяющий заданную пару вершин. Вес пути равен сумме весов ребер, входящих в этот путь.
3. СТРАТЕГИИ ПОИСКА ПУТИ НА ГРАФЕ
ЦЕЛЬ: Познакомится с классическим алгоритмом обхода деревьев широко используемых в задачах искусственного интеллекта и научиться применять их на практике.