Reja: Algoritm tushunchasi

Kattalashtirish zanjiri usuli

 deymizki, S tarmog'ining yoyi, oqim oqishiga nisbatan qabul qilinadi va v da,

e = va f (e)

 yoki

e = va f (e)> 0.

The Yuqoridagi shartlarning qaysi biriga, birinchi yoki ikkinchisiga bog'liq holda, biz mos ravishda va v dan mos keladigan qabul qilinishi mumkin bo'lgan yoy haqida gaplashamiz.

F Berilgan oqim uchun s dan t gacha bo'lgan kuchlanish zanjiri (l uzunligi) o'zboshimchalik bilan ketma-ketlikdir

v0, e1, v1, e2, v2, ..., vl - 1, el, vl,

    v0 = s, vl = t va har bir i uchun l arc ei vi - 1 dan vi oqim uchun f ga nisbatan qabul qilinadi.

The Kattalashtiruvchi zanjirni bilish f oqimini f = min {delta (ei) ga ko'paytirishni osonlashtiradi: 1 < i< l}, bu erda

Buning uchun har bir topilgan yoy ei bo'ylab oqimni ko'paytirish kifoya qiladi:

va har bir mos kelmagan boshq ei uchun oqimni b ga kamaytiring:

Zanjirga tegishli bo'lmagan yoylar uchun f '(e) = f (e) ni o'rnatamiz. Oqim kattaligi deltab ga oshadi:

W (f ') = Divf' (lar) = Divf (lar) +delta = W (f ') +delta.

• 
  Kattalashtirish zanjiri shaklga ega
  
• 
  v₁, v₁, v₃, v₃, v₂, v₃, v₂, v₅, v₂, v₅, v₅, v₆, v₆, v₇, v₆, v₇, v₇, v₈, v₈,
  
• 
       bu oqimning v = 1 ga 10 dan 11 gacha ko'payishini ta'minlaydi.
  
• 
   3-teorema. Quyidagi uchta shart tengdir:
  
• 
  A (a) s dan t gacha bo'lgan oqim maksimaldir.
  
• 
  B) f uchun kattalashtirish zanjiri yo'q.
  
• 
  A (c) W (f) = c (A, V \ A), s  A, t  A bo'lgan ba'zi A  V uchun.
  
• 
  
  

Isbot

(a) (b). Agar oqim maksimal bo'lsa, uning uchun zanjir oshmasligi aniq, chunki bunday zanjirning mavjudligi oqimni ko'paytirishga imkon beradi.

(b) (c). Faraz qilaylik, qandaydir f uchun kattalashtirish zanjiri yo'q. Biz A  V to'plamni v zanjiri mavjud bo'lgan vertikallarning to'plami sifatida aniqlaymizv₀, e₁, v₁, e₂,v₂, …, v_k–1, e_k, v_k

Masalan, k  0, v0 = s, vk = v, va ei vi-1 dan vi, 1 i  k ga to'g'ri keladigan yoydir. Shubhasiz, s  A va t  A, chunki bu f uchun ortib boruvchi zanjirning mavjudligini anglatadi. P (A) qismini ko'rib chiqing. E  P (A) har bir yoy uchun f (e) = c (e) tenglik A to'plamning ta'rifiga muvofiq bajarilishi kerak, shu bilan f (A, V \ A) = c (A, V \ A). A ning ta'rifidan foydalanib, biz f (V \ A, A) = 0 ni olamiz. Lemma 1 ga binoan, bu

W(f) = f(A, V \A) – f(V \A, A) = c(A, V\A).

• 
  (в)  (а) allaqachon tasdiqlangan haqiqatdan kelib chiqib, o'zboshimchalik bilan oqimning qiymati oshmasligi kerak (A, V\A)
  

Maksimal oqim algoritmi

Usul g'oyasi: o'zboshimchalik oqimidan boshlab (masalan, f (e) = 0 har bir yoy uchun e e E), biz zanjirlarning ko'payishini va ular bo'ylab haqiqiy oqimni ko'paytirishni qidiramiz.

 1) Bunday algoritm cheklangan sonlar bilan tugaydimi?

2) Olingan oqim maksimal bo'ladimi?

The Ikkinchi savolga javob 3-teoremadan to'g'ridan-to'g'ri kelib chiqadigan tasdiqlovchida bo'ladi.

 Ford va Fulkerson birinchi savolga ma'lum ma'noda salbiy javob berishdi. Xususan, ular jarayonni hech qachon tugamasligini hisobga olib, keyingi kattalashtirish zanjirlarini "shu qadar zararli" tarzda tanlash mumkin bo'lgan tarmoqning misolini keltirdilar; bundan tashqari, butun vaqt davomida oqim kattaligi maksimal oqimning to'rtdan biridan kam bo'ladi.

Edmonds va Karp algoritmi

 Edmonds va Karp agar biz haqiqiy oqimni har doim eng qisqa o'sadigan zanjir bo'ylab oshirsak, u holda maksimal oqim mn / 2 zanjirdan foydalanib qurilganligini ko'rsatdi.

 Eng qisqa qidiruvga o'xshash algoritm yordamida eng qisqa zanjirni topish oson. Aniqroq, manbadan boshlab, Gf grafikasida yoylar, v of dan iborat keng ko'lamli qidiruvni amalga oshiramiz, shunday qilib bizning tarmog'imizda nisbiy haqiqiy oqimdan f ga va v ga to'g'ri keladigan yoy mavjud, to cho'kish nuqtasiga qadar. . Shubhasiz, ushbu jarayon natijasida s-dan t-gacha bo'lgan eng qisqa yo'l asl tarmoqdagi s-dan t-gacha bo'lgan eng qisqa zanjirga to'g'ri keladi. O kengligi bo'yicha birinchi qidirish jarayonini O (m + n) vaqtida bajarishimiz mumkinligini hisobga olsak, O (tn (m + n)) kabi maksimal oqimni qurish uchun barcha algoritmning murakkabligini taxmin qilishimiz mumkin.

• 
  Maksimal oqimni qurish algoritmi
  
• 
   Ushbu usul ba'zi bir yordamchi kontursiz tarmoqni qurishga asoslangan bo'lib, uning tuzilishi f ga nisbatan oqimga nisbatan s dan t gacha bo'lgan barcha eng qisqa kuchayib boruvchi zanjirlarni aniq ko'rsatib beradi. Bunday tarmoqni Sf tomonidan belgilang. Biz uni Gf grafikasida keng tarmoqli qidiruvdan foydalanib quramiz, yoy bilan aniqlangan, asl tarmoqdagi haqiqiy oqim f ga qarab. Sf tarmog'ida s, 0, d  l dan d + 1 masofada, 0  d  l masofada joylashgan shaklidagi Gf grafikasining manbai s, cho'kish t va yoylari mavjud, bu erda l - Sf uzunligi, t. e Gf grafigidagi s dan t gacha bo'lgan masofa. O'tkazgichning kengligi c (u, v) yoy yoyi bir-biriga mos keladigan yoyni anglatadimi yoki yo'qmi (c, u, v) - f (u, v) yoki f (v, u) sifatida aniqlanadi. yoki bu qiymatlarning yig'indisi), agar bir vaqtning o'zida va v dan qabul qilinadigan izchil va nomuvofiq boshq bo'lsa.
  
• 
  Yordamchi kontur tarmog'ida soxta maksimal oqimni qurish uchun samarali algoritm (Malxotri, Kumar va Maeshvari)
  
• 
   Ma'lumot: Voqealar ro'yxati
  
• 
  ПРЕДШ [v], ЗАПИСЬ[v], v  V, пропускные способности c[u, v], и, v  V, источник s  V и сток t  V. Natijalar: Maksimal oqim F[u, v], и, v  V.
  
•