- •1(18).Основное понятие теории графов. Определения и разновидности графов. Способы задания графов: аналитический, геометрический, матричный. Изоморфизм графов. Примеры.
- •2(19). Операции над графами с примерами.
- •3(20) Маршруты. Цепи. Циклы.
- •4(21) Метрические характеристики графа
- •5(22) Понятие сети. Матрица весов.
- •6(23) Алгоритм Беллмана-Мура (алгоритм корректировки меток)
- •7(24). Деревья и их свойства. Лес.
- •8(25). Задача об остове экстремального веса.
- •9(26) Эйлеровы графы и циклы. Алгоритм Флерн. Гальмитоновые графы и циклы
- •10(27) Планарные графы. Укладка графа. Теорема Эйлера. Теорема Понтрягина-Куратовского. Понятие искаженности и толщины непланарных графов
- •11(28) Алгоритм плоской укладки
- •2 Итерация
- •12(29). Раскраски графов
- •13(30)Потоки в сетях.
- •14(31) Потоки минимальной стоимости.
- •15(32)Элементы теории кодирования. Кодирование как способ представления информации.
- •16(33) Общий критерий взаимной однозначности. Теорема Маркова. Примеры
- •17(34) Неравенство Макмиллана.
- •18(35) Коды с минимальной избыточностью. Примеры.
- •19(36). Оптимальное кодирование Хаффмана. Решение задачи о построении кодов с минимальной избыточностью для двоичного кодирования.
- •20(37) Самокорректирующиеся коды. Коды Хэмминга. Алгоритм построения кода Хэмминга
- •21(38) Обнаружение ошибки в кодах Хемминга.
14(31) Потоки минимальной стоимости.
Рассмотрим задачу находящую потока заданного величиной Q от skt в g=(v,e,ῼ,D) в которой каждая дуга характеризующая простую стоимость С ∊ῼ и не отри-й стоимостью d ∊D пересылки единичного потока из в вдоль дуги если θ> где волна макс потока в сети g от skt, то решения нет, если θ<= то мажет быть определено несколько различных потоков в вел-ы θ от skt. Математическая модель заданная следующим образом: Нужно минимизировать , ,где - Это поток по дуге при ограничениях:
ограничение: ∀ ∊Е , 0<=Φ <=C
для наг вер-а S∊V; это уравнение истока.
Для конечной вершины t∊V Уравнение Стока.
∀ уравнение Балажа(Условие сохранения потока)
Если - кратчайший путь от skt в сети g=(v,E,D);Cmin( ) min из пропускной способности дуг входящих в этот путь (кратчайший путь).θ<Cmin( )- то задача имеет тривиальное решение . Весь поток θ направляемый вдоль пути Общее решение задачи строиться следующим образом. Сначала находиться кратчайший путь от skt и величина max возможного потока вдоль этого пути. Если окажется что θ<= то задача решена. В Противном случае сеть модернизируют специальным образом. Затем опять находим кратчайший путь от skt и Макс Возможных потоков Вдоль этого Пути в Модернизированной сети. Процедуры модернизации сети и нахождения кратчайшего пути в ней повторяются до тех пор пока Либо Нужное кол-о θ Будет перенаправлена, либо возьмёт сеть в которой нет пути от skt Что означает отсутствие решения у исходной задачи. Модернизация сети дополняется только определённым порядком: Пусть g=(v,E,ῼ,D) исходная сеть v-множество вершин: Е-множество рёбер: ῼ множество весов (пропускной способности дуг): D набор стоимости единичного потока из в по дуге . Модернизация относительно данного потока сеть строиться следующим образом:
1) =V т.е число и набор вершин в мод-й сети не изменяется.
2) где F некоторое множество фиксированных дуг. Т. О после модернизации число дуг сети увеличиваться.
3) Если дуга и ϕ >0 то дуга фикс Дуга. Включая множество F При этом следует что =ϕ этот пункт применим только к дугам по которым проходит поток ϕ относительно которого происходит модернизация сети.
4) Для всех ненасыщенных дуг где нет противоположного потока в том числе и для некоторых дуг с потоком относительно которого происходит мод-я сети т.е (31) ϕ <c ϕ , то получим что
5)Для всех насыщенных дуг Е, ϕ получиться что ,
Пример: Пусть матрицами ῼ и D заданы произведение спос-и дуг сети стоимости транспортной единице потока вдоль всех дуг. Требования :1) построить макс поток Skt пути разложить отдельно-й S oт t.Построить поток величины θ=[3/4ϕmax] имеющих минимальную стоимость.(матрица в круглых скобках )
ῼ |
s |
|
|
|
|
t |
s |
- |
13 |
11 |
- |
- |
- |
|
- |
- |
11 |
6 |
- |
- |
|
- |
- |
- |
11 |
13 |
17 |
|
- |
- |
- |
- |
9 |
- |
|
- |
- |
- |
- |
- |
10 |
t |
- |
- |
- |
- |
- |
- |
D |
s |
|
|
|
|
t |
||
s |
- |
9 |
10 |
- |
- |
- |
||
|
- |
- |
12 |
9 |
- |
- |
||
|
- |
- |
- |
7 |
9 |
13 |
||
|
- |
- |
- |
- |
14 |
- |
||
|
- |
- |
- |
- |
- |
9 |
||
t |
- |
- |
- |
- |
- |
- |
Построим рисунок соответственной сети. 1 число стоит транспортного и единичного потока вдоль дуги(d). 2 число прои-я спос-ть дуги(с).
Найдём макс поток от skt по алгоритму Форда-Фаркенсона.
Этап1:
S ( ) насыщенна
S t ( ) насыщенна
S ( ) насыщенна
S ( ) насыщенна
Больше путей нет θ=[3/4 ]=[3/4*24]=18 единиц