Практическая работа №4
Специальные алгоритмы на графах.
1. Цель работы
Реализовать и проверить на тестовом примере специальный алгоритм
на графе.
2. Порядок выполнения работы
1.Самостоятельно составить и визуализировать граф (количество вершин должно быть не менее 10).
2.Согласно варианту из таблицы 4.1 выбрать специальный алгоритм.
Вариант необходимо уточнить у преподавателя.
3.На примере графа, полученного в пункте 1, описать работу выбранного специального алгоритма.
4.Реализовать выбранный специальный алгоритм средствами ЭВМ.
5.На примере графа, полученного в пункте 1, продемонстрировать работу алгоритма, реализованного в пункте.
3. Содержание отчета
1.Цель работы.
2.Матрица смежности и изображение графа, полученного в пункте 1
порядка выполнения п/р.
3.Пошаговое описание действий при применении алгоритма на примере созданного графа (см. пункт 3 порядка выполнения п/р).
4.Блок-схема алгоритма.
5.Описание разработанной программы в 4 пункте порядка выполнения п/р: листинг с комментариями и описание переменных.
6.Результат работы алгоритма на примере созданного графа (см. пункт 5 порядка выполнения п/р).
7.Выводы.
Таблица 4.1.
№
Алгоритм
варианта
1
Построение кластерного дерева по алгоритму WPGMA (взвешенный неориентированный полносвязный граф)
2
Алгоритм нахождения Гамильтонова цикла для полносвязного графа (взвешенный неориентированный полносвязный граф)
3
Алгоритм Брона-Кербоша (невзвешенный неориентированный граф)
Алгоритм Форда-Фалкерсона.
4
Исходные данные: взвешенный ориентированный граф с наличием только одной вершины без входящих ребер (источник), и только одной вершины без исходящих ребер (сток).
Задача о марьяже
5Исходные данные: взвешенный ориентированный двудольный граф
Построение кластерного дерева по алгоритму “Neighbor Joining”
6Исходные данные: взвешенный неориентированный полносвязный граф
7
Алгоритм раскраски графа Исходные данные: невзвешенный неориентированный граф
Алгоритм нахождения Эйлерова цикла
8Исходные данные: взвешенный неориентированный граф, в котором все вершины имеют четную степень.
9
Алгоритм Флойда-Уоршела Исходные данные: взвешенный ориентированный граф
Алгоритм Нуссинов
10
Исходные данные: невзвешенный неориентированный граф вида цепочки, в состав которого входят вершины 4 типов (2 пары противоположностей)