Алгоритм. Случае, изменяем поток f’ij = fij + δ, а во втором случае (здесь дуга идет из j в i) полагаем поток равным f’ji = fji − δ (необходимо обратить

Пусть к этому шагу в транспортной сети G, c построен поток f и сток получил пометку (m+, δ). Тогда увеличиваем поток fms через дугу (m, s) и полагаем его равным f’ms = fms +δ. Переходим к рассмотрению вершины m. Общий шаг: пусть находимся в вершине j. Возможны две ситуации: вершина имеет метку вида (i+, γ), либо вершина имеет метку вида (i−, γ). Тогда в первом

случае, изменяем поток f’ij = fij + δ, а во втором случае (здесь дуга идет из j в i) полагаем поток равным f’ji = fji − δ (необходимо обратить внимание на то, что поток через дугу на каждом шаге изменяется на одну и ту же величину δ). В обоих случаях переходим к вершине i. Продолжаем изменение потока, пока не достигнем источника. Как только источник достигнут, переходим к этапу расставления пометок.

20. Разрезы в сетях. Величина потока не превосходит величины разреза. Величина разреза.

Определение. Разрезом в сети G = (E, V, q, A, B) называется произвольное подмножество U ⊆ V такое, что A ∈ U и B ∈/ U.

Определение. Величина потока через разрез:

V(p, U) = V+(p, U) − V−(p, U),

где V+(p, U) = p(Y, X),

V−(p, U) = p(X, Y).

Теорема. Для потока p: E → R+ ∪ {0} в сетиG = (E, V, q, A, B) и произвольного разреза U ⊆ V имеет

место V(p, U) = V(p).

Доказательство. Индукция по |U|. Если |U| = 1, то U = {A}, V−(U, p) = 0и V+(U, p) = V(p).

Предположим, что теорема верна при |U| = n. Докажем теорему при |U| = n + 1. Пусть U = W ∪ C},

C!= A, B и |W| = n. По предположению V(W, p) = V(p).

Тогда V(U, p) − V(W, p) =(V+(U, p) − V+(W, p)) − (V−(U, p) − V−(W, p)) =

( p(C, X) − p(Y, C))−( p(Y, C) − p(C, X))= p(C, X) − p(Y, C) = 0.

Значит, V(U, p) = V(W, p) = V(p).

21. Алгоритм Форда-Фолкерсона.

Пусть дана транспортная сеть (G, c). Работа алгоритма состоит из трех этапов.

1. Выбор исходного потока. Строим произвольный поток f в сети (G, c),

например, нулевой.

2. Расставление пометок. Вершинам будут приписываться метки состоящие

из двух элементов. На первом шаге, помечаем источник меткой (−, ∞). Очеред-

ной шаг: выбираем одну из уже помеченных, но еще не обработанных вершин (на-

пример, с наименьшим номером) и обрабатываем ее. Пусть требуется обработать

вершину i с пометкой (x, q), тогда действуем по следующим правилам:

- если из вершины i в не помеченную вершину j идет такая дуга, что fij < cij,

то помечаем вершину j парой (i+, min(q, cij − fij));

- если в вершину i из не помеченной вершины j идет такая дуга, что fji > 0,

то помечаем вершину j парой (i−, min(q, fji)).

После того как помечены все возможные на данном шаге вершины, переходим

к следующему шагу.

Этап завершается в двух случаях:

- если помечен сток — в этом случае алгоритм переходит к этапу изменения потока;

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

3. Изменение потока. Пусть к этому шагу в транспортной сети G, c построен

поток f и сток получил пометку (m+, δ). Тогда увеличиваем поток fms через дугу

(m, s) и полагаем его равным f0ms = fms +δ. Переходим к рассмотрению вершины

m. Общий шаг: пусть находимся в вершине j. Возможны две ситуации: вершина

имеет метку вида (i+, γ), либо вершина имеет метку вида (i−, γ). Тогда в первом

случае, изменяем поток f0ij = fij + δ, а во втором случае (здесь дуга идет из j в i) полагаем поток равным f0ji = fji − δ (необходимо обратить внимание на то, что поток через дугу на каждом шаге изменяется на одну и ту же величину δ). В обоих случаях переходим к вершине i. Продолжаем изменение потока, пока не достигнем источника. Как только источник достигнут, переходим к этапу расставления пометок.

22. Конечные автоматы и регулярные языки. Примеры регулярных и нерегулярных языков.

1. Алфавитом X называется произвольный набор символов.

2. Словом над X называется произвольный набор символов α = x1x2... xl, где xi ∈ X. Число l называется длиной слова α. Пустое слово λ — слово длины 0.

3. Через X∗ обозначается множество всех слов над алфавитом X. Если α, β ∈ X∗, то через αβ ∈ X∗

обозначается конкатенация слов α и β.

α^n — конкатенация α с собой n раз.

4. Языком L над X называется любое подмножество X∗, то есть L ⊆ X∗.

Примеры языков.

1. X = {а, б, в,..., я};

L = {α ∈ X∗| α — слово русского языка}; мама, папа ∈ L; ммпа, аько ∈/ L.

2. X = {а,..., я} ∪ {,.!?;:-“”} ∪ {А,..., Я}; L = {α ∈ X∗| α — предложение русского языка};

Мама мыла раму. ∈ L; Мама мыло раме. ∈/ L.

Определение. Конечный автомат над — ориентированный граф A = (Q, E), ребра которого помечены функцией f: E → X таким образом, что для любого символа x ∈ X и любой вершины q ∈ Q существует и единственно ребро e ∈ E c началом q и меткой f(e) = x. Вершины конечного автомата называются состояниями. Тогда каждому состоянию q ∈ Q и символу x ∈ X однозначно сопоставлено состояние q 0 = δ(q, x), являющееся концом ребра с началом q и меткой x. Функция

δ: Q × X → Q называется функцией перехода.

Определение. Конечный автомат называется настроенным, если в нем выделено начальное состояние q0 ∈ Q и множество F ⊆ Q допускающих состояний.

Определение. Настроенный автомат A = (Q, X, δ, q0, F) распознает язык L ⊆ X∗,

если для любого α ∈ X∗ имеет место α ∈ L ⇐⇒ q0δ(α) ∈ F.

Определение. Язык L ⊆ X∗ называется регулярным, если он распознается некоторым (настроенным) конечным автоматом.

Примеры.

1.

2.

3.

23. Отношение различимости слов заданным языком. Ранг языка. Теорема Майхилла-Нероуда.

Бинарное отношение ∼ на множестве M называется отношением эквивалентности

если для всех x, y, z ∈ M выполнены следующие условия:

1. X ∼ x (рефлексивность);

2. x ∼ y и y ∼ z =⇒ x ∼ z (транзитивность);

3. x ∼ y =⇒ y ∼ x (симметричность).

Фактор-класс элемента x ∈ M: [x] = {z ∈ M | x ∼ z}. Тогда [x] = [y] ⇐⇒ [x] ∩ [y] 6= ∅ ⇐⇒ x ∼ y. Множество M разбито на непересекающиеся фактор-классы.

Множество всех фактор-классов M/ ∼= {[x] | x ∈ M} называется фактор-множеством

Пусть задан язык L ⊆ X∗. Говорим, что слова α, β ∈ X∗ неразличимы относительно L(α ∼L β), если

αε ∈ L ⇐⇒ βε ∈ L для любого ε ∈ X∗.

Примеры. Для языка L = {a, aab, aba, bb} имеем

1. a 6∼L b, так как a ∈ L и b ∈/ L;

2. a 6∼L aba, так как a ba ∈ L и aba ba ∈/ L;

3. aa 6∼L bb, так как aa b ∈ L и bb b ∈/ L;

4. aba ∼L bb, так как aba ∈ L, bb ∈ L, abaε /∈ L, bbε /∈ L при ε!= λ;

5. aa ∼L b, так как aa ∈/ L, b ∈/ L,, aa b ∈ L, b b ∈ L, aaε /∈ L, bbε /∈ L при ε 6= λ, b;

Бинарное отношение ∼L является отношением эквивалентности:

1. α ∼L α;

2. α ∼L β и β ∼L γ =⇒ α ∼L γ;

3. α ∼L β =⇒ β ∼L α.

Кроме того выполнено условие конгруэнтности:

4. α ∼L β =⇒ αγ ∼L βγ.

Фактор-класс строки α ∈ X∗ обозначается через [α]L = {β ∈ X∗| x ∼ z}.

Количество элементов в фактор множестве X∗/ ∼L= {[α]L | α ∈ X∗}

называется рангом языка L, обозначаемого через rk L