acykliskhet

Acykliskhet, eller acykliskhet på norsk, er fraværet av sykluser i en struktur. Innen matematikk og beslektede fag beskrives et system som acyklisk hvis det ikke inneholder en lukket sløyfe. I grafteori uttrykkes dette vanligvis slik: et urettet graf er acyklisk hvis det ikke inneholder sykluser, mens et rettet graf er acyklisk hvis det ikke inneholder rettede sykluser.

Urettede acykliske grafer er skoger; en sammenkoblet acyklisk graf er et tre. I et tre med n noder er det n−1 kanter. Trær har entydige enkle stier mellom noder og inneholder ingen sykluser. Påvisning av sykluser og omforming til en acyklisk form er vanlige problemstillinger i nettverksdesign og datastrukturer.

Rettede acykliske grafer, DAG-er, har ingen rettede sykluser. De tillater en topologisk ordning og brukes til å modellere fortrinnskrav, planlegging, dataprosessering og versjonshistorier. En topologisk sortering kan utføre på en DAG hvis og bare hvis den er acyklisk.

Acykliskhet spiller også en sentral rolle i kjemi. Et acyklisk molekyl er et molekyl som ikke inneholder en ring. Alkaner og mange polymerer er acykliske, mens sykloalkaner og aromatiske forbindelser inneholder ringer. Fraværet eller tilstedeværelsen av ringe påvirker egenskaper som reaktivitet og stabilitet.

Utover grafteori og kjemi forekommer acykliskhet også i informatikk og databaser, for eksempel i avhengighetsgrafer som må være acykliske for å sikre terminering, og i databasesammenhenger som påvirker spørreoptimalisering og lagringsstruktur. Se også: syklus, syklussdeteksjon, tre (graf), DAG, topologisk sortering, sykloalkan, alkan.