Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Решение. Этап 1.

Читайте также:
  1. Глава 3. Решение.
  2. ДУВП. Решение. Общее решение. Общий интеграл. Промежуточный интеграл. Первый интеграл. Понижение порядка с помощью независимых первых интегралов.
  3. ЛНДУ в ЧППП. Общее решение.
  4. Межличностные конфликты, их конструктивное разрешение.
  5. Решение.
  6. Решение.
  7. Решение.

Шаг 1.

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

путь : , значит, по этому пути пропускаем поток в 2 единицы;

путь : , значит, по этому пути пропускаем поток в 3 единицы;

путь : , значит, по этому пути пропускаем поток в 1 единицу.

Шаг 2. Путь содержит насыщенную дугу . Больше нельзя добавить потока по этому пути. Пути , и содержат насыщенные дуги.

Но путь имеет две дуги, которые еще ненасыщенные.

Шаг 3. Увеличиваем поток по найденному пути: . Значит, на этом пути поток увеличиваем на 1 единицу, и тем самым дуга стала насыщенной.

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

Этап 2.

Выясним, является ли построенный поток максимальным по величине. Строим сеть, на которой отметим все вершины и ненасыщенные дуги. На этой сети разность пропускных способностей дуги и проходящего по ней потока обозначим числом в квадратных скобках.

Шаг 5, 6. Вершину пометить . На шаге 6 предусматривается пометка вершин, смежных с вершиной I, соединенных ненасыщенными дугами. Но на построенной сети таких вершин нет.

В результате вершина S оказалась непомеченной.

Этап 3. Шаг 8. Так как вершина S непомеченная, то поток, сформированный на сети, получился максимальным.

Строим разрез на сети. Разбиваем множество вершин на два подмножества: A и B. Так как только одна вершина оказалась помеченной, то множество A состоит из одной вершины I, а остальные образуют множество B:

.

Проводим разрез , который состоит из дуг и :

.

Определяем величину максимального потока :

(ед.),

 

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

 


Дата добавления: 2015-08-09; просмотров: 176 | Нарушение авторских прав


Читайте в этой же книге: Введение | Виды графов | Представление графов с помощью матриц | Потоки в сетях | Задача о максимальном потоке | О максимальном потоке | Алгоритм Форда-Фалкерсона | Этап 3. |
<== предыдущая страница | следующая страница ==>
Графы со многими источниками и стоками| Решение. Этап 1.

mybiblioteka.su - 2015-2024 год. (0.007 сек.)