Головна |
Вирішіть одну з наступних завдань, згідно з порядковим номером у групі:
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. СТРАТЕГІЇ ПОШУКУ ШЛЯХИ на графі
МЕТА: Познайомиться з класичним алгоритмом обходу дерев широко використовуваних в завданнях штучного інтелекту і навчитися застосовувати їх на практиці.
Ребро (a, 1,2). | СТРАТЕГІЯ ПОШУКУ В ГЛИБИНУ
ПРОГРАМА ОБЧИСЛЕННЯ перестановок БЕЗ ПОВТОРЕНЬ | ПРОГРАМА ОБЧИСЛЕННЯ поєднання БЕЗ ПОВТОРЕНЬ | АЛГОРИТМИ на графі ТА ЇХ ПРОЛОГ ПРОГРАМИ | СТРАТЕГІЯ пошуку в ширину | Large (TT, Solv). | Opt_f (TT, F1), | ЗАВДАННЯ ПРО ТРЬОХ СУДИНАХ | Обсяги (8,5,3). | ЗАВДАННЯ 4.2 | Showpos (P). |