Файл: 9. Гамильтоновы графы. Достаточные условия гамильтоновости графа. 17.docx

14. Алгоритм нахождения максимального пути в графе.

Максимальным путем называется путь с максимальным весом . В общем случае, в одном графе может быть несколько максимальных путей.Построение максимального пути во взвешенном ориентированном графе возможно, если в нем нет контуров с положительным весом. Если в графе есть такой контур, то некоторые пути могут иметь сколь угодно большой вес, т.к. каждый обход контура увеличивает вес пути на величину веса этого контура.Для нахождения максимального пути граф G (сеть) должен быть ациклическим, ибо в противном случае может оказаться, что длины некоторых путей не ограничены сверху. Если G_n - ациклический граф, то для любых двух его вершин x_i ? x_j выполняется одно из условий:

• 
  1. x_i предшествует x_j, x_iS_предш (x_j);
  
• 
  2. x_i следует за x_j, x_iS_след (x_j);
  
• 
  3. нет пути между x_i и x_j.,
  

Первое и второе условия одновременно не выполнимы из-за требуемой ацикличности графа.Перед вычислением максимального пути в орграфе необходимо упорядочить вершины графа по алгоритму Фалкерсона.Сам алгоритм вычисления максимального пути чисто перечислительный. Он перебирает все возможные пути от текущей вершины до всех последующих, достижимых из текущей вершины.Пусть d_j - длина максимального пути от вершины x₁ до вершины x_j, тогда величина d_j удовлетворяет следующим рекуррентным соотношениям (1. 2. 5):Соотношения (1. 2. 5) позволяют легко вычислить длины максимальных путей от s = x₁ до вершин, достижимых из вершины s. Сами пути могут быть построены методом последовательного возвращения (второй этап в алгоритме Дейкстры).

15. Потоки в сетях. Построение максимального потока транспортной сети.

2. 
   Потоком по транспортной сети называется целочисленная функция (u), заданная на множестве ребер и обладающая свойствами:
   

1. 
   (uU) (u)  С(u);
   
2. 
   для каждой внутренней (отличной от начала и конца) вершины х графа = , где – множество ребер, входящих в вершину х, – множество ребер, выходящих из вершины х.
   

---

Смысл функции (u) – это количество транспорта, пропускаемого через сеть. Условие (1) означает, что количество транспорта, пропускаемого по ребру u, не превышает пропускную способность ребра. Условие (2) утверждает, что поток, входящий в вершину, равен выходящему (поток в вершинах не скапливается). Обозначим поток, выходящий из начальной вершины, через (х₀), а поток, входящий в конечную вершину, через (z). Очевидно, (х₀) = (z). Задача, связанная с транспортной сетью, – максимизировать поток, пропускаемый по сети.На графике каждое ребро транспортной сети помечается дробью, числитель которой означает пропускную способность ребра, а знаменатель – поток, проходящий по этому ребру.

3. 
   Пусть A  X – множество вершин транспортной сети, х₀А, zA. Разрезом транспортной сети называется множество ребер, входящих в А. Мощностью разреза называется С(А) = (это максимально возможный поток, входящий в А по ребрам разреза).
   

2. 
   5.6.1. (z)  С(А).
   

Доказательство. У множества А могут быть выходящие дуги, по которым часть потока, входящего в разрез, выходит из А. Поэтому (z)  (А), где (А) – поток, входящий в А по дугам разреза. Но (А)  С(А), откуда (z)  С(А).

3. 
   5.6.2 (Форд – Фалкерсон). Максимальный поток по транспортной сети равен минимальной из мощностей разрезов, то есть
   (z) = С(А).
   

Доказательство. Из теоремы 1 имеем (z)  С(А). Чтобы доказать равенство, достаточно построить поток * и найти множество А* такие, что *(z) =

---

С*(А). Тогда из неравенства будет следовать, что поток максимальный, а разрез минимальный.Максимальный поток строим с помощью следующего алгоритма, который состоит из двух частей.1. Насыщение потока. Поток называется насыщенным, если любой путь из x₀ в z содержит ребро u, для которого (u) = С(u) (насыщенное ребро).1.1. Задаем произвольный начальный поток, например, нулевой на всех ребрах.1.2. Ищем путь из x₀ в z. Если путь найден, то переходим к пункту 1.3. Если путь не существует, то переходим к пункту 1.5.1.3. Увеличиваем поток по найденному пути так, чтобы одно из ребер стало насыщенным.1.4. Условно разрываем насыщенное ребро (все, если их несколько) и переходим к пункту 1.2.1.5. Сеть насыщена и разорвана.2. Перераспределение потока. Пометим рекурсивным образом все возможные вершины в сети.2.1. Вершину x₀ пометим –0.2.2. Пусть x_i – любая помеченная вершина, y – смежная с ней непомеченная. Вершину у помечаем +i, если данные вершины соединены ненасыщенным ребром x_i  y, и помечаем –i, если вершины соединены непустым ребром x_i  y. После пометки вершин возможны два случая: вершина z оказалась либо помеченной, либо непомеченной.2.3. Вершинаz оказалась помеченной. Значит, существует последовательность помеченных вершин от х₀ к z. В этой последовательности каждая последующая вершина помечена номером предыдущей со знаком + или –. Перераспределим поток на соответствующем маршруте, увеличивая его на ребрах, ориентированных по направлению движения от х₀ к z, и уменьшая на ребрах, ориентированных в противоположном направлении. Это можно делать до тех пор, пока одно из ребер не станет насыщенным или пустым. При этом суммарный поток по сети увеличится, так как увеличится поток, выходящий из вершины от х₀. Далее снова переходим пункту 2.1.2.4. Вершинаz оказалась непомеченной. Это означает конец работы алгоритма, то есть полученный поток * является максимальным.Действительно, пусть А* – множество всех непомеченных вершин. Тогда ребра, входящие извне в эти вершины, насыщенные, а выходящие – пустые. Множество

---

А* определяет разрез, так как х₀А, zA. Так как входящие в А* ребра насыщенные, то *(А*) = С(А*). Так как выходящие из А* ребра пустые, то весь входящий в А* поток скатывается в z, и *(z) = *(А*) = С(А*).Работа алгоритма завершится за конечное число шагов, так как после каждого шага поток увеличивается на целое число, а сверху он ограничен пропускной способностью сети. Это доказывает теорему.

---

16. Сетевой график. Правила построения сетевых графиков.

Сетевой график представляет собой ориентированный граф, в котором вершины соответствуют событиям, а дуги – работам.События на сетевом графике (графе) изображаются вершинами графа, а работы – ориентированными дугами, показывающими связь между ними. У сетевого графика есть начальная (исходная) вершина, не имеющая входящих дуг, и конечная вершина (завершающее событие), не имеющая выходящих дуг.Существуют некоторые базовые правила составления сетевого графика:

1. 
   каждая работа должна быть заключена между двумя событиями. В сети не может быть работ, имеющих одинаковые коды;
   

2. 
   в сети не должно быть событий, из которых не выходит ни одной работы, если только это событие не является для данного графика завершающим; соответственно, в сети не должно быть события, в которое не входит ни одной работы, если только это событие не является исходным;
   

3. 
   в сетевом графике не должно быть замкнутых контуров.
   

4. 
   Построить сетевой график работы по данным, приведенным на рис.31.
   

Решение. Заполняем сначала левые сектора. Результат приведен на рис.32.Затем заполняем правые сектора. Определяем цепь, задающую жесткий график работ. Окончательный результат приведен на рис.33.

17. Двудольные графы. Теорема Кенига.

Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.Двудо́льный граф или бигра́ф -  это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет вершину из одной части с какой-то вершиной другой части, то есть не существует рёбер между вершинами одной и той же части графа.

---