Edmondso–Karpo didinančiųjų kelių algoritmas
Pradėjus nuo nulinio srauto, paieška į plotį randamas trumpiausias s–t kelias liekamajame tinkle, o srautas padidinamas mažiausiu šio kelio liekamuoju pralaidumu, atnaujinant tiesioginių ir atvirkštinių briaunų pralaidumus.
Esminės žinios
Pradėjus nuo nulinio srauto, paieška į plotį randamas trumpiausias s–t kelias liekamajame tinkle, o srautas padidinamas mažiausiu šio kelio liekamuoju pralaidumu, atnaujinant tiesioginių ir atvirkštinių briaunų pralaidumus. Kai kelio nebelieka, srautas yra maksimalus. Algoritmas atlieka O(VE²) aritmetinių operacijų, nepriklausomai nuo pralaidumų dydžių.
Sąlygos ir taikymo ribos
- Ši operacijų skaičiaus riba galioja naudojant baigtinius neneigiamus pralaidumus ir tiksliąją aritmetiką.
- Vietoj trumpiausių kelių renkantis bet kokius didinančiuosius kelius, ši riba nebegalioja; apvalinant reikia atskirai užtikrinti srauto leistinumą.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitoje 13 aptariamas srauto didinimas liekamajame tinkle ir pateikiamas teiginys 13.4 (Edmondso–Karpo), po kurio eina teorema 13.7.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaitytas visas 241 glaustai suformuluotas teiginys, prielaidos, atskirai pateiktos lygtys bei susitarimai ir visos 596 semantinės kilmės sąsajos; peržiūrėta visa autoriaus 241 įrašo tikslių šaltinių patikros matrica ir nurodyti ribotumai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai parinkti nepriklausomai patikrinti pirminių šaltinių skyriai; tai NEREIŠKIA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atliekama informacinio turinio peržiūra, o ne žmogaus atliekamas dalykinis sertifikavimas, išsamus vadovėlio atkūrimas ar eksperimentinis atkartojimas. Patvirtinimo įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-edmonds-karp-flow
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra