Методы программирования. Кулаков Ю.В - 13 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

для проверки связности получаемых подграфов. Рассмотрите также способ обнаружения точек сочленения и
компонент двусвязности при единственном обходе графа, когда сохраняется незначительное количество допол-
нительной информации. Выполните упражнения по поиску компонент двусвязности в заданных графах.
Познакомьтесь с понятием транзитивного бинарного отношения и замыкания транзитивного отноше-
ния. Заметьте, что замыкание по транзитивности, например, коммуникационной сети, представленной ориенти-
рованным графом, позволяет определить, существует ли возможность переправить сообщение из одного задан-
ного места в другое. Рассмотрите алгоритм вычисления транзитивного замыкания бинарного отношения. Вы-
полните алгоритм вручную для некоторого бинарного отношения и проанализируйте полученные результаты.
4.3. Алгоритмы поиска для взвешенных графов
Познакомьтесь с понятиями остовного дерева и минимального остовного дерева. Понятие минимального
остовного дерева может использоваться, например, в задаче построения железнодорожной сети, связывающей
некоторое число городов. В такой задаче известна стоимость строительства отрезка путей между любой парой
городов и требуется найти сеть минимальной стоимости. Изучите алгоритм Дейкстры-Прима построения ми-
нимального остовного дерева, заключающийся в том, что сначала выбирается произвольная вершина графа и
включается в остовное дерево. Затем на каждом шаге рассматривается множество ребер, допускающих присое-
динение к уже построенной части остовного дерева, и выбирается из них ребро с наименьшим весом. Работа
алгоритма заканчивается после того, как в остовное дерево попадут все вершины. Исполните этот алгоритм
вручную на конкретном примере и проанализируйте полученный результат. Изучите алгоритм Крускала по-
строения минимального остовного дерева, заключающийся в том, что все начинается с пустого дерева, к кото-
рому добавляются ребра в порядке возрастания их весов. Процесс добавления ребер продолжается до тех пор,
пока не получится набор ребер, объединяющий все вершины графа. Найдите с помощью этого алгоритма мини-
мальное остовное дерево для того же графа, что и при рассмотрении алгоритма Дейкстры-Прима, и сравните по-
лученные результаты.
Рассмотрите понятие кратчайшего пути из одной вершины ориентированного графа в другую, которое
используется во многих практических приложениях. Например, взвешенным ориентированным графом моде-
лируется транспортная сеть, по которой товары доставляются из города в город, или коммуникационная сеть,
по которой переправляется информация. Рассмотрите алгоритм Дейкстры поиска кратчайшего пути и выпол-
ните его для заданного графа. Изучите также алгоритм поиска дерева кратчайших путей из начальной вершины
графа в любую другую его вершину, который основан на итерационном уточнении дерева кратчайших путей, и
алгоритм поиска дерева кратчайших путей из любой вершины графа до конечной вершины, основанный на ме-
тоде динамического программирования. Выполните вручную эти алгоритмы для заданных графов и проком-
ментируйте полученные результаты.
Вопросы для самопроверки
1. Каковы определения понятий: граф; дуга, инцидентная вершине; вершина, коинцидентная дуге; сте-
пень вершины; граничные вершины дуги; начало и конец дуги?
2. Что понимается обычно под частичный графом, подграфом, частичным подграфом?
3. Какой смысл вкладывается в понятия взвешенной вершины, взвешенной дуги и взвешенного графа?
4. Чем отличаются ориентированные и неориентированные графы?
5. Как Вы понимаете термины: ребро; цепь; концевая вершина цепи; длина цепи; составная, сложная и
простая цепь; цикл?
6. Какой граф называют связным графом?
7. Что такое компонента связности графа?
8. Сколько компонент связности может иметь связный и несвязный граф?
9. Какой смысл вкладывается в понятия: расстояние между вершинами графа; диаметр графа; путь; кон-
цевая вершина пути; начальная и конечная вершина пути; длина пути; составной, сложный и простой путь;
контур?
10. Какой граф называют сильно связным графом?
11. Что такое компонента сильной связности?
12. Сколько компонент сильной связности может иметь сильно связный и несильно связный граф?
13. Каким образом представляются графы в ЭВМ с помощью матрицы смежности, матрицы инциденций и
списка смежности?
14. Чем различаются возможные представления по объему занимаемой памяти и времени доступа к дан-
ным?
15. Что Вы понимаете под обходом вершин графа?
16. Каким образом выполняются обходы вершин графа в глубину и по уровням?
17. При решении каких практических задач, формулируемых в терминах графов, бывает важно определить
не только число компонент связности или сильной связности графа, но и сами компоненты связности или силь-
ной связности?
18. Как строятся матрицы достижимости, матрицы связности и матрицы сильной связности?
19. Каким образом алгоритм Уоршелла, вычисляющий матрицу достижимости, может быть использован
для получения матрицы связности и матрицы сильной связности?
20. Как работает алгоритм выделения компонент связности или сильной связности, который может быть
реализован на компьютере?

Страницы