Лекция: ЗАДАНИЕ 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. СТРАТЕГИИ ПОИСКА ПУТИ НА ГРАФЕ

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