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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Нахождение минимальной стоимости в транспортной сети

Информация:

Тип работы: курсовая работа. Добавлен: 09.07.2012. Сдан: 2010. Страниц: 10. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Федеральное агентство по образованию
Воронежский государственный технический университет
Естественно-гуманитарный факультет
Кафедра систем автоматизированного проектирования и информационных систем
             
             
             
             
             
             
             
             
             
            КУРСОВАЯ РАБОТА
по дисциплине      Дискретная математика
Тема Нахождение минимальной стоимости в транспортной сети_______ 

Выполнил студент    ИС-091      Юшин Н.О.
                                Группа      Подпись, дата                 Инициалы, фамилия
Руководитель      д.т.н. профессор Белецкая С.Ю.
         Подпись, дата           Инициалы, фамилия
Защищена     Оценка
                      Дата 
 
 
 
 

Воронеж-2010
 


СОДЕРЖАНИЕ 

Введение
1 Теоретическая  часть
1.1 Основные понятия теории графов
2 Транспортная задача
      2.1Основные  понятия.
      2.2Алгоритм поиска в ширину
      2.3 Увеличение потока (или Алгоритм  Форда-Фалкерсона)
      2.4 Алгоритм Беллмана-Форда 
Список использованной литературы
Приложение.Текст  задачи
 

          Введение

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

    Теоретическая часть
      Основные  понятия теории графов
       Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами графа, линии - ребрами графа. С графами, сами того не подозревая, мы встречаемся довольно часто. Многим, например, известна схема московского метрополитена. Схема эта – не что иное,  как граф, где  вершины — конечные станции и станции пересадок, ребра - пути, соединяющие эти станции.
       Основы  теории графов как математической науки  заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня  эта задача стала классической. 

 

  
    Карта кенигсбергских мостов.

    Граф  Эйлера к задаче о  кенигсбергских мостах.
       Бывший  Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов  на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта  города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться  в начальный пункт, причём на каждом мосту следовало побывать только один раз.
       Прогуляться по городским мостам (рис. 1) предложили и Эйлеру. После безуспешной попытки  совершить нужный обход он начертил упрощённую схему мостов. Получился  граф, вершины которого — части  города, разделённые рекой, а ребра  — мосты (рис.2).
       Прежде  чем обосновать невозможность требуемого маршрута, Эйлер рассмотрел и другую, более сложную карту (рис. 3). 


    Карта кенигсбергских мостов из альбома Эйлера.
       В итоге он доказал общее утверждение: для того чтобы можно было обойти все ребра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнения следующих двух условий:
       1) из любой вершины графа должен  существовать путь по его ребрам  в любую другую вершину (графы,  удовлетворяющие этому требованию, называются связными);
       2) из каждой вершины должно выходить  чётное количество рёбер.
       Замкнутый путь, проходящий по одному разу по всем ребрам графа, называют с тех пор эйлеровым циклом.
       Если  отбросить условие возвращения  в исходную вершину, то можно допустить  наличие двух вершин, из которых  выходит нечётное количество рёбер. В этом случае начинать движение следует  с одной из этих двух вершин, а  заканчивать — в другой.
       В случае с кенигсбергскими мостами  при каждой из четырёх вершин нечетное число рёбер, так что нет не только эйлерова цикла, но и пути из одной вершины в другую, проходящего  по всем ребрам графа.
       Замкнутый путь по ребрам графа, проходящий по одному разу через все  вершины, называют гамильтоновым циклом. Интересно, что в отличие от эйлерова цикла условия существования на произвольном графе гамильтонова цикла до сих пор не установлены.
       Сформулируем  кратко основные положения современной  теории графов. Для этого введем следующие определения. Если ребро соединяет две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром, называются смежными. Ребро, когда две вершины, соединяемые им, совпадают, называется петлей. Число ребер, инцидентных вершине называется степенью вершины. Если два ребра инцидентны одной и той же паре вершин, они называются кратными; граф, содержащий кратные ребра, называется мультиграфом. 


    Виды  графов.
       Граф 1, изображенный на рисунке 4, содержит четыре вершины {1, 2, 3, 4} и семь ребер {а, b, с, d, e, f, g}. Ребро а инцидентно вершинам 2 и 4; ребро g инцидентно только вершине 3 и является петлей, вершины 2 и 3 смежны, а вершины 1 и 4 не смежны; ребра d и f - кратные; степень вершины 2 равна 4.
       Ребро, соединяющее две  вершины и имеющее  направление от одной  вершины к другой, называется направленным или ориентированным и изображается стрелкой. Граф, в котором все ребра - ориентированные, называется ориентированным графом (орграфом); ребра орграфа называют дугами. Кратные дуги – дуги, имеющие не только общие вершины, но и совпадающие по направлению. Граф 2, изображенный на рис.4, - ориентированный; дуги d и f – кратные.
       Граф  считается однозначно заданным, если заданы множество его вершин, множество  ребер и указаны все инцидентности (т. е. указано, какие вершины какими ребрами соединены). Наиболее наглядно граф задается рисунком; однако не все  детали рисунка одинаково важны; в частности, несущественны геометрические свойства ребер (длина, кривизна и т.д.) и взаимное расположение вершин на плоскости. Для машинной обработки  более удобны символические представления  графов, в которых несущественных геометрических деталей нет.
       Примером  символического представления графов является представление списками вершин и ребер. Вот как рассмотренный  выше граф 1 задается списком вершин {1, 2, 3, 4} и списком ребер, в котором для каждого ребра указана пара инцидентных ему вершин:
а: (1, 2)
b: (1, 3)
с: (2, 3)
d: (2, 4)
е: (3, 4)
f: (2, 4)
g: (4, 4)
       Такой же список ребер имеет и граф 3 (рис. 4); поэтому графы 1 и 3 равны, хотя их рисунки заметно отличаются.
       Для неориентированного ребра порядок, в котором указаны соединяемые  им вершины, не важен. Для ориентированного ребра это важно: первой указывается  вершина, из которой выходит ребро. Например, орграф 2 получен из графа 1 введением ориентации ребер; однако, для того чтобы приведенный выше список ребер описывал граф 2, в нем нужно изменить описание ребер c и d - с: (3,  2) и d: (4, 2). 


    Изоморфные  графы.
       Свойства  графа не меняются с изменением положения  его вершин, не зависят от того, какими именно линиями вершины соединены. Два графа, изображенные на рисунке 5, в этом смысле одинаковы: у них  одинаковое число вершин, и если две вершины одного графа соединены  ребром, то вершины второго графа, имеющие те же номера, также соединены  ребром. Это замечание более строго формулируется так:  графы, между вершинами которых можно установить взаимно однозначное соответствие, при котором вершинам, соединённым ребром соответствуют вершины, также соединённые ребром называются изоморфными (от греч «изос» — «равный» и «морфе» — «вид», «форма»).
       Плоские графы («укладывающиеся» на плоскость) обладают многими интересными свойствами. Так, Эйлер обнаружил простую  связь между количеством вершин (В), количеством рёбер (Р) и количеством частей (Г), на которые граф разделяет плоскость:
       В – Р + Г = 2.
       Граф, который можно  изобразить на плоскости  так, чтобы его  ребра не пересекались, называется плоским. Но такие графы встречаются не всегда.
       Если  в неориентированном графе с  n вершинами нет кратных ребер и петель, то максимальное число ребер в нем равно n(n-1)/2.  Это соответствует случаю, когда между любыми двумя вершинами есть ребро; такой граф называется полным. Полный граф «не укладывается» на плоскость без пересечения рёбер. Пример такого графа приведен на рис. 6. Это граф с пятью вершинами, каждые две из которых соединены ребром.  


    Пример  полного графа.
       Граф, не имеющий ребер (состоящий  из изолированных  вершин) называется пустым.
       Маршрут - это последовательность ребер в неориентированном графе, в котором конец каждого ребра совпадает с началом следующего ребра. Число ребер маршрута называется его длиной. Цикл - это замкнутый маршрут, т. е. маршрут, в котором начальная вершина совпадает с конечной. В графе 1 (см. рис. 4) а, с, e - маршрут; a, f, e, b - цикл. В орграфе ориентированный маршрут, т. е. маршрут, в котором все дуги проходятся по их ориентации, называется путем, а путь, являющийся циклом, называется ориентированным циклом. В графе 2 (рис. 4) а, d, e - путь, f, e, с - ориентированный цикл. Иногда в литературе используется и другая терминология: например, замкнутый маршрут именуют контуром, а циклом называют только такой контур, который не пересекает сам себя, т. е. не содержит повторяющихся вершин.
       Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут. Орграф считается связным, если он связан без учета ориентации его дуг. Связный граф с n вершинами содержит не менее n - 1 ребер. Орграф называется сильно связным, если из любой вершины в любую другую существует путь. Граф 2 (рис. 4) -  связный, но не сильно связный, так как в вершину 1 нет путей из других вершин. 


    Пример  неориентированного дерева.
       Дерево - это неориентированный связный граф без циклов. Дерево с n вершинами всегда имеет (n - 1) ребер. Между любыми двумя вершинами дерева существует единственный маршрут (если бы его не было, нарушилась бы связность, а если бы было два маршрута с одинаковыми концами, то получился бы цикл). Поэтому дерево иногда определяется как минимальный связный граф, т. е. граф, в котором удаление любого ребра нарушает связность. Вершина дерева, которая соединена ребром только с одной вершиной, называется висячей вершиной или листом. В любом дереве, содержащем более одной вершины, имеется не менее двух листьев. На рис. 7 граф представляет пример неориентированного дерева. Его листьями являются вершины 1, 6 и 7.
       Ориентированное дерево - это граф с выделенной вершиной (корнем), в котором между корнем и любой вершиной существует единственный путь. При этом возможны два варианта ориентации: либо все пути ориентированы от корня к листьям, либо все пути ориентированы от листьев к корню. Ориентированное дерево можно получить из неориентированного дерева, выбрав в нем любую вершину в качестве корня и один из двух вариантов ориентации дуг. Например, граф на рис. 8 получен из предыдущего графа (см. рис. 7)  выбором вершины 5 в качестве корня и ориентацией дуг от корня к листьям. Если ориентацию всех дуг поменять на противоположную, то получится дерево с ориентацией от листьев к корню; если же поменять ориентацию только у частей дуг, то полученный граф не будет ориентированным деревом.
       В заключение расскажем о классической задаче теории графов, которая называется «задачей о четырех красках». Внимательно  рассматривая географическую карту, можно  заметить, что кроме графов, изображающих железные или шоссейные дороги, есть ещё один — граф, состоящий из границ между странами (областями, районами). Сами границы служат ребрами, а вершинами  этого графа являются точки, в  которых сходятся границы трёх или  более стран. 


    Пример  ориентированного дерева.
 
 
       Одна  из классических задач теории графов называется «задачей коммивояжера»  или «задачей о бродячем торговце».
       Представим  себе торгового агента, который должен побывать в нескольких городах и  вернуться обратно. Известно, какие  дороги соединяют эти города, и  каковы расстояния между ними по этим дорогам. Нужно выбрать самый  короткий маршрут. Это уже не «игрушечная» задача. Например, водитель почтового  автомобиля, вынимающий письма из ящиков, очень хотел бы знать кратчайший маршрут, как и водитель грузовика, развозящий товары по киоскам.  Решить эту задачу очень непросто, особенно когда число вершин графа велико. Поэтому ее решение мы рассмотрим позже, используя не только методы теории графов, но и специальные приемы программирования.
       Вот другая задача, в некотором смысле противоположная задаче коммивояжера. Предполагается проложить железную дорогу, которая соединит несколько  крупных городов. Для любой пары городов известна стоимость прокладки  пути между ними. Требуется найти  наиболее дешевый вариант строительства.
       Интересно, что алгоритм нахождения оптимального варианта строительства довольно прост (чего нельзя сказать о других задачах  теории графов). Продемонстрируем его  на примере дороги, соединяющей пять городов: A, B, C, D и E. Стоимость прокладки пути между каждой парой городов указана в таблице. 

        A B C D E
      A   1,5 1 2 2,5
      B 1,5   1,2 3 0,8
      C 1 1,2   1,1 0,9
      D 2 3 1,1   2,7
      E 2,5 0,8 0,9 2,7  
 
       Сначала строим ту дорогу, которая имеет  наименьшую стоимость. В нашем случае это маршрут B – E. Теперь найдем самую дешевую линию, соединяющую город B или E с каким-то из остальных городов. Это путь между E и C. Включаем его в схему. Далее поступаем аналогично: ищем самый дешевый из путей, соединяющих один из городов B, C, E с одним из оставшихся – A или D. Это дорога между C и A. Осталось подключить к железнодорожной сети город D. Дешевле всего соединить его с C. Получим сеть, изображенную на рисунке 26. 

 

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

Вот мы и приблизились непосредственно к основной теме моей курсовой работы- минимизации  стоимости в транспортной сети, или  транспортной задаче.
      2.Транспортная задача (классическая) — задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.
     Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени  на перевозку).

      Задача (сказка): Вы владелец некоторого завода, выпускающего «Товар», и недавно Вам посчастливилось заключить контракт с одной крупной фирмой, находящейся в другом городе на поставку товаров в их розничную сеть. Так как он находится очень далеко (во Владивостоке), товары придется доставлять авиаперевозкой. В ходе телефонных переговоров Партнер поинтересовался «а на какой объем поставок в день мы можем рассчитывать?». Вы задумались… У Вас есть собственные грузовики (дальнобойщики) осуществляющие транспортировку. Аэропорт находится далековато. Просмотрев накопленную статистику перевозок, Вы выявили, что в собственной области при транспортировке есть некоторые ограничения: на дорогах стоят пункты досмотра груза, весового контроля, некоторые дороги и вовсе ремонтируются. Все это назовем «пропускной способностью» дорог в день. Отталкиваясь от этих условий Вам необходимо узнать: сколько ящиков «Товара» в день вы можете подвозить в аэропорт? При этом, вы хотите эффективно вести бизнес и доставлять товар, кратчайшими маршрутами, т.к. это износ шин, механизмов, в общем амортизационные расходы.
     Итого: сколько ящиков Вы сможете транспортировать в аэропорт в день, учитывая пропускную способность дорог, при этом, чтобы  общее расстояние маршрутов было минимальным?
     Задача  – самая что ни на есть на графах. Решение будет построено постепенно.
