Алгоритм построения максимального потока в сети.

Шаг 1. Задать начальное значение потока, если оно не задано. Удобно задавать начальное значение потока равным нулю. Перейти на шаг 2.

Шаг 2. Построить увеличивающую цепь от истока к стоку сети. Если увеличивающей цепи не существует, то максимальный поток построен, его значение: (t)=div(f,s), в противном случае перейти на шаг 3.

Шаг 3. Вдоль построенной цепи увеличить значение потока на величину . Перейти на шаг 2.

На основании теоремы Форда-Фалкерсона доказательством того, что построенный поток максимальный, будет существование разреза, величина которого равна значению построенного потока.

При моделировании реальных задач могут использоваться сети с неориентированными ребрами. Использование при расчетах неориентированных сетей предоставляет дополнительные возможности при выборе оптимального решения.

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

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

Для полученной ориентированной сети максимальный поток определяется по алгоритму, указанному выше.

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

7. Конечные автоматы

7.1. Понятие конечного автомата Общие сведения о конечных автоматах

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

Они обладают следующими свойствами:

1. Любая ЦВМ состоит из конечного числа элементов, каждый из которых в любой момент времени может находиться лишь в одном из конечного числа устойчивых состояний. Поэтому вся машина в целом имеет конечное множество состояний.

2. Любая ЦВМ работает последовательно, то есть ее операции синхронизированы сигналами тщательно настроенных электронных часов. В связи с этим состояние машины меняется в четкой последовательности.

3. ЦВМ является детерминированным устройством. Это значит, что при наличии полной информации о внутренних состояниях всех элементов машины и всех ее входов следующее состояние машины определяется однозначно.

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

С функциональной точки зрения современные ЦВМ состоят из 5 типов устройств:

1) устройство ввода;

2) устройство памяти;

3) арифметико-логическое устройство;

4) устройство управления;

5) устройство вывода.

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

Таким образом, типичный сигнал в элементах ЦВМ имеет следующий вид

Рис. 38

При этом единицей кодируется сигнал более высокого уровня, а нулём – более низкого. Или более точно, устанавливается некоторое пороговое значение сигнала и далее сигналы выше порога кодируются 1, а ниже – 0. Таким образом, не вникая в дальнейшие особенности работы электронных схем, отметим, что сигналы в таких устройствах двузначны. Это значит, что переменные, используемые для их описания, принимают только два значения. Это же замечания относится и к материальным носителям информации и к преобразователям сигналов. В результате состояние любой ЦВМ, имеющей конечное число r двоичных элементов математически может быть описано следующим образом.

Нумеруются элементы ЭВМ, затем с каждым устойчивым состоянием связывается вектор

.

При этом координате приписывается значение 1, если -й элемент находится в единичном состоянии, и 0, если -й элемент находится в нулевом состоянии.