MAKSIMAL OQIM VA MINIMAL KESIM HAQIDAGI TEOREMA HAMDA UNI FORD-FULKERSON ALGORITMI YORDAMIDA YECHISH
Keywords:
Kalit so'zlar: oqim tarmog'i, maksimal oqim, minimal kesim, Ford-Fulkerson teoremasi, kengaytiruvchi yo'l, qoldiq graf, sig'im funksiyasi, algoritm, optimal boshqaruv, graf nazariyasi.Abstract
Annotatsiya. Ushbu maqolada jarayonlar tadqiqoti va optimal boshqaruv
fanining fundamental natijalaridan biri — maksimal oqim va minimal kesim haqidagi
teorema ko'rib chiqiladi. Masala amaliy vaziyat asosida shakllantirilib, oqim
tarmog'ida manbadan oqargacha yo'naltirilgan maksimal oqim qiymatini va shu
tarmoqning minimal sig'imli (s, t)-kesimini aniqlash maqsad qilingan. Har bir qirraning
sig'imi berilgan holda, optimal yechimni topish uchun Ford-Fulkerson algoritmi
qo'llanilgan. Kengaytiruvchi yo'l va qoldiq graf tushunchalari asosida hisoblash
jarayoni bosqichma-bosqich amalga oshirilgan va natijada tarmoqning eng yuqori
o'tkazish qobiliyatini ifodalovchi optimal yechim aniqlangan.
References
FOYDALANILGAN ADABIYOTLAR
1. Ford L. R., Fulkerson D. R. Maximal flow through a network // Canadian Journal
of Mathematics. — 1956. — Vol. 8. — P. 399–404.
2. Edmonds J., Karp R. M. Theoretical improvements in algorithmic efficiency for
network flow problems // Journal of the ACM. — 1972. — Vol. 19, No. 2. — P.
248–264.
3. Dinic E. A. Algorithm for solution of a problem of maximum flow in a network
with power estimation // Soviet Mathematics Doklady. — 1970. — Vol. 11. — P.
1277–1280.
4. Goldberg A. V., Tarjan R. E. A new approach to the maximum-flow problem //
Journal of the ACM. — 1988. — Vol. 35, No. 4. — P. 921–940.
5. Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and
Applications. — Prentice Hall, New Jersey, 1993. — 846 p.
6. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms,
3rd edition. — MIT Press, Cambridge, 2009. — 1292 p.
7. Schrijver A. Combinatorial Optimization: Polyhedra and Efficiency. — Springer,
Berlin, 2003. — 1881 p.
8. Azlarov T., Mansurov H. Matematik dasturlash asoslari. — Toshkent: O'qituvchi,
2005. — 284 b.
9. Sa'dullayev A. va boshq. Optimallashtirish usullari va operatsiyalar tadqiqoti. —
Toshkent: Universitet, 2018. — 312 b.
10. Taha H. A. Operations Research: An Introduction. — Pearson, 2017. — 848 p.