Алгоритмы буду, если можно так выразиться, рассказывать, т.к. в сети предостаточно их описаний.
      2.1Основные понятия.
Карта дорог в  нашем случае представляется в виде графа. Вершинами являются перекрестки, а ребра графа – это дороги. Ребрам (дорогам) приписаны их характеристики: расстояние (до след. перекрестка), а  так же пропускная способность в  день. 

В коде граф представляют либо в виде списков смежности, либо матрицы смежности. Для простоты мы будем использовать матрицу смежности. Если в матрице смежности на пересечении [u] и [v] вершины стоит «1» – значит, что эти вершины (перекрестки) соединены ребром (дорогой). Не обязательно обозначать именно «1», в матрице очень удобно можно хранить и иную полезную информацию приписанную ребру: например расстояние, и пропускную способность (в аналогичной матрице).

     На  рисунке изображена матрица, симметричная относительно главной диагонали, т.е. M[u][v] = M[v][u]. Это значит, что нам задан ненаправленный граф и по ребру можно пройти в любом направлении (туда-обратно). Если в матрице M[u][v] = 1, а в обратном направлении M[u][v] = 0, то граф – направленный и можно пройти по ребру только от вершины [u] до [v].
     Пропускные  способности дорог у нас будут  записаны в матрицу C[..][..], которая вообще говоря, представляет собой направленный граф. Ведь дороги нам нужны для того, чтобы проехать от «завода» по направлению в «аэропорт». Направленный граф с заданными пропускными способностями (заводом и аэропортом) называется – сетью.
     Когда для графа необходимо вычислить  определенную характеристику, но не массово  «от всех-ко-всем», а допустим расстояние от одной вершины до остальных, то гораздо удобнее воспользоваться  массивом (меньше памяти). Т.е. допустим в [u] ячейке массива dist[..] будем хранить расстояние до [u] вершины от «завода». Аналогично массивами будем пользоваться, при обходе графа для того, чтобы отмечать уже посещенные вершины (mark), записывать сколько ящиков привезли (push), и откуда мы в вершину приехали (pred).
     ОК. Отлично. Знаем, как преобразовать  нашу карту в граф. А как мы будем доставлять ящики до аэропорта? Нам нужно уметь находить путь от «завода» до «аэропорта». Для этого  будем пользоваться…
     2.2Алгоритм поиска в ширину (breadth first search), BFS.
     Пока  мы учитываем только: смежность (соседство) вершин графа, не рассматривая пропускные способности и расстояния.
BFS является одним из самых основных алгоритмов, составляющих основу многих других.
      Простое описание (рисунок будет ниже). Мы сейчас стоим в некоторой стартовой (завод) вершине [s], из которой по ребрам видны только соседние вершины. И нам очень нужно как можно скорее попасть в вершину [t], которая находится где-то в этом графе. Далее мы поступаем так. Просматриваем по ребрам (а именно свободным дорогам) нашей вершины соседей: есть ли среди них [t]. Если нет, то записываем всех (впервые обнаруженных) соседей в очередь «нужно там побывать». Когда просмотрели всех соседей — отмечаем свою вершину – «тут уже побывали». Достаем первую непосещенную вершину из очереди и идем в нее.
      Продолжаем  поиски таким же образом. При этом те вершины, в которых однажды  побывали — игнорируем (ни шагу назад). Если по дороге встретили [t] – отлично, цель достигнута!
Для того, чтобы не заезжать в одни и те же перекрестки  по нескольку раз, мы будем их отмечать в массиве mark[..]. После осмотра соседей из [u] вершины, ставим отметку mark[u] = 1 – значит, что на [u]-ом перекрестке мы «уже побывали».
На рисунке: в вершинах – написаны порядковые номера

После завершения алгоритма  получим следующую картину:

Отметим основные особенности:
в каждую вершину  мы попадаем ровно (не более чем) один раз
помещаем вершины  в очередь при их первом просмотре
от своего завода мы радиально (волнообразно) находим  остальные вершины в графе
«радиус осмотра» постоянно  увеличивается
когда мы найдем «аэропорт», то количество ребер (дорог) между «заводом»  и «аэропортом» будем минимальным. Т.о. мы быстрейшим осмотром графа найдем «аэропорт»
Смотрим только по свободным  дорогам, по которым можно перевезти  ящики!
      Теперь  мы знаем, как найти путь, по которому можно провезти наши ящики «Товара» в аэропорт. Хорошо… Провезем их по дороге, и отметим это себе на карте. Эту пометку – «сколько ящиков, по какой дороге (ребру) и  в какую сторону мы везем» мы назовем  «поток». Отмечать это будем в  матрице (flow) F[..][..]. Т.е. по дороге из [u] в [v] мы везем F[u][v] ящиков.
      Пора  столкнуться с реальностью –  придется считаться с «пропускной  способностью», которая обозначается матрицей (capacity) C[..][..]. Ведь по дороге от [u] в [v] мы можем провезти не более C[u][v] ящиков. That’s a pity.
Мы поступили дальновидно. Пока мы BFS’ом искали «аэропорт», пока отмечали «посещенные вершины» мы так же отмечали, из какого перекрестка приехали — записывали в массив pred[..]. Т.е. в вершину [v] мы попали из вершины pred[v]. И так же заблаговременно завели еще один полезный массив: push[v], т.е. сколько мы могли бы «толкнуть» ящиков в перекресток [v] по некоторой дороге [u]-[v].
И поддерживали его  в актуальном состоянии: push[v] = min(push[u], C[u][v]-F[u][v]);
      Благодаря этому, пока нам не придется лишний раз «разматывать» траекторию от «аэропорта» до «завода» в обратном порядке, чтобы вычислить, сколько  максимально ящиков мы сможем провести по этому маршруту.
      Push[v] = push[«аэропорт»] = flow = вот! сколько ящиков довезли в аэропорт по найденному пути. Один раз размотаем маршрут и по всем ребрам (дорогам), и добавим «поток» flow ко всем ребрам пути.
      Но, хоть в задаче речь идет о натуральных  величинах: количестве ящиков, пропускной способности и расстояниях, все  же возможно придется столкнуться с  «минусом»… 

2.3 Увеличение потока (или Алгоритм Форда-Фалкерсона)
      Теперь  принимаем во внимание: смежность (соседство) вершин графа, направленные пропускные способности ребер, но пока не рассматриваем  расстояния.
      Когда мы увеличиваем поток (ящиков) от вершины [u] к вершине [v], мы естественно выполняем операцию: F[u][v] += flow, но в обратную сторону мы уменьшаем поток F[v][u] -= flow; Вот почему. Возможна такая ситуация:
На рисунке: на ребрах – подписан (поток / пропускная способность)
В первый раз, пронеся поток в 3 ящика  в вершину [i] и обнаружив ребро [i]-[j]: Мы перевезли min(push[i], C[i][j] – F[i][j]) = min(3, 3-0) = 3 ящика, и отметили это как F[i][j] += 3, а в обратную сторону мы поставили: F[j][i] -= 3.
      Во  второй раз, оказавшись в вершине [j], мы пытаемся протолкнуть min(push[j], C[j][i]-F[j][i]) = min(6, 0-(-3)) = min(6, 3) = 3 в вершину [i]. Против потока +3, мы толкнули -3 ящиков и получили компенсацию потока по этой дороге. Зато в направлении к «аэропорту» в следующей итерации мы дополнительно отправили остальные 3 ящика.
      Интерпретация: из склада [j] мы позвонили в склад [i], и сказали: «Оставьте себе свои 3 ящика – найдите им другое применение, мы вместо них привезли своих 3». Хоть алгоритм сам любезно нашел им применение.
Продолжаем искать поток:
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.