En rettet graf siges at være aperiodisk , hvis der ikke er et heltal k > 1, der dividerer længden af en cyklus af grafen. Tilsvarende er en graf aperiodisk, hvis den største fælles divisor af dens cykluslængder er én. Denne største fælles divisor for graf G kaldes perioden for graf G.
I enhver rettet todelt graf har alle cyklusser en længde, der er delelig med to. Af denne grund kan ingen todelt graf være aperiodisk. I enhver rettet acyklisk graf er det sandt, men fuldstændig meningsløst, at ethvert tal k deler alle cyklusser (da der overhovedet ikke er nogen rettede cykler), så ingen rettet acyklisk graf kan være aperiodisk. Og i enhver orienteret cyklus er der kun én cyklus, så enhver længde af en cyklus er delelig med n , længden af den cyklus.
Antag, at graf G er stærkt forbundet, og at k deler længderne af alle cyklusser i graf G.
Overvej resultaterne af en dybde-først-søgning på en graf G , startende ved et hvilket som helst toppunkt, og tildel hvert toppunkt v et sæt V i , hvor i er lig med længden (modulo k ) af stien i dybde-første søgning træ fra roden v . Det kan vises [1] at denne toppunktspartition V i har den egenskab, at hver kant i grafen kommer fra et sæt V i og ender i et andet sæt V ( i + 1) mod k . Omvendt, hvis der eksisterer en partition med denne egenskab for en stærkt forbundet graf G , så skal k dividere længderne af alle cyklusser af G .
Således kan vi finde perioden for en stærkt forbundet graf G ved at følge disse trin:
Grafen er aperiodisk, hvis og kun hvis perioden beregnet på dette stadium er lig med 1.
Hvis grafen G ikke er stærkt forbundet, kan vi udføre lignende beregninger på hver stærkt forbundne komponent af G , idet vi ignorerer kanterne, der forbinder en stærkt forbundet komponent til en anden.
Jarvis og Shear beskrev en meget lignende algoritme ved hjælp af bredde -først -søgning i stedet for dybde-først-søgning. Fordelen ved dybde-først-søgning er, at stærk forbindelsesanalyse kan indgå i den samme søgning.
Hvis vi i en stærkt forbundet digraf definerer en Markov-kæde på toppunkter, hvor sandsynligheden for at gå fra v til w er ikke-nul, hvis og kun hvis der er en bue fra v til w , så er denne kæde aperiodisk hvis og kun hvis grafen er aperiodisk. En Markov-kæde, hvor alle tilstande er tilbagevendende, har en stærkt forbundet overgangsgraf, og en Markov-kæde er aperiodisk, hvis og kun hvis denne graf er aperiodisk. Aperiodiciteten af grafer er således et nyttigt koncept i analysen af aperiodiciteten af Markov-kæder.
Aperiodicitet er også en vigtig nødvendig betingelse for at løse vejfarveproblemet . Ifølge løsningen af dette problem af Trachtman [2] har en stærkt forbundet rettet graf, hvor alle hjørner har den samme i -grad, en synkroniseret buefarvning , hvis og kun hvis den er aperiodisk.