Задачи для самостоятельного решения

↑

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

Задачи для самостоятельного решения

1. Найти максимальные потоки для всех пар вершин в сетях.

a)

b)

x₈

c)

3.3. Задача о многополюсных путях с максимальными

пропускными способностями

Пусть дана ориентированная сеть  с пропускными способностями дуг  ≥ 0, (x, y) Î E.В задаче о многополюсных путях с максимальными пропускными способностями необходимо для каждой пары вершин x, y ÎV найти соединяющий x и y путь (если он существует), имеющий максимальную пропускную способность.

Пронумеруем вершины сети и построим матрицу пропускных способностей С= | c_ij | _nxn (n = |V | ) с элементами

и матрицу путей T = | t_ij | _nxn с элементами t_ij = j .

Алгоритм решения задачи о многополюсных путях с максимальными пропускными способностями подобен алгоритму Флойда поиска минимальных путей для каждой пары вершин сети.

Шаг 1. Положить k = 0, и положить матрицы  с ,  

Шаг 2. Построить матрицы , по матрицам и , вычисляя их элементы по формулам:

.

Шаг 3. Если k + 1 < n , то положить k := k +1 и перейти к шагу 2.

Если k+1 = n , то матрица C ⁿ дает искомые максимальные пропускные способности для пар вершин сети.

Путь с максимальной пропускной способностью от вершины x_i к вершине x_j строится по элементам матрицы Tⁿ . Элемент  указывает промежуточную вершину x_m в пути от вершины x_i к вершине x_{j .}  Находим и , которые указывают очередные промежуточные вершины. Если , то вершина x_m непосредственно следует за вершиной x_i (непосредственно предшествует вершине x_j ).  Процесс завершаем при получении номера вершины непосредственно следующей за x_i и номера вершины непосредственно предшествующей x_j .

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

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

.

На последующих итерациях получим:

.

Матрица C⁵  дает значения максимальных пропускных способностей путей между вершинами. Например, максимальная пропускная способность путей между третьей и пятой вершинами равно 11. Сам путь с указанной пропускной способностью строим по матрице T⁴. Получим x₃ ®  x₄ ® x₅ .

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



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману