Topologinė tvarka ir orientuotųjų ciklų aptikimas
Baigtinio orientuotojo grafo viršūnes galima išdėstyti taip, kad kiekvienai briaunai u→v viršūnė u eitų prieš v, tada ir tik tada, kai grafas yra aciklinis.
Esminės žinios
Baigtinio orientuotojo grafo viršūnes galima surikiuoti taip, kad kiekvienai briaunai u→v viršūnė u būtų prieš v, tada ir tik tada, kai grafas yra aciklis. Atvirkštinė visos paieškos gilyn (DFS) viršūnių apdorojimo pabaigos tvarka yra orientuotojo aciklio grafo (DAG) topologinė tvarka. Priešingu atveju, patikrinus kiekvieną briauną pagal šią tvarką, aptinkamas ciklas; naudojant gretimumo sąrašus, visa procedūra trunka O(|V|+|E|).
Sąlygos ir taikymo ribos
- Vykdykite DFS iš kiekvienos dar neaplankytos viršūnės, o ne tik iš vienos pradinės viršūnės.
- Kilpos pažeidžia topologinę tvarką; pačią viršūnių apdorojimo pabaigos tvarką būtina apversti.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Lecture10 topologinio rikiavimo įrodymas ir ciklų aptikimas, printed4; visos DFS sąnaudos apima ir izoliuotas viršūnes.
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-topological-order-cycle-test
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra