Шапорев С.Д. Дискретная математика - файл n10.doc

приобрести
Шапорев С.Д. Дискретная математика
скачать (1595.4 kb.)
Доступные файлы (14):
n1.doc1008kb.24.06.2000 17:47скачать
n2.doc580kb.29.02.2000 18:08скачать
n3.doc957kb.07.03.2000 15:50скачать
n4.doc492kb.24.06.2000 17:37скачать
n5.doc1198kb.19.04.2000 15:24скачать
n6.doc985kb.19.04.2000 21:35скачать
n7.doc771kb.07.05.2000 17:26скачать
n8.doc992kb.08.05.2000 16:38скачать
n9.doc217kb.08.05.2000 19:26скачать
n10.doc1581kb.26.03.2000 20:59скачать
n11.doc1011kb.31.03.2000 22:04скачать
n12.doc1025kb.31.03.2000 22:09скачать
n13.doc1691kb.05.04.2000 16:10скачать
n14.doc960kb.09.04.2000 12:05скачать

n10.doc





для анализа возможности уменьшения по правилу (4.7.1) меток вершин, не находящихся в данный момент в очереди, но достижимых из нее за один шаг. В процессе работы алгоритма одна и та же вершина может несколько раз вставать в очередь, а затем покидать ее.

Алгоритм Беллмана – Мура состоит из двух этапов. На первом этапе находятся длины кратчайших путей от вершины до всех остальных вершин графа. Этот этап заканчивается при отсутствии вершин в очереди.

Второй этап – построение кратчайшего пути от до совпадает с соответствующим этапом в алгоритме Дейкстры и выполняется по формуле (4.7.3). Опишем подробно все шаги алгоритма.

Этап 1. Нахождение длин кратчайших путей от вершины до всех остальных вершин графа.

Шаг 1. Присвоение начальных значений. - множество вершин в очереди.

Шаг 2. Корректировка меток и очереди.

2а). Удаляем из очереди вершину, находящуюся в самом начале очереди.

2б). Для каждой вершины , непосредственно достижимой из , корректируем ее метку по формуле (4.7.1).

2бб). Если при этом , то переходим к подшагу 2бв), иначе продолжаем перебор вершин по шагу 2б).

2бв). Корректировка очереди. Если не была ранее в очереди и не находится в ней в данный момент, то вершину ставим в конец очереди. Если же уже была когда-нибудь ранее в очереди или находится там в данный момент, то переставляем ее в начало очереди.

Шаг 3. Проверка на завершение первого этапа. Если Ш, то возвращаемся к началу второго шага, если же Ш, то первый этап закончен, то есть минимальные расстояния от до всех вершин графа найдены.

Рассмотрим подробный пример. Пусть граф задан весовой матрицей .

Изобразим эту сеть на рисунке и рассчитаем крат-

(?,4) (?,10,5,-3) чайший путь от узла до узла .

6 Этап 1. Шаг 1.

4 3

(0) -8 -7 Шаг 2. 2а). Ш.

9 (?,8,0) 2б). Пусть - множество вершин

6 5 непосредственно достижимых из

(?,11,4) 8 (?,6,-4) вершины .



2бб). 4
2бв). , надо было поставить в конец очереди, но было пусто, поэтому конец очереди совпал с началом.

2б).

2бб). Да.

2бв).

Шаг 3. Ш? Нет. Переход на начало второго шага.

Вторая итерация. Шаг 2. 2а).

2б).

2бб). 11
2бв).

2б).

2бб). -4<6? Да.

2бв). Вершину надо поставить в начало очереди, но она уже стоит там.

2б).

2бб). 10
2бв).

Шаг 3. Ш? Нет, переход на третью итерацию второго шага.

Третья итерация. Шаг 2. 2а).

2б).

2бб). 4<11? Да.

2бв). Вершину надо поставить в начало очереди, но она уже там.

2б).

2бб). 5<10? Да.

2бв). Вершину передвигаем из конца очереди в начало.

Шаг 3. Ш? Нет, переход на четвертую итерацию второго шага.

Четвертая итерация. Шаг 2. 2а).

2б).

2бб). 8
2бв).

Шаг 3. Ш? Нет.

Пятая итерация. Шаг 2. 2а).

2б).

2бб). -3<5? Да.

2бв).

2б).

2бб). 9<8? Нет.

Шаг 3. Ш? Нет.

Шестая итерация. Шаг 2. 2а).

2б).

2бб). 0<8? Да.

2бв). содержало только вершину и она встала в начало очереди.

Шаг 3. Ш? Нет.

Седьмая итерация. Шаг 2. 2а). Ш. Ш.

Шаг 3. Ш. Конец первого этапа. Найдены минимальные расстояния до всех вершин от первой вершины. Эти расстояния таковы:

Второй этап. Шаг 4. Полагаем Пусть - множество вершин, непосредственно предшествующих

Первая итерация. Включаем дугу в кратчайший путь. Возвращаемся на четвертый шаг.

Вторая итерация. Нет.





Включаем дугу в кратчайший путь. Возвращаемся на четвертый шаг.

Третья итерация. Нет.



Включаем дугу в кратчайший путь. Возвращаемся на четвертый шаг.

Четвертая итерация. Нет.



Включаем дугу в кратчайший путь. Возвращаемся на четвертый шаг.

Пятая итерация. Нет.

Включаем дугу в кратчайший путь. Возвращаемся на четвертый шаг.

Шестая итерация. Да. Задача закончена. Искомый кратчайший путь от вершины до вершины имеет нулевой вес и состоит из следующих дуг
§ 4.9. Деревья (основные определения).
Существует один простой и важный тип графов, которому разные авторы дали одинаковое название – деревья. Деревья отличаются предельной простотой строения. Существует несколько определений дерева.

Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется лесом. Таким образом, деревья являются компонентами леса.

Пусть и Тогда справедлива эквивалентность следующих утверждений:

1). - дерево;

2). - связный граф и

3). - ациклический граф и

4). любые две несовпадающие вершины графа соединяет единственная простая цепь;

5). - ациклический граф, обладающий тем свойством, что если какую- либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

Ориентированный граф называется ориентированным деревом (ордеревом), ес-

ли: 1). существует ровно

одна вершина ,

называемая корнем, ко-

торая не имеет предше-

ствующих вершин, то

есть 2). лю-

бой вершине в

графе непосредственно предшествует ровно одна вершина, то есть Неориентированное дерево можно превратить в ориентированное, выбрав в качестве корня произвольную верши-

ну. На рисунке слева корень графа – вершина

. Пусть . Граф называ-

ется подграфом графа , если и

Подграф графа называется ос-

товным подграфом, если Подграф

графа графа называется остовным поддере-

вом (остовом, каркасом), если и - де-

рево.

Теорема Кэли. Число различных деревьев, которые можно построить на различных вершинах, равно

В этой формуле подсчитывается число всех деревьев с данными вершинами. Многие из этих деревьев изоморфны, и возникает вопрос о числе не изоморфных деревьев среди них. Это более трудная задача, она решается для каждого конкретного случая по алгоритму теории Пойа.


Вернемся к произвольным графам. Матрицей Кирхгофа графа называется матрица , , если Сумма элементов в каждой строке и каждом столбце этой матрицы равна нулю, то есть ,



Кэли (1-1 г.г.) - ский математик.

Кирхгоф (1-1 г.г.) - ский математик.

. Кроме того, из этого следует, что алгебраические дополнения всех

элементов матрицы равны между собой. Матрица Кирхгофа используется для подсчета числа остовов в графе.

Теорема Кирхгофа. Число остовных деревьев в связном графе порядка равно алгебраическому дополнению любого элемента матрицы Кирхгофа
§ 4.10. Задача об остове минимального веса (о кратчайшем остове).

Пусть - связная сеть. В приложениях часто возникает задача о построении остова графа , имеющего наименьший вес. Пусть, например, служит моделью железнодорожной сети, соединяющей пункты , а - расстояние между пунктами и . Требуется проложить сеть телеграфных линий вдоль линий железнодорожной сети так, чтобы все пункты были связаны между собой телеграфной сетью и общая протяженность линий телеграфной сети была наименьшей.


Известно несколько алгоритмов построения кратчайшего остовного дерева. Рассмотрим алгоритм Прима, представляющий собой итерационную процедуру, состоящую из двух шагов и выполняющуюся раз на графе с вершинами.

Пусть и Ш, то есть и - разбиение множества узлов сети на два непересекающихся подмножества. Определим пошаговое расстояние между множествами и следующим образом:

(4.10.1)

где - дуга, соединяющая вершины и .

В алгоритме Прима остовное дерево строится в результате последовательного расширения исходного поддерева. На каждой итерации число вершин и ребер поддерева увеличивается на единицу. Основные шаги алгоритма таковы.


Шаг 1. (Присвоение начальных значений).

Полагают , где - произвольная вершина, Ш.

Шаг 2. (Обновление данных).

Находится ребро такое, что и Полагают

Шаг 3. (Проверка на завершение).

Если , то - искомый остов. В противном случае переходят ко второму шагу.

Пример. Построить остов с наименьшим весом для сети, заданной матрицей смежности вершин. Построим по этой матрице сеть. Поскольку матрица симметрическая, то граф дан неориентированный. Исходный граф изображен внизу следующей



Прим (1-1 г.г.) - ский математик.

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации