Головна

алгоритм

Нехай до цього кроку в транспортній мережі 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

то помічаємо вершину 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



 доведення коректності |  Операції об'єднання і перетину регулярних мов

 штрих Шеффера |  Знаходження мінімальної ДНФ. |  приклади |  Лемма про несамодвойственной функції. Лемма про немонотонної функції. |  Лемма про функції, які не зберігають T_0 і T_1. Теорема Поста про повноту (доказ теореми справа наліво). |  Неорієнтовані графи. Ступені вершин. Сума ступенів вершин графа. Ізоморфізм графів. Приклад неізоморфних графів з однаковими ступенями. |  Вершин, ребер і компонент зв'язності. |  Ейлерови і Гамільтона шляху. Критерій існування ейлерового шляху. |  Теорема Келі про кількість дерев на n вершинах. Коди Прюфера. |  Доведення формули Ейлера для плоских зв'язкових графів |

© um.co.ua - учбові матеріали та реферати