Minimalaus jungiamojo medžio pjūvio savybė
Jungiame neorientuotame svoriniame grafe, jei pasirinktų briaunų aibė priklauso kuriam nors minimaliam jungiamajam medžiui ir nė viena iš šių briaunų nekerta pjūvio, galima pridėti mažiausio svorio šį pjūvį kertančią briauną ir išlaikyti šį invariantą.
Esminės žinios
Jungiame neorientuotame svoriniame grafe, jei pasirinktų briaunų aibė priklauso kuriam nors minimaliam jungiamajam medžiui ir nė viena iš šių briaunų nekerta pjūvio, galima pridėti mažiausio svorio šį pjūvį kertančią briauną ir išlaikyti šį invariantą. Pasirinktos vienodo svorio briaunos nebūtinai priklauso kiekvienam optimaliam sprendiniui.
Sąlygos ir taikymo ribos
- Pjūvis padalija viršūnių aibę į dvi netuščias dalis.
- Invariantas ir sąlyga, kad pjūvis nekirstų pasirinktų briaunų, atskiria saugų pasirinkimą nuo savavališkai parinktų mažo svorio briaunų.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaita 3, teorema 3.3: saugi mažiausio svorio briauna ir išlyga dėl vienodų svorių.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); 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 paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-minimum-spanning-cut
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra