[Править]Формальное описание

Дан граф   с пропускной способностью   и потоком   для ребер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:

• . Поток из   в   не превосходит пропускной способности.

• .

•  для всех узлов  , кроме   и  . Поток не изменяется при прохождении через узел.

Остаточная сеть   — сеть с пропускной способностью   и без потока.

Вход Граф   с пропускной способностью  , источник   и сток  Выход Максимальный поток   из   в 

1.  для всех ребер 

2. Пока есть путь   из   в   в  , такой что   для всех ребер  :

   1. Найти 

   2. Для каждого ребра 

      1. 

      2. 

Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса — Карпа) или поиском в глубину в  .

-------27 Структура сети связи и основные определения

Основные определения

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

В настоящее время применяют следующие принципы построения (топологии) сетей:

• "каждый с каждым" (Рис. 4.1). Сеть надежна, отличается оперативностью и высоким качеством передачи сообщений. На практике применяется при небольшом числе абонентов;

Рис. 4.1. Топология сети "каждый с каждым"

• радиальный ("звезда") (Рис. 4.2). Используется при ограниченном числе абонентских пунктов, расположенных на небольшой территории;

Рис. 4.2. Топология сети "звезда"

• радиально-узловой (Рис. 4.3). Такую структуру имеют городские телефонные сети, если емкость сети не превышает 80...90 тысяч абонентов;

Рис. 4.3. Радиально-узловая топология сети

• радиально-узловой с узловыми районами (Рис. 4.4). Используется при построении телефонных сетей крупных городов.

Рис. 4.4. Топология радиально-узловой сети с узловыми районами

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

-------28 Основные структуры сети

ХЗ ХЗ ХЗ

------29 Задача минимизации сети состоит в нахождении ребер, соединяющих все узлы сети и имеющих минимальную суммарную длину (рис. 30.17).

На ребрах, соединяющих узлы 1, 2, 3, указаны длины. Узел 3 соединен с узлами 1 и 2 минимальной длиной 4 + 6 = 10. Если соединить узлы 1 и 2, то возникает цикл и получающаяся сеть не будет минимальной. Отсутствие циклов в минимальной сети дало ей название "минимальное дерево-остов".

Алгоритм решения

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

------31 Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

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

• Q — множество состояний автомата;

• q₀ — начальное (стартовое) состояние автомата ( );

• F — множество заключительных (или допускающих) состояний, таких что  ;

• Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

• δ — заданное отображение множества   во множество   подмножеств Q:

(иногда δ называют функцией переходов автомата).

Автомат начинает работу в состоянии q₀, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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