Leistinasis srautas ir didžiausiojo srauto bei mažiausiojo pjūvio sertifikatas
Srautas orientuotame tinkle neviršija neneigiamų pralaidumų ir tenkina srauto tvermę visose viršūnėse, išskyrus šaltinį s ir santaką t.
Esminės žinios
Srautas orientuotame tinkle neviršija neneigiamų pralaidumų ir tenkina srauto tvermę visose viršūnėse, išskyrus šaltinį s ir santaką t. Liekamieji pralaidumai leidžia siųsti papildomą srautą tiesiogine kryptimi ir atšaukti esamą srautą. Leistinasis srautas yra didžiausias tada ir tik tada, kai nėra liekamojo s–t kelio; lygiavertiškai, kai jo vertė lygi kurio nors s–t pjūvio pralaidumui.
Sąlygos ir taikymo ribos
- Naudoti baigtinį tinklą, skirtingas s ir t viršūnes ir baigtinius pralaidumus.
- Pjūvio pralaidumas yra pradinių briaunų, nukreiptų iš šaltinio pusės į santakos pusę, pralaidumų suma; vien leistinasis srautas nėra optimalumo sertifikatas.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
13 paskaitos tinklo ir liekamojo tinklo apibrėžtys bei 13.7 teorema, spausdinto leidinio puslapiai 1–2 ir 6–7.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaitytas visas 241 glaustas teiginys, prielaidos, atskirai pateiktos lygtys bei susitarimai ir visos 596 kilmės semantinės sąsajos; peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai perimti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai nepriklausomai patikrinti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituoto šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atliekama informacinio turinio peržiūra, o ne žmogaus atliekamas dalykinis patvirtinimas, 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-max-flow-min-cut
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra