Turinys:
Apibrėžimas - ką reiškia aciklas?
Aciklas yra būdvardis, naudojamas apibūdinti grafiką, kuriame nėra ciklo ar uždaro kelio. Kitaip tariant, tai yra kelias be pasikartojančių viršūnių (mazgai, sudarantys diagramą arba jungtys tarp viršūnių), išskyrus pradines ir pabaigos viršūnes.
Informatikoje jis naudojamas frazėje „nukreiptas aciklinis grafikas“ (DAG). Techniškai DAG yra diagrama, sudaryta sujungiant skirtingas viršūnes su kraštais, nukreiptais taip, kad neleidžiama naršyti seka, kurios viršūnė gali praeiti pro ją daugiau nei du kartus; todėl nėra uždaro kelio.
Techopedia paaiškina Acliclic
DAG koncepcija naudojama kuriant žodžių žaidimus, tokius kaip „Scrabble“, ir mokslinių tyrimų programas, pagrįstas biologija ir genetika. DAG taip pat naudojamas kuriant matematikos, informatikos, elektroninių schemų modelius, sudarant operacijas, apskaičiuojant formas atitinkančias reikšmes ir kt. DAG naudojami modeliuose, siekiant iliustruoti informacijos srautą per sistemą. DAG yra geresnė alternatyva kitiems duomenų struktūrų metodams, nes ji optimizuoja atminties naudojimą ir pagerina našumą.
Ciklas yra kelias, einantis per viršūnių seką, kad pradžios ir pabaigos viršūnės būtų ta pati. Jei grafikas neturi tokių ciklų, tada jis vadinamas acikliniu. Pavyzdžiui, apsvarstykite tris viršūnes, X, Y ir Z, susietas diagramoje. Važiuodamas iš bet kurios iš trijų viršūnių per jos struktūrą skirtingais įmanomais būdais, jei negalima grįžti į tą pačią pradinę viršūnę, du kartus neaplankius nė vienos viršūnės (išskyrus pradinę viršūnę ar tašką), tai yra aciklinė schema.
Trumpiausias ciklo ilgis ir aciklinio grafiko perimetras yra apibrėžti kaip begalybė. Aciklinių diagramų pavyzdžiai yra Medžiai ir Miškai. Aciklinis ir nenukreiptas grafas su bet kuriomis dviem viršūnėmis, sujungtomis tik vienu keliu, vadinamas medžiu. Šeimos medis yra geras nukreipto aciklinio medžio koncepcijos pavyzdys. Miškas yra nenukreiptas grafas, kurio pogrupiai yra medžiai.
