Reja: Algoritm tushunchasi

Форда-Фалкерсон Методi

• 
  qoldiq tarmoq tushunchasi
  
• 
  kattalashtirish zanjiri haqida tushuncha
  
• 
  kesilgan tushuncha
  

Usul iterativdir

Ford_Fulkerson_Method (G, s, t)

Oqimning boshlang'ich qiymatini 0 ga o'rnating

while kattalashtirish zanjiri p mavjud

do f zanjiri bo'ylab f oqimini oshiring

return f

• 
  Qoldiq tarmoqlar
  
• 
  Some Agar biron bir tarmoq va oqim ko'rsatilgan bo'lsa, unda qoldiq tarmoq bu oqimning ko'payishiga imkon beradigan qirralardan tashkil topgan tarmoqdir.
  
• 
  Source G = V, E manbalari s va cho'kmasi t bo'lgan tarmoq bo'lsin. O'tkazgichni c (u, v) dan oshmasdan biz u dan vgacha yuboradigan qo'shimcha oqimning qiymati qoldiq o'tkazuvchanlikdir:
  
• 
  cf (u, v) = c (u, v) - f (u, v)
  

A Berilgan tarmoq uchun G = V, E va oqim f, f oqim tomonidan hosil bo'lgan qoldiq tarmoq Gf = V, Ef  tarmoq bo'lib, bu erda

Ef = {(u, v)  V V: cf (u, v)> 0}.

F Ef qirralari yoki E ning chekkalari, yoki ularning teskari tomonlari. Agar f (u, v) 0 va (u, v)  Ef. Agar f (u, v)> 0 ba'zi qirralar uchun bo'lsa (u, v)  E, u holda f (v, u) <0. Bunday holda cf (v, u) = c (v, u) - f (v) , u)> 0 va shuning uchun (v, u)  Ef.