Решение практических заданий по дискретной математике (стр. 4 из 4)
.Шаг 3. Одна из временных меток превращается в постоянную:
Шаг 4.
Следовательно, возвращаемся на второй шаг.2-я итерация.
Шаг 2.
Шаг 3.
Шаг 4.
Переход на второй шаг.3-я итерация.
Шаг 2.
Шаг 3.
Шаг 4.
Переход на второй шаг.4-я итерация.
Шаг 2.
Шаг 3.
Шаг 4.
Переход на второй шаг.5-я итерация.
Шаг 2.
Шаг 3.
Шаг 4.
Конец первого этапа.Следовательно, длина кратчайшего пути равна
.Этап 2. Построение кратчайшего пути.
1-я итерация.
Шаг 5. Составим множество вершин, непосредственно предшествующих
с постоянными метками : 
Проверим равенство 
для этих вершин:
т.е. 
т.е. 
Включаем дугу
в кратчайший путь, 
Шаг 6.
Возвращаемся на пятый шаг.2-я итерация.
Шаг 5.
Включаем дугу
в кратчайший путь, 
.Шаг 6.
. Завершение второго этапа.Следовательно, кратчайший путь построен. Его образует последовательность дуг:
.Окончательно, кратчайший путь от вершины
до вершины v6 построен. Его длина (вес) равна . Сам путь образует последовательность дуг: 
б) Определим максимальный поток
через сеть G. Для этого используем алгоритм Форда-Фалкерсона. 
Выбираем произвольно путь из вершины v1 в вершину v6 . Пусть это будет путь
. Минимальную пропускную способность на этом пути, равную 10, имеет дуга , т.е. 
Увеличим на этом пути поток до 10 единиц. Дуга становится насыщенной. Дуга имеет на данный момент пропускную способность, равную 10.Путь
Следовательно, поток на этом пути можно увеличить на 9 единиц. Дуги 
становятся насыщенными.Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v1 по насыщенным дугам
и получаем его величину
единиц.8. Используя алгоритм Краскала, построить остов с наименьшим весом для неориентированного взвешенного графа
, у которого 
, если заданы веса (длины) ребер: 
□ Построим граф G :
1. Упорядочим ребра в порядке неубывания веса (длины):
2. Возьмем ребро u1 и поместим его в строящийся остов.
Возьмем ребро u2 и поместим его в строящийся остов (т.к. оно не образует с предыдущим ребром цикла).
Берем ребро u3 и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).
Берем ребро u4 и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).
Берем ребро u5 и помещаем его в строящийся остов (т.к. оно не образует цикла с предыдущими ребрами).
Ребра
не рассматриваем, т.к. они образуют циклы с предыдущими ребрами.Проверим окончание алгоритма. Число входящих в остов ребер равно 5. Заданный граф имеет п = 6 вершин и
. Таким образом, остов содержит все вершины заданного графа G .Вес (длина) построенного остова
равен
.Литература
1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.
2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энерго атомиздат, 1987. – 496 с.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.
4. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006. - 400 с.
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: ФИЗМАТЛИТ, 2005. – 416 с.
6. Хаханов В.И., Чумаченко С.В. Дискретная математика ( конспект теоретического материала). – Харьков: ХНУРЭ, 2003. – 246 с.
7. Богданов А.Е. Курс лекций по дискретной математике.–Северодонецк: СТИ, 2006. – 190 с.