Студопедия Главная Случайная страница Обратная связь

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

Постановка задачи. Одной из задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой вершине t





Одной из задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s графа (источника) к некоторой вершине t (стоку). При этом каждой дуге (граф ориентированный) (ij) приписана некоторая пропускная способность C(i, j), определяющая максимальное значение потока, который может протекать по данной дуге. Со­держательных интерпретаций задачи достаточно много, и, бе­зусловно, они усилят и сделают более понятными сложные за­нятия по этой проблематике.

Метод решения задачи о максимальном потоке от s к t был предложен Фордом и Фалкерсоном, и их «техника меток» со­ставляет основу других алгоритмов решения многочисленных задач, являющихся обобщениями или расширениями указан­ной задачи.

Одним из фундаментальных фактов теории потоков в сетях является классическая теорема о максимальном потоке и ми­нимальном разрезе. Разрезом называют множество дуг, удале­ние которых из сети приводит к «разрыву» всех путей, веду­щих из s в t. Пропускная способность разреза — это суммарная пропускная способность дуг, его составляющих. Разрез с мини­мальной пропускной способностью называют минимальным разрезом.

Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности минимального разре­за, разделяющего s и t, причем существует поток, достигающий этого значения.

Теорема устанавливает экви­валентность задач нахождения максимального потока и минима­льного разреза, однако не определяет метода их поиска.

Пример. Показана сеть (рис.10), источник — вершина 1, сток — вер­шина 6, в скобках у дуг указаны их пропускные способности. Минимальный разрез — дуги (1, 2) и (3, 4), следовательно, со­гласно теореме максимальный поток равен 4. Разрез определен путем простого перебора. Логика его «лобового» поиска очевид­на. Осуществляем перебор по дугам путем генерации всех воз­можных подмножеств дуг. Для каждого подмножества дуг проверяем, является ли оно разрезом. Если является, то вычисляем его пропускную способность и сравниваем ее с минимальным значением. При положительном результате сравнения запоми­наем разрез и изменяем значение минимума. Удачный выбор данных позволяет сделать программный код компактным, но очевидно, что даже при наличии различных отсечений в перебо­ре метод применим только для небольших сетей. Однако, как найти максимальный поток, т. е. его распределение по дугам, по-прежнему открытый вопрос.

«Техника меток» Форда и Фалкерсона заключается в после­довательном (итерационном) построении максимального пото­ка путем поиска на каждом шаге увеличивающейся цепи, то есть пути (последовательности дуг), поток по которой можно увеличить. При этом узлы (вершины графа) специальным обра­зом помечаются. Отсюда и возник термин «метка».

Пример. Рядом с пропуск­ными способностями дуг указаны потоки, построенные на этих дугах. На рисунке по­ток через сеть равен 10 и найдена увели­чивающаяся цепочка, выделенная «жирны­ми» линиями. Обра­тите внимание на ориентацию дуг, входящих в цепочку. По данной цепочке можно пропустить поток, равный 1, пропуск­ная способность дуги (5, 6). Изменяем суммарный поток, его значение становится равным 11. Поток увеличен, необходимо продолжить поиск увеличивающихся цепочек; если окажется, что построить их нельзя, то результирующий поток максима­лен. Заметим, что для данного примера это значение потока окончательное. Обратите внимание на то, как изменен поток на дугах сети в зависимости от их ориентации.

 

 

рис.10

 


рис.11

 







Дата добавления: 2014-11-10; просмотров: 1166. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


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


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

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

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

Закон Гука при растяжении и сжатии   Напряжения и деформации при растяжении и сжатии связаны между собой зависимостью, которая называется законом Гука, по имени установившего этот закон английского физика Роберта Гука в 1678 году...

Гальванического элемента При контакте двух любых фаз на границе их раздела возникает двойной электрический слой (ДЭС), состоящий из равных по величине, но противоположных по знаку электрических зарядов...

Сущность, виды и функции маркетинга персонала Перснал-маркетинг является новым понятием. В мировой практике маркетинга и управления персоналом он выделился в отдельное направление лишь в начале 90-х гг.XX века...

Разработка товарной и ценовой стратегии фирмы на российском рынке хлебопродуктов В начале 1994 г. английская фирма МОНО совместно с бельгийской ПЮРАТОС приняла решение о начале совместного проекта на российском рынке. Эти фирмы ведут деятельность в сопредельных сферах производства хлебопродуктов. МОНО – крупнейший в Великобритании...

Studopedia.info - Студопедия - 2014-2025 год . (0.011 сек.) русская версия | украинская версия