Ֆորդ-ֆալկերսոնի ալգորիթմ

**Ֆորդ–Ֆալկերսոնի** ալգորիթմը որոշում է տրանսպորտային ցանցերում առավելագույն հոսքերի հայտնաբերման խնդիրը։

Ալգորիթմի գաղափարը հետևյալում է. սկզբնապես հոսքի մեծությանը վերագրվում է 0։  f(u, v)=0 նշանակություն՝ բոլոր u, v \in V համար։ Ապա հոսքի մեծությունը ինտերատիվ մեծանում է՝ մեծացնող ուղու ընդլայնման հետևանքով ( *s* աղբյուրից *t* հոսանքին ուղին, որի երկայնքով կարելի է ավելի շատ հոսք ուղարկել)։ Գործընթացը շարունակվում է, քանի դեռ հնարավոր է գտնել մեծացնող ուղի։

## Ալգորիթմ
## Ոչ պաշտոնական բնութագրում
# Բոլոր հոսքերը զրոյացնում ենք։ Մնացորդային ցանցը սկզբնապես համընկնում է ելակետային ցանցի հետ։
# Մնացորդային ցանցում գտնում ենք աղբյուրից դեպի հոսանք ցանկացած ուղի։ Եթե այդպիսի ուղի չկա՝ կանգ ենք առնում։
# Գտնված ուղով բաց ենք թողնում (այն անվանվում է **մեծացնող ուղի** կամ **մեծացնող շղթա**) առավելագույն հնարավոր հոսքը։
## Մնացորդային ցանցում հայտնաբերված ուղու վրա փնտրում ենք նվազագույն բացթողնման հնարավորությամբ եզրը c_\min։
## Գտնված ուղու յուրաքանչյուր եզրի համար մեծացնում ենք հոսքը c_\min, իսկ դրա հակառակ ուղղությամբ՝ փոքրացնում c_\min։
## Մոդիֆիկացնում ենք մնացորդային ցանցը։ Բոլոր եզրերի համար գտնված ուղու, ինչպես նաև դրան հակառակ եզրի վրա, դուրս ենք բերում նոր բացթողման հնարավորությունը։ Եթե այն դառնում է ոչ զրոյական, ապա եզրն ավելացնում ենք մնացորդային ցանցին, իսկ եթե զրոյական է՝ ջնջում ենք։
# Վերադառնում ենք 2-րդ քայլին։

Կարևոր է, որ ալգորիթմը չի հստակեցնում, թե կոնկրետ որ ուղին ենք մենք փնտրում 2-րդ քայլում կամ, թե ինչպես ենք մենք դա անում։ Այդ իսկ պատճառով ալգորիթմը համապատասխանում է միայն ամբողջ բացթողնման հնարավորություններին, սակայն անգամ դրանց համար, բացթողնման հնարավորությունների մեծ նշանակությունների դեպքում, այն կարող է շատ երկար աշխատել։ Եթե բացթողնման հնարավորությունները նյութական են, ապա կարող է անվերջ երկար աշխատել՝ չհամընկնելով օպտիմալ որոշմանը։ (տես օրինակը ներքևում).

Եթե փնտրենք ոչ ցանկացած ուղի, այլ ամենակարճը, կստացվի Էմոնդս-Կարպի ալգորիթմը կամ Դինիցի ալգորիթմը.

## Պաշտոնական նկարագրություն
Տրված է G(V, E) գրաֆը c(u, v) բացթողնման հնարավորությունով և f(u, v)=0 հոսքով՝ *u*-ից *v* եզրերի համար։ Պետք է գտնել *s* աղբյուրից *t* հոսանքին առավելագույն հոսքը։ Ալգորիթմի յուրաքանչյուր քայլի համար գործում են բոլոր հոսքերի համար գործող պայմանները։

* \ f(u, v) \leqslant c(u, v). u-ից v հոսանքը չի գերազանցում բացթողնման հնարավորությունը։
* \ f(u, v) = - f(v, u).
* \ \sum_v f(u, v) = 0 \Longleftrightarrow f_{in}(u) = f_{out}(u) բոլոր կապերի համար u, բացի s և t։ Կապերի միջով անցնելիս հոսքը չի փոխվում։

**Մնացորդային ցանց** G_f(V, E_f) - բացթողման հնարավորությունով ցանց c_f(u, v) = c(u, v) - f(u, v) և առանց հոսքի։

**Մուտք** Գրաֆ \, G բացթողման հնարավորությունով \, c, աղբյուր \, s և հոսանք \, t
**Ելք** Առավելագույն հոսք \, f \, s-ից \, t
# f(u, v) \leftarrow 0 բոլոր եզրերի համար \, (u, v)
# Քանի դեռ ուղի կա \, p \, s-ից \, t \, G_f, այնպիսին, որ \, c_f(u, v) > 0բոլոր եզրերի համար (u, v) \in p։
## Գտնել \, c_f(p) = \min\{c_f(u, v) \;|\; (u, v) \in p\}
## Յուրաքանչյուր եզրի համար (u, v) \in p
### f(u, v) \leftarrow f(u, v) + c_f(p)
### f(v, u) \leftarrow f(v, u) - c_f(p)

Ուղին կարող է գտնվել.օրինակ, լայնությամբ փնտրման (Էմոնդս-Կարպի ալգորիթմ) կամ խորությամբ փնտրման G_f(V, E_f)։

## Բարդությունը
Արդեն գոյություն ունեցող հոսքերին հոսք ավելացնելով առավելագույն հոսքը կստացվի այն դեպքում, երբ հնարավոր չի լինի գտնել մեծացող հոսք։ Այդուհանդերձ, եթե բացթողնման հնարավորության մեծությունը իռացիոնալ թիվ է, ապա ալգորիթմը կարող է անվերջ աշխատել։ Ամբողջ թվերի դեպքում այդպիսի խնդիր չի առաջանում և աշխատանքի ժամանակը սահմանափակ է O(*E*f*), որտեղ *E* - գրաֆում եզրերի թիվն է, *f* - գրաֆում առավելագույն հոսքը, քանի որ ամեն մեծացող ուղի կարող է գտնվել O(''E'') համար և մեծացնում է հոսքը առնվազն 1-ով։

### Չհամընկնող ալգորիթմի օրինակ
աջից
Դիտարկենք հետևյալ ցանցի օրինակը \ s աղբյուրով, \ t հոսանքով, \ e_1 = \ 1, \ e_2 = r=(\sqrt{5}-1)/2, \ e_3 = \ 1 եզրերի բացթողնման հնարավորություններով և մնացած բոլոր եզրերի բացթողնման հնարավորություններով, որոնք հավասար են M \ge 2 ամբողջ թվին. \ r հաստատունը ընտրված է այնպես, որ \ r^2 = 1 - r. Օգտագործում ենք ուղիներ մնացորդային գծագրից, որոնք բերված են աղյուսակում, ընդ որում՝ \ p_1 = \{ s, v_4, v_3, v_2, v_1, t \}, \ p_2 = \{ s, v_2, v_3, v_4, t \} և \ p_3 = \{ s, v_1, v_2, v_3, t \}.

Նկատենք, որ 1 քայլից հետո, ինչպես և 5 քայլից հետո e_1, e_2 և e_3 եզրերի մնացորդային հնարավորությունները ունեն r^n, r^{n+1} և 0 ձևը, համապատասխանաբար, որևէ բնական n համար։ Դա նշանակում է, որ կարող ենք օգտագործել p_1, p_2, p_1 և p_3 մեծացող ուղիները անվերջ անգամներ և այդ եզրերի մնացորդային բացթողնման հնարավորությունները միշտ կլինեն նույն ձևով։ 5-րդ քայլից հետո ամբողջական հոսքը հավասար է 1 + 2(r^1 + r^2)։ Անվերջ ժամանակահատվածում ամբողջական հոսքը կհամընկնի \textstyle 1 + 2\sum_{i=1}^\infty r^i = 3 + 2r, այն դեպում, որ առավելագույն հոսքը հավասար է 2M + 1" Այսպիսով, ալգորիթմը ոչ միայն անվերջ երկար է աշխատում, այլ նաև լավագույն որոշմանը չի համընկնում։

## Օրինակ
Հետևյալ օրինակը ցույց է տալիս Ֆորդ-Ֆալկերսոնի ալգորիթմի առաջին քայլերը չորս կապերով տրանսպորտային ցանցում` *A* աղբյուրով և*D* հոսքով։ Այս օրինակը ցույց է տալիս ամենավատ դեպքը։ Լայնությամբ փնտրման դեպքում ալգորիթմին պետք կգա ընդամենը 2 քայլ.
 

## Ծանոթագրություններ

## Արտաքին հղումներ
* Визуализатор алгоритма 
* Реализация поиска максимального потока методом Форда-Фалкерсона на Java 

Կատեգորիա:Գրաֆների ալգորիթմներ