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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Т е м а 4. АЛГОРИТМЫ НА ГРАФАХ
Программа
4.1. Графы
Основные понятия теории графов. Возможные представления графов в ЭВМ.
4.2. Алгоритмы поиска в невзвешенных графах
Алгоритмы поиска связных и двусвязных компонент в неориентированных графах. Алгоритм поиска
сильносвязных компонент в ориентированных графах. Алгоритмы нахождения транзитивного замыкания.
4.3. Алгоритмы поиска для взвешенных графов
Остовные деревья. Алгоритмы нахождение остовного дерева минимального веса, определения кратчайших
расстояний между вершинами графа.
Методические указания
4.1. Графы
Изучите основные понятия теории графов: граф; дуга, инцидентная вершине; вершина, коинцидентная ду-
ге; степень вершины; граничные вершины дуги; начало и конец дуги; частичный граф; подграф; частичный
подграф; смежные дуги и вершины; окрестность единичного радиуса вершины; взвешенная вершина; взвешен-
ная дуга; взвешенный граф; ориентированные и неориентированные графы; ребро; цепь; концевая вершина це-
пи; длина цепи; составная, сложная и простая цепь; цикл; связный граф; компонента связности графа; несвяз-
ный граф; расстояние между вершинами графа; диаметр графа; путь; концевая вершина пути; начальная и
конечная вершина пути; длина пути; составной, сложный и простой путь; контур; сильно связный граф; ком-
понента сильной связности.
Рассмотрите три различные возможные представления графов в ЭВМ, которые отличаются объемом зани-
маемой памяти и временем доступа к данным: матрицей смежности, матрицей инциденций и списком смеж-
ности. Так, матрица смежности обеспечивает быстрый доступ к информации о дугах (ребрах) графа, но если в
графе мало дуг (ребер), то эта матрица будет содержать гораздо больше пустых клеток, чем заполненных. Дли-
на списка смежности пропорциональна числу дуг (ребер) в графе, однако при пользовании этим списком время
получения информации о дуге (ребре) увеличивается. Заметьте, что выбор наилучшего представления опреде-
ляется требованиями конкретной задачи. Если в графе много вершин, причем каждая из них связана лишь с
небольшим количеством других вершин, список смежности оказывается выгоднее, поскольку он занимает
меньше места, а длина просматриваемых списков дуг (ребер) невелика. Если же число вершин в графе мало, то
лучше воспользоваться матрицей смежности: она будет небольшой и потери при хранении даже сильно разре-
женной матрицы будут незначительны. Для закрепления знаний о возможных представлениях графов построй-
те матрицу смежности, матрицу инциденций и список смежности для заданных ориентированного и неориен-
тированного графов, а также решите обратную задачу.
4.2. Алгоритмы поиска в невзвешенных графах
Работая с графами, часто приходится выполнять некоторое действие по одному разу с каждой из вершин
графа. Например, некоторую порцию информации следует передать каждому из компьютеров сети. Подобный
обход вершин графа можно совершать двумя различными способами. При обходе в глубину проход по выбран-
ному пути осуществляется настолько глубоко, насколько это возможно, а при обходе по уровням равномерно
двигаются вдоль всех возможных направлений. Изучите эти два способа подробно, рассмотрите и проанализи-
руйте алгоритмы их реализации. Для некоторых графов определите вручную порядок посещения узлов при об-
ходе в глубину и по уровням, начиная с заданной вершины.
При решении практических задач (например, планирование дорожного строительства, компьютерной сети
и т.п.), формулируемых в терминах графов, бывает важно определить не только число компонент связности
неориентированного графа или число компонент сильной связности ориентированного графа, но и сами компо-
ненты. Алгоритмы определения компонент связности и сильной связности графа основаны на использовании
матриц связности и сильной связности графов, соответственно. Познакомьтесь с понятиями матрицы достижи-
мости, матриц связности и сильной связности. Рассмотрите алгоритм Уоршелла, вычисляющий матрицу дос-
тижимости, на основе которой можно получить матрицу связности или матрицу сильной связности. Используя
алгоритм Уоршелла для некоторого ориентированного графа с небольшим числом вершин определите вручную
его компоненты сильной связности. Заметьте, что в задачах, возникающих на практике, число вершин графа
очень велико и ручной метод выделения компонент является нерентабельным. Рассмотрите алгоритм выделе-
ния компонент связности или сильной связности, реализуемый на компьютере.
Познакомьтесь с понятиями двусвязного графа, компоненты двусвязности графа и точки сочленения.
Анализ компонент двусвязности (например, компьютерной сети) показывает, насколько она устойчива при раз-
рушениях отдельных узлов. Если граф, образованный компьютерами сети, двусвязен, то сеть сохранит способ-
ность функционировать даже при выходе из строя одного из компьютеров. Заметьте, что найденные точки со-
членения определяют компоненты двусвязности графа. Точки сочленения можно обнаружить с помощью ме-
тода грубой силы, удаляя из графа поочередно каждую вершину и пользуясь одним из двух алгоритмов обхода

Страницы