Построение максимального потока

↑

⇐ ПредыдущаяСтр 4 из 5Следующая ⇒

Построение максимального потока

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

Для построения маршрута в графе воспользуемся "жадным алгоритмом" [8], адаптировав его к нашей задаче.

Шаг 1. Начинаем движение из вершины, в которую совсем не поступает ресурсов (лучше выбрать донора). Кроме того, из всех вершин лучше выбрать ту, в которой берет начало ребро с наибольшим весом.

Шаг 2. Выбираем ребро с наибольшим весом, исходящее из этой вершины.

Шаг 3. Идем, следуя направлению ребра.

Шаг 4. Пройдя по ребру, "помечаем" его, чтобы не пройти во второй раз, то есть записываем начальную и конечную вершины отрезка.

Шаг 5. Присоединив таким образом следующую вершину к маршруту, возвращаемся к шагу 2. Если из вершины нет выхода, заканчиваем построение маршрута (обычно конечной вершиной является потребитель (денег, труда, продуктов; в нашем случае это еще и обмен деньгами).

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

В нашей выборке определились следующие три маршрута:

1. ДД – ПП – ОТ – ОС – ОТ – ПД = (Д29+П19) + (Т19) + (Т21+С22) + (Т28+С20) + (Д15+Т17) = 48 + 19 + 43 + 48 + 32 = 190; средняя интенсивность маршрута: 190/5 = 38.

2. ДД – ОТ – ОС – ОТ – ПП – ОТ – ДД – ПД = (Д23+Т21) + (Т21+С22) + (Т28+С20) + (П15+Т16) + (Т19) + (Т15) + (Д40+П15) = 44 + 43+48+31+19+15+55 = 255; средняя интенсивность маршрута: 255/7 = 36.

3. ДД – ПП – ОТ – ДД – ПД = (Д29+П19) + (Т19) + (Т15) + (Д40+П15) = 38+19+15+55 = 127; средняя интенсивность маршрута: 127/4 = 35.

Построение минимального остовного дерева

Остовным деревом связного графа G называют любой его подграф, содержащий все вершины графа, связный и не имеющий циклов. Кроме того, он обладает следующими свойствами: число ребер графа ровно на единицу меньше числа вершин; любые две вершины графа можно соединить единственной (и притом простой) цепью.

Остовное дерево, сумма весов ребер которого является максимальной (или минимальной – в зависимости от задачи) – называется минимальным остовным деревом (МОД). При построении МОД направление ребра не учитывается.

Алгоритм построения МОД:
Шаг 1. Выбираем ребро с максимальным весом. Теперь это ребро и инцидентные ему вершины принадлежат МОД.
Шаг 2. Из каждой вершины выбираем инцидентное ей ребро с максимальным весом, и присоединяем вместе с вершиной к МОД.
Шаг 3. Необходимо проверять, нельзя ли эту новую вершину присоединить к уже существующему МОД через другое ребро с большим весом. Для этого определяется, с какими из вершин уже принадлежащими МОД, связана новая вершина. Если находим ребро с весом большим, чем в пункте 2, то "забываем" про старое ребро и присоединяем вершину к МОД.
Шаг 4. Устанавливаем, все ли вершины уже принадлежат МОД. Если нет, переходим к шагу 2. Если да, заканчиваем построение МОД.

В отличие от максимального потока, у графа может быть только одно минимальное остовное дерево.

Минимальное остовное дерево обмена ресурсами между домохозяйствами имеет следующий вид (рис. 1).

Минимальное остовное дерево показывает, что вершин с наибольшей инцидентностью две: "Донор денег" и "Обмен связями". Кроме того, сравнив несколько способов обработки первичных данных, мы можем утверждать, что денежные и продуктовые потоки являются наиболее устойчивыми. В денежно-продуктовом обмене участвуют следующие вершины: "Доноры денег", "Доноры продуктов", "Потребители денег", "Потребители продуктов", "Независимые по связям", "Обмен денег", "Обмен связями". Потоки связей и услуг проходят через "Обмен связями". МОД как бы распадается на две части с двумя центрами. "Донор денег" является центром денежных и продуктовых потоков. "Обмен связями" – центр трудовых и информационных потоков. Два этих центра связаны между собой двойным потоком – денег и связей (компромиссный вариант), который направлен от ДД к ОС.

Познавательные статьи:



Техника нижней прямой подачи мяча

Комплекс физических упражнений для развития мышц плечевого пояса

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов