Residual Graph — Joriy oqimga nisbatan qaysi yoylarda oqimni oshirish yoki oldingi qarorni qaytarish mumkinligini ko‘rsatuvchi yordamchi graf. Bu tushuncha algoritmlar va ma’lumotlar tuzilmalarida natijani aniq ifodalash, murakkablikni tahlil qilish hamda muqobil yechimlarni solishtirish uchun ishlatiladi.
Tuzilish mexanizmi
Asl (u,v) yoy uchun oldinga residual sig‘im c(u,v)−f(u,v), orqaga residual sig‘im esa f(u,v) bo‘ladi. Musbat residual sig‘imli yoylargina oshiruvchi yo‘lda qatnashadi.
Residual Graphni tushunishda uning matematik ta’rifi bilan dasturiy ko‘rinishini ajratish muhim. Matematik model qaysi obyektlar va munosabatlar ruxsat etilishini belgilaydi; implementatsiya esa ularni massiv, ro‘yxat, xarita yoki boshqa tuzilma orqali saqlaydi. Bir xil model turli xotira va vaqt xususiyatlariga ega ko‘rinishlarda amalga oshirilishi mumkin. Shuning uchun “to‘g‘ri” tanlov faqat ta’rifga emas, bajariladigan so‘rovlar, kirish hajmi va yangilanish chastotasiga ham bog‘liq.
Algoritmdagi roli
Orqaga yoy algoritmga avval yuborilgan oqimni kamaytirib, uni boshqa yo‘lga qayta taqsimlash imkonini beradi. Shu xususiyat greedy tanlovda qilingan mahalliy qarorni tuzatadi va Ford–Fulkerson oilasining to‘g‘riligida markaziy o‘rin tutadi.
Residual Graphning foydasi faqat yakuniy javob bilan o‘lchanmaydi. U masalani qaysi qismlarga ajratish, qaysi invariantni saqlash va natijani qanday tekshirish mumkinligini ham ko‘rsatadi. Algoritm tanlanganda preprocessing, asosiy so‘rov, yangilash va natijani tiklash xarajatlari alohida baholanadi. Bir martalik hisoblash uchun ma’qul usul doimiy yangilanadigan xizmat uchun qimmat bo‘lishi mumkin.
Implementatsiya talablari
Residual Graph asl tarmoqning alohida nusxasi bo‘lishi shart emas; ko‘pincha har qirra qarama-qarshi indeksli juft obyekt bilan saqlanadi. Yangilashda oldinga sig‘im kamayib, orqaga sig‘im ayni miqdorga ortishi invariant sifatida saqlanadi.
Residual Graph bilan ishlovchi dastur kirish shartlarini aniq tekshirishi kerak. Tugun yoki element identifikatorlari, yo‘nalish, vazn, tenglik va dublikat qoidalari oldindan kelishilmasa, nazariy jihatdan to‘g‘ri algoritm noto‘g‘ri model ustida ishlashi mumkin. Testlar minimal holat, bo‘sh kirish, uzilgan yoki takroriy ma’lumot, teng qiymatlar va eng yomon tartibni qamrab oladi. Katta kirishda natijaning o‘zi bilan birga xotira sarfi, bajarilish vaqti va I/O hajmi ham o‘lchanadi.
Sodda holat
Agar sig‘imi 10 bo‘lgan u→v yoyda 6 birlik oqim bo‘lsa, residual grafda u→v uchun 4, v→u uchun 6 birlik imkoniyat mavjud. Keyingi yo‘l v→u dan 2 birlik foydalansa, asl oqim 4 ga kamayadi.
Amaliy hujjatda Residual Graph uchun kuzatiladigan kafolatlar alohida yoziladi: natijaning aniqligi, deterministikligi, murakkablik chegarasi va xato holatidagi xatti-harakat. Nazariy Big O bahosi kirish o‘sgandagi tendensiyani beradi, lekin kesh lokaliteti, disk murojaati va ma’lumot taqsimoti real tezlikka ta’sir qiladi. Shu bois kichik etalon implementatsiya bilan natijani solishtirish, so‘ng real ish yukida profil olish ishonchli tekshiruv usulidir.
+## Verifikatsiya
Har residual qirra uchun qarama-qarshi qirra indeksi o‘zaro mos bo‘lishi tekshiriladi. Oqim oshirilganda juft residual sig‘imlar yig‘indisi o‘zgarmas qoladi; manfiy residual sig‘im paydo bo‘lishi implementatsiya xatosini bildiradi. Residual Graph implementatsiyasi uchun bu tekshiruvlar oddiy unit testdan kengroq bo‘lib, modelning asosiy matematik shartlarini nazorat qiladi. Etalon bilan farq topilsa, tasodifiy kirish minimal qarshi misolgacha kichraytiriladi; shu misol regressiya testiga qo‘shiladi.
Bog‘liq tushunchalar
residual graph, augmenting path, maximum flow, residual capacity, reverse edge, network