Inhoudsopgave:
Definitie - Wat betekent Acyclic?
Acyclisch is een bijvoeglijk naamwoord dat wordt gebruikt om een grafiek te beschrijven waarin er geen cyclus of gesloten pad is. Met andere woorden, het is een pad zonder herhaalde hoekpunten (knooppunten die de grafiek vormen, of koppelingen tussen hoekpunten), exclusief de begin- en eindpunten.
In de informatica wordt het gebruikt in de uitdrukking "gerichte acyclische grafiek" (DAG). Technisch gezien is DAG een grafiek die wordt gevormd door verschillende hoekpunten te verbinden met randen die zodanig zijn gericht dat het niet mogelijk is om door een reeks te navigeren waar een hoekpunt meer dan tweemaal doorheen kan gaan; daarom is er geen gesloten pad.
Techopedia legt Acyclic uit
Het concept van DAG wordt gebruikt om woordspellen te ontwerpen zoals Scrabble en wetenschappelijke onderzoekstoepassingen op basis van biologie en genetica. DAG wordt ook gebruikt bij het bouwen van modellen in wiskunde, informatica, elektronische schakelingen, compileerbewerkingen, computergerelateerde waarden op formulieren, enz. DAG's worden in modellen gebruikt om de informatiestroom door een systeem te illustreren. DAG is een beter alternatief voor andere technieken in datastructuren door optimalisatie van het geheugengebruik en een verbetering van de prestaties.
Een cyclus is een pad dat wordt doorkruist door een reeks hoekpunten, zodat zowel de begin- als de eindhoeken hetzelfde punt zijn. Als een grafiek dergelijke cycli niet heeft, wordt deze acyclisch genoemd. Beschouw bijvoorbeeld de drie hoekpunten, X, Y en Z gekoppeld in een grafiek. Terwijl je op verschillende manieren door een van de drie hoekpunten door de structuur ervan gaat, als je niet terug kunt keren naar hetzelfde startpunt zonder een hoekpunt te bezoeken (exclusief het startpunt of punt) twee keer, dan is het een Acyclische grafiek.
De lengte van de kortste cyclus en de omtrek van een acyclische grafiek is gedefinieerd als oneindig. Voorbeelden van acyclische grafieken zijn bomen en bossen. Een acyclische en niet-gerichte grafiek met twee hoekpunten verbonden door slechts één pad wordt een boom genoemd. Een stamboom is een goed voorbeeld van het concept van een gerichte acyclische boom. Een forest is een niet-gerichte grafiek waarvan de subsets bomen zijn.
