Grafai vaizduoja porinius ryšius; medžiams taikoma acikliškumo sąlyga.
Esminės žinios
Baigtinį grafą sudaro viršūnės V ir jas jungiančios briaunos; orientuotos briaunos yra sutvarkytos poros. Netuščias paprastasis neorientuotas medis yra jungus ir neturi ciklų; kiekvieną viršūnių porą jungia vienintelis paprastasis kelias.
Sąlygos ir taikymo ribos
Šiame įraše paprastieji grafai neturi kilpų ir lygiagrečių briaunų.
Orientuotas aciklinis grafas nebūtinai yra neorientuotas medis.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Grafų apibrėžimai, gretimumo pateikimo būdai, atstumai pagal briaunų skaičių ir BFS trumpiausi keliai. Jungaus aciklinio neorientuoto medžio apibrėžimas ir vienintelio kelio savybė; klaida, nurodanti n−1 viršūnes, neįtraukta.
2026-10-10 · Baigtinių grafų susitarimai ir jungumo bei acikliškumo medžio kriterijus.
Susiję žinyno įrašai
Tyrinėkite ryšius šioje pažinimo srityje ir jos sąsajas su kitomis sritimis.
Rodomi 1–11 iš 11 ryšių
Mokslinių žinių ryšiai · 11 / 11
Ryšio tipas nusako santykį. Susieti teiginiai, šaltiniai ir sąlygos apibrėžia jo taikymo ribas.
BFS paeiliui nagrinėja sluoksnius pagal atstumą, matuojamą briaunų skaičiumi; DFS eina per neaplankytas gretimas viršūnes ir grįžta atgal. Naudojant gretimumo sąrašus ir pastovios sąnaudos patikras, ar viršūnė aplankyta, viso grafo apėjimo laiko sudėtingumas yra O(|V|+|E|). BFS nustato trumpiausius atstumus nesvertiniame grafe; DFS nebūtinai.
BFS randa trumpiausius kelius nesvertiniame grafe, kai jų ilgis matuojamas briaunų skaičiumi. Dijkstros algoritmas apskaičiuoja mažiausio svorio atstumus iš vienos pradinės viršūnės, kai visų briaunų svoriai yra neneigiami, kiekviename žingsnyje galutinai nustatydamas mažiausią preliminarų atstumą.
AVL dvejetainiame paieškos medyje kiekvienos viršūnės pomedžių aukščiai skiriasi ne daugiau kaip vienetu. Jo aukštis yra O(log n); paieška ir atnaujinimai, atliekant vietinius pasukimus ir palaikant aukščių reikšmes, blogiausiu atveju trunka O(log n) laiko.
Dvejetainėje maksimumo krūvoje masyve saugomas dvejetainis medis, kurio visi lygiai, išskyrus galbūt paskutinį, užpildyti, o paskutinio lygio viršūnės išdėstytos iš kairės į dešinę be tarpų; kiekvieno tėvinio mazgo raktas yra ne mažesnis už jo vaikinių mazgų raktus. Maksimumo paieškos trukmė yra O(1); krūvos tvarkos atkūrimas aukštyn arba žemyn po įterpimo ar pašalinimo trunka O(log n), o krūvos sudarymas iš apačios į viršų – O(n).
Dinaminio programavimo metu apibrėžiami daliniai uždaviniai ir rekurentiniai sąryšiai, tikrinama aciklinė priklausomybių tvarka ir baziniai atvejai, o kiekvienas reikalingas dalinis uždavinys sprendžiamas vieną kartą, įsimenant rezultatus arba sprendžiant nuo mažesnių uždavinių prie didesnių. Bendras darbo kiekis gaunamas sumuojant nerekursinio darbo kiekį visose apskaičiuotose būsenose.
Dvejetainiame prefiksiniame kode nė vienas visas kodinis žodis nėra kito kodinio žodžio pradinis segmentas, todėl galima iš karto nuosekliai dekoduoti. Vienareikšmiškai dekoduojamo kodo kodinių žodžių ilgiai tenkina Σ2⁻ˡⁱ≤1; ir atvirkščiai, teigiami sveikieji ilgiai, tenkinantys šią nelygybę, leidžia sudaryti prefiksinį kodą. Tikėtinas ilgis yra ne mažesnis už šaltinio entropiją.
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.
3CNF formulėje su m klauzulių kiekvienam literalo pasirodymui sukurkite viršūnę. Sujunkite pasirodymus iš skirtingų klauzulių, jeigu jų literalai nėra vienas kito neiginiai. Formulė yra patenkinama tada ir tik tada, kai grafas turi m dydžio kliką: iš kiekvienos klauzulės pasirinkite vieną teisingą literalo pasirodymą; atvirkščiai, klikos suderinamus literalus galima išplėsti iki kintamųjų reikšmių priskyrimo.
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.
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|).
Logaritminės atminties daugelio į vieną redukcija apskaičiuoja f taip, kad x∈A tada ir tik tada, kai f(x)∈B, naudodama tik skaitomą įvestį, O(log n) darbinę juostą ir tik rašomą išvestį. Pasiekiamumo iš s į t orientuotajame grafe uždavinys yra NL-pilnas šių redukcijų atžvilgiu: apriboto ilgio keliui nedeterministiškai atspėti pakanka logaritminės atminties, o kiekvienas NL skaičiavimas redukuojamas į jo polinominio dydžio konfigūracijų grafą.