Найти_путь(Текущая,Пройденные):- длина(Пройденные,6)

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. СТРАТЕГИИ ПОИСКА ПУТИ НА ГРАФЕ

ЦЕЛЬ: Познакомится с классическим алгоритмом обхода деревьев широко используемых в задачах искусственного интеллекта и научиться применять их на практике.