c(U,V) – пропускна здатність ребра;

f(U,V) – потік по даному ребру;

div(U,f) – різниця сум всіх потоків, які витікають з U і втікають в U. div(U,f)=;

Р – розріз.

Даний алгоритм випливає із теореми Форда-Фалкерсона:

Max w(f)=min c(f): максимум із пропускних здатностей розрізів між s і t.

Для довільної множини можна побудувати максимальний потік між s і t за допомогою рекурентного алгоритму.

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

Починаємо з нульового потоку і намагаємося його збільшити. Нехай вже маємо деякий потік f між s і t. В кожній вершині ставимо мітку вигдяду , де величина, на яку можна збільшити потік з s в цю вершину, n –попередня вершина, через яку можна збільшити потік в дану вершину. Становимо “+”,якщо ребро іде від попередньої вершини до даної. Потік по ребру можна збільшити, та “-”, якщо від даної і попередньої вершини потік можна зменшити.

Позначки є 2-ох типів: тимчасові і постійні. На початку ставимо тимчасову позначку вигляду у вершині s. Вона означає. Що потік з s в s можна збільшувати необмежено і при цьому не потрібно проходити через жодну іншу вершину.

На кожному кроці обираємо одну з вершин з тимчасовою позначкою , яку робимо постійною.

Навколо цієї вершини V, в якій немає позначки або вона є тимчасовою. Якщо у V немає позначки й існує ребро (U,V), потік по якому немає макс. пропускної здатності, тобто <c(U,V), то у вершині V ставимо позначку , яка означає, що можна збільшити потік від s до V через вершину U. Якщо ж існує ребро (U,V) потік по якому не нульовий: , яка означає, що можна збільшити потік від s до U і одночасно зменшити зворотній потік від V до U, за рахунок чого зросте потік від s до V.

Якщо у вершині V вже є тимчасова позначка , то замінюємо її на нову тільки в тому випадку, коли нова величина або більше від попередньої .

Коли у вершину t ставимо постійну позначку, то відповідно до позначок збільшується потік від s до t, стираємо всі позначки і починаємо процес знову.

Якщо більше не можливо перетворити тимчасову позначку на постійну, то побудований потік вже є максимальний.

П-ад: - кольором виділено постійні позначки.

s | a | b | t

(1,s,+) | (2,s,+)

(1,s,+) | (2,s,+) | (1,a,+)

(1,s,+) | (2,s,+) | (1,a,+)

(2,s,+)

(2,b,+) | (2,s,+) | (1,b,+)

(2,b,+) | (2,s,+) | (2,a,+)

1)

(1,s,+) (2,s,+)

2) (2,b,+) (2,a,+)

(2,s,+)

3)

Отримали максимальний потік: w(f)=3.

7. Скінченні автомати.

Автоматом Мілі називають п’ятірку А, X, Y, f, g, яка складається з з

множини А станів автомата

вхідного алфавіту х і вихідного алфавіту у.

Функції переходів f: (A x x)>X і функції переходів (A x x)>У

Вважаємо, що автомат може перебувати в довільному з станів і під впливом вхідного сигналу х э X переходити в новий стан, який залежить від теперішнього стану А, і символу х, і позначається f(a, x). При цьому на вихід автомата подається вихідний символ h(0, x) є Y. А – можна визначати таблицями переходів і виходів.

Стани | F | G

1 | 2 | 3 | 1 | 2 | 3

X | y | x | x | a | b | c

Y | x | y | x | b | c | a

Ці таблиці можна звести в одну:

А\Ч | 1 | 2 | 3

Х | (y,a) | (x,b) | (x,c)

Y | (x,b) | (y,c) | (x,a)

Якщо автомат має скінченні множини станів вхідних і вихідних символів, то його зручно зоображати графом, вершини якого – стани, а стрілки – переходи між ними.

Доводиться також вивчати автомати, в яких з того ж стану під дією того ж вхідного символа автомат може перейти в кілька можливих станів, або видати кілька різних вихідних символів, тобто його поведінка не визначена однозначно. Такий автомат називається не детермінованим.

Можливий також випадок коли для деякого стану і деякого символу взагалі не визначено відповідного переходу. В цьому випадку вважаємо що автомат припиняє роботу. Такий автомат називається не цілком визначеним.

Важливим є клас автоматів, для яких вихідний символ однозначно визначається тим станом а = f(a, x), куди переходить автомат. Якщо ця залежність визначається функцією y = h(a), то функція виходів рівна y(a, x) = h(f(a,x)). Функція h називається функцією позначок. Вважаємо що в кожній вершині а є позначка h(a’), яка подається на вихід, коли автомат переходить у стан а’. Такий автомат називається автоматом Мура.

Не кожен автомат Мілі є автоматом Мура.

Цей автомат не є автоматом Мура, оскільки повинен однозначно визначатись вихід залежно від х чи y. Переходячи в стан х можна отримати на виході і a i b.

Нехай автомат Мілі перебуває в стані а є A, і на його вхід надходить рядок символів х1, х2, х3….хn є X*. Під дією х1 автомат перейде в стан а1 = f(a, x1), і видасть символ y1 = g(a, x1). Під дією х2 перейде в стан а2 = f(a, x2), і видасть символ y2 = g(a,