|
Лекция
13
Ориентированный граф и его
графическая интерпретация.Локальные степени. Матрица смежностей.
Ориентированные пути и связность в ориентированном графе.
Ориентированный
граф (или сокращенно орграф) -
это пара множеств  , где  - любое непустое
конечное множество, а  - подмножество в  (здесь  - прямое произведение
множества на себя, т.е.
множество всех упорядоченных пар элементов из , и  - диагональ множества ). Элементы из называются вершинами орграфа, а элементы из - его ребрами.
Если  и  , то  называется началом, а  называется концом ребра  ; как и в «неориентированном случае», вершины , называются инцидентными ребру , а ребро называется инцидентным вершинам , .
Орграф имеет естественную
геометрическую интерпретацию: его вершины изображаются в виде точек на
плоскости, а ребра – в виде стрелок, идущих из начала в конец ребра. Например,
если орграф имеет в качестве
множества вершин   и в качестве множества
ребер   то геометрически он выглядит так:
Если два орграфа
 таковы, что
одновременно выполняются два условия -  и  , - то говорят, что  - подграф орграфа  При этом пишут:  . Если одновременно и  , то орграфы называются равными и пишут  .
Два орграфа -  - называются изоморфными, если существует отображение
 такое, что выполнены
следующие четыре условия:
1) если  и  , то  ;
2) для всякого  существует такой  , что  ;
3) если  , то  ;
4) если  и  , то .
Если  - орграф и  , то следующие три числа имеют специальные названия: число  (количество ребер,
исходящих из вершины ) называется исходящей
степенью вершины ; число  (количество ребер,
входящих в вершину ) называется входящей
степенью вершины ; число  называется степенью вершины .
Каждый орграф можно описать матрицей смежностей по следующей схеме:
если  , то построим матрицу   положив
С каждым орграфом однозначно связывается
обычный граф  , в котором множество вершин - то же самое (т.е. множество ), а множество ребер  получается «стиранием
стрелок» у ребер из множества (т.е. если  , то  тогда и только
тогда, когда
либо  , либо  ). Граф называется ассоциированным с орграфом .
В каждом орграфе выделяется основной
объект – ориентированный путь (или
кратко - орпуть) орпуть - это символ
 ,
в котором  (причем, в списке  могут быть
повторяющиеся вершины) и в котором  . Ясно, что при переходе от ориентированного графа к
ассоциированному с ним графу орпуть создает конкретный обычный путь. В
приведенных только что обозначениях вершина  называется началом орпути, а вершина  называется концом орпути. При этом о самом орпути
говорят, что он является орпутем из в .
Две вершины  орграфа называются связанными, если имеется орпуть из  в  и одновременно имеется
орпуть из в . Орграф называется связным,
если в нем любые две вершины связанны. Так же, как в неориентированном случае,
понятие связности приводит к понятию
связной компоненты: подграф  орграфа  называется связной компонентой орграфа , если: 1) является связным
орграфом; 2) не существует связного орграфа  такого, что  и  .
Подобно тому, как это делалось в
случае обычных графов, для ориентированных графов вводятся понятия цепи,
простой цепи, цикла и простого цикла. Эти объекты можно исследовать по тому же
плану, что и в неориентированном случае.
Лекция 14
Сети
и потоки в сетях. Стационарные потоки. Алгоритм Форда-Фалкерсона поиска
максимального стационарного потока. (Данный вопрос лучше смотреть в сетевых
моделях исследования операций).
Пусть
- некоторый орграф и  вещественно-значная
функция на множестве ребер; тогда пара  называется сетью, а функция  в контексте сети
называется функцией пропускной
способности или пропускной способностью сети.
Всякая функция  , удовлетворяющая неравенству  , называется потоком в
сети. В обсуждении свойств потоков в сети традиционно используется
следующее обозначение:
пусть
 - любая функция и  - два любых
подмножества вершин; символ  будет обозначать сумму
значений функции  на ребрах таких, что  и  ; если
 состоит из
единственной вершины  , то символ  обозначает сумму весов
ребер, начинающихся в и заканчивающихся в
вершинах из  ; аналогичный смысл
имеет символ  - сумма значений
функции на ребрах, начинающихся
в и заканчивающихся в
вершине .
Поток в сети называется стационарным, если существуют две
вершины  и число  такие, что выполнены
следующие условия:
В этой ситуации
число  называется величиной
потока  , вершина называется источником, а вершина - стоком потока .
Известна следующая классическая задача о максимальном потоке: в данной
сети для данного источника и для данного стока найти стационарный поток
максимально возможной величины. Можно доказать, что такая задача всегда имеет
решение. Один из способов ее ре- шения называется алгоритмом Форда-Фалкерсона. Сформулируем этот алгоритм по шагам.
Шаг 0. Фиксируем на данной
сети с источником и стоком произвольный
стационарный поток , например - поток, тождественно равный нулю (т.е. равный
нулю на каждом ребре данного орграфа  ). Нетрудно проверить, что такой поток действительно
стационарный и имеет величину 0.
Шаг 1. Около вершины поставим пометку
следующего вида:
 .
Здесь символ  обозначает число,
заведомо превосходящее все числа, которые будут участвовать в дальнейших рассмотрениях
(в случае программирования это - компьютерная бесконечность, т.е. самое большое
число, допускаемое данным программным средством).
Замечание.
Почти все дальнейшие действия по алгоритму представляют собой расстановку
пометок около некоторых вершин. Цель этой расстановки в том, чтобы в конце
концов поставить пометку у стока или установить, что
сток пометить невозможно. В
первом
случае окажется
возможным заменить имеющийся стационарный поток
на другой стационарный
поток, имеющий величину, большую, чем величина потока . После этого надо будет запустить все сначала. Во втором
случае окажется, что имеющийся поток оптимален, т.е. его
величина имеет максимальное возможное значение. Каждая пометка, кроме уже
проставленной около источника , будет иметь вид  , где  - некоторое число, а - имя одной из вер-шин
орграфа , причем реально в пометке это имя будет либо в виде  , либо в виде  .
Шаг 2. Пусть - некоторое ребро,
начало которого, т.е. вершина , уже имеет некоторую пометку  (или, если - это источник , то пометку  , где  ). Ес-ли  , т.е. поток равен на ребре пропускной способности
, то пометка у вершины не проставляется. Если же
 , то пометка у вершины выставляется следующим
образом.
На
первом месте в пометке будет стоять символ , т.е. пометка будет такой:  , где число  еще нужно найти. Положим
 .
Пусть теперь такое ребро, у
которого пометку имеет конец, т.е. вершина имеет пометку . Если  , то пометку у вершины не выставляют; если же
 , то вершина получает пометку  , где
 .
Процедура расстановки пометок в
соответствии с Шагом 2 проводится до тех пор, пока не окажется
помеченной вершина  , или до тех пор, пока не выяснится, что вершину пометить невозможно.
Можно доказать, что в последнем случае поток , с помощью которого проводился весь Шаг 2, имеет максимальную возможную величину, и
задача решена.
Если же вершина оказалась помеченной,
то переходим к следующему шагу. Отметим принципиальную подробность: если
вершина оказалась помеченной,
то число, фигурирующее в пометке,
обязательно положительно.
Шаг 3. Пусть вершина имеет пометку  . Мы изменим сейчас поток
на не-скольких ребрах
данного графа, в результате чего получится новый стационарный поток из
источника в сток , величина которого будет на  (это число указано в
пометке стока ) больше величины потока .
Если вершина имеет пометку  , то на ребре  изменим поток , прибавив к его значению на этом ребре число . Если вершина имеет пометку  , то на ребре  изменим поток , вычитая из его значения на этом ребре число .
Затем перейдем к вершине и проделаем то же, что
только что делалось относительно вершины ; при этом прибавлять или вычитать будем прежнее число . Продолжая так, в соответствии с пометками, отбирать ребра
графа и менять на них значение потока (на каждом отбираемом ребре - на одно и
то же число !), мы придем к источнику . Это будет означать завершение изменения потока. Можно
доказать, что полученный в результате
поток является стационарным и его величина на больше величины
исходного потока .
Затем нужно повторить все сначала с
уже новым базовым стационарным потоком.
Пример. Найти максимальный
стационарный поток из в в следующей сети
(числа у стрелок означают пропускную способность):
Считаем,
что исходный стационарный поток тождественно равен нулю. Проставляем пометку
около вершины : она такова - . Выбираем далее для пометки вершину ; соответствующая пометка:
 . Выбираем далее для пометки вершину  ; соответствующая пометка:  . Теперь появилась возможность пометить и вершину ; соответствующая пометка :  .
Возникла возможность поток увеличить
на 1. Для этого на ребре  положим его равным 1
(а не нулю, как это было для исходного
потока), также равным 1 новый поток будет и на ребрах  и  . На остальных ребрах поток остается равным нулю.
Новый поток имеет величину 1, он
стационарен с источником и стоком . Повторим теперь процедуру сначала, стремясь поставить
пометку к стоку .
Вершину пометим пометкой . Далее пометим вершину  ; соответствующая пометка:  . Далее пометим вершину  ; соответствующая пометка:  . Теперь пометим вершину ; соответствующая пометка:  . Теперь снова увеличим на 1 значения потока на ребрах  . Новый поток будет тоже стационарен, но уже величины 2.
Вновь поставим пометку у вершины и попытаемся увеличить
имеющийся стационарный поток величины 2.
Пометим вершину  ; соответствующая пометка:  . Далее пометим вершину ; соответствующая пометка:  . Далее пометим вершину ; соответствующая пометка: . Вновь изменим поток на 1: прибавим 1 к значениям прежнего
потока на ребрах  ,
 . Вновь полученный поток имеет величину 3.
Дальнейшие попытки достигнуть пометками
вершину не имеют успеха.
Следовательно, максимальный стационарный поток найден.
|
