Шапорев С.Д. Дискретная математика - файл n12.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скачать

n12.doc





.

9 Шаг 3. .

. Шаг 4. Нет.

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

12 7 9 ,

10 13 9 ,

9 .

Шаг 3. .

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

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

Шаг 3. ,

Шаг 4. Нет.

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

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

Шаг 3. ,

Шаг 4. Да. Конец первого этапа.

Этап 2. Кратчайший путь здесь очевиден, это путь . Максимальный поток по этому пути Так как , то ; требуется модификация сети.

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

По четвертому пункту правил характеристики

9(6) всех дуг, где нет потока останутся без измене-

-13(17) ний; для дуг потока , то есть только

9(13) для дуги изменятся характеристики

7(11) 9(14)

12(11) По пятому пункту правил для насыщенной

(0) 13(6) 9(10) дуги В ре-

зультате имеем новую сеть . Не-

-10(11) 9(13) обходимо найти кратчайший путь между и

в этой сети. Так как теперь есть дуги с отрицательным весом, следует применить алгоритм Беллмана – Мура.

Этап 1.

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

2б). ,

2бб). Да, корректировка очереди.

2бв). .

2б). ,

2бб). . Нет, корректировка очереди не проводится.

Шаг 3. Ш? Нет.

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

2б). ,

2бб). Да, корректировка очереди.

2бв). .

2б). ,

2бб). . Да. 2бв). .

Шаг 3. Ш? Нет.

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

2б). ,

2бб). Нет, корректировка очереди не проводится.

2б). ,

2бб). Нет.

2б). ,

2бб). Да, корректировка очереди.

2бв). .

2б). ,

2бб). Да, корректировка очереди.

2бв). .

Шаг 3. Ш? Нет.

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

2б). ,

2бб). Нет, очередь не корректируется.

Шаг 3. Ш? Нет.

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

2б). ,

2бб). Нет, очередь не корректируется.

Шаг 3. Ш? Нет.

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

Шаг 3. Ш? Да. Конец первого этапа алгоритма Беллмана – Мура.

Итак, кратчайший путь найден. Это путь . Его вес Общий поток по двум уже рассмотренным путям равен , то есть требуется еще одна модификация сети.

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

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