Aperiodičan graf
U oblasti matematičke teorije grafova, usmeren graf je aperiodičan ako ne postoji ceo broj к > 1 koji deli dužinu svakog ciklusa grafa. Ekvivalentno tome, graf je aperiodičan ako najveći zajednički delilac dužine njegovih ciklusa iznosi jedan. Najveći zajednički delilac grafa G predstavlja period grafa G.

Grafovi koji ne mogu biti aperiodični 
U svakom bipartitivnom usmerenom grafu, ciklusi imaju dužinu deljivu sa dva, dakle nijedan takav graf ne može biti aperiodičan. U svakom usmerenom acikličnom grafu, poznato je da svako k deli sve cikluse (jer ne postoji usmerenih ciklusa za deljenje), pa nijedan aciklični graf nije aperiodični. U usmerenom grafu koji ima samo jedan ciklus, k će biti dužina tog ciklusa. Iz toga sledi da ni takav graf ne može biti aperiodičan.

Testiranje aperiodičnosti 
Pretpostavlja se da je G čvrsto povezan graf i da k deli dužine svih ciklusa u G. Razmotriti rezultat obavljanja pretrage u dubinu grafa G, sa početkom u bilo kom čvoru i dodelu svakog čvora V do određenog Vi, gde je i dužina puta pretrage u dubinu od korena do čvora V. Može se pokazati da ova podela u setove Vi ima svojstvo da svaka ivica u grafu ide iz skupa Vi u drugi set V(i+1) mod k. Nasuprot tome, ako particija sa tim postoji kod povezanog grafa G, k mora deliti dužine svih ciklusa grafa G.

Period povezanog grafa G možemo pronaći prateći sledeće korake:
 Pretražimo u dubinu graf G
 Za svako e u G koje povezuje čvorove nivoa i stabla pretrage u dubinu sa čvorovima nivoa j, neka je ke = j - i - 1.
 Izračunati najveći zajednički delilac seta brojeva ke.
Graf je aperiodičan ako i samo ako period izračunat na ovaj način iznosi jedan.

Ako G nije strogo povezan graf, možemo na sličan način izvesti prethodna tri koraka tako što za svaku strogo povezanu komponentu grafa G ignorišemo ivice koje prolaze iz jedne čvrsto povezane komponente u drugu.

Džarvis i Shier opisuju veoma sličan algoritam koristeći pretragu u širinu umesto pretrage u dubinu. Prednost pretrage u dubinu je jaka analiza grafa, koja može biti uključena u istu pretragu.

Aplikacije 
U čvrsto povezanom grafu, ako su na čvorovima definisani lanci Markova u kojima je verovatnoća prelaska iz v na w različita od nula ako i samo ako postoji ivica od v do w, onda je taj lanac aperiodičan ako i samo ako je i graf aperiodičan. Lanci Markova koji su u svim stanjima rekurentni imaju čvrsto povezani graf tranzicije stanja, a lanac Markova je aperiodičan ako i samo ako je ovaj graf aperiodičan. Dakle, aperiodičnost grafova je koristan koncept u analizi lanaca Markova.

Aperiodičnost je takođe bitna kod rešavanja problema bojanja puta. Prema rešenju ovog problema (Trahtman 2009), čvrsto povezan usmeren graf u kojem svi čvorovi imaju isti izlazni stepen, ima sinhrozabilnu granu bojanja ako i samo ako je aperiodičan.

Literatura 
 Jarvis, J. P.; Shier, D. R. (1996), "Graph-theoretic analysis of finite Markov chains", in Shier, D. R.; Wallenius, K. T., Applied Mathematical Modeling: A Multidisciplinary Approach, CRC Press.
 Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics 172.

Теорија графова
U oblasti matematičke teorije grafova , usmeren graf je aperiodičan ako ne postoji ceo broj к >koji deli dužinu svakog ciklusa grafa . Ekvivalentno tome , graf je aperiodičan ako najveći zajednički delilac dužine njegovih ciklusa iznosi jedan . Najveći zajednički delilac grafa G predstavlja period grafa G . Grafovi koji ne mogu biti aperiodični U svakom bipartitivnom usmerenom grafu , ciklusi imaju dužinu deljivu sa dva , dakle nijedan takav graf ne može biti aperiodičan . U svakom usmerenom acikličnom grafu , poznato je da svako k deli sve cikluse ( jer ne postoji usmerenih ciklusa za deljenje ) , pa nijedan aciklični graf nije aperiodični . U usmerenom grafu koji ima samo jedan ciklus , k će biti dužina tog ciklusa . Iz toga sledi da ni takav graf ne može biti aperiodičan . Testiranje aperiodičnosti Pretpostavlja se da je G čvrsto povezan graf i da k deli dužine svih ciklusa u G . Razmotriti rezultat obavljanja pretrage u dubinu grafa G , sa početkom u bilo kom čvoru i dodelu svakog čvora V do određenog Vi , gde je i dužina puta pretrage u dubinu od korena do čvora V . Može se pokazati da ova podela u setove Vi ima svojstvo da svaka ivica u grafu ide iz skupa Vi u drugi set V( i+1 ) mod k . Nasuprot tome , ako particija sa tim postoji kod povezanog grafa G , k mora deliti dužine svih ciklusa grafa G . Period povezanog grafa G možemo pronaći prateći sledeće korake : Pretražimo u dubinu graf G Za svako e u G koje povezuje čvorove nivoa i stabla pretrage u dubinu sa čvorovima nivoa j , neka je ke = j - i - Izračunati najveći zajednički delilac seta brojeva ke . Graf je aperiodičan ako i samo ako period izračunat na ovaj način iznosi jedan . Ako G nije strogo povezan graf , možemo na sličan način izvesti prethodna tri koraka tako što za svaku strogo povezanu komponentu grafa G ignorišemo ivice koje prolaze iz jedne čvrsto povezane komponente u drugu . Džarvis i Shier opisuju veoma sličan algoritam koristeći pretragu u širinu umesto pretrage u dubinu . Prednost pretrage u dubinu je jaka analiza grafa , koja može biti uključena u istu pretragu . Aplikacije U čvrsto povezanom grafu , ako su na čvorovima definisani lanci Markova u kojima je verovatnoća prelaska iz v na w različita od nula ako i samo ako postoji ivica od v do w , onda je taj lanac aperiodičan ako i samo ako je i graf aperiodičan . Lanci Markova koji su u svim stanjima rekurentni imaju čvrsto povezani graf tranzicije stanja , a lanac Markova je aperiodičan ako i samo ako je ovaj graf aperiodičan . Dakle , aperiodičnost grafova je koristan koncept u analizi lanaca Markova . Aperiodičnost je takođe bitna kod rešavanja problema bojanja puta . Prema rešenju ovog problema ( Trahtman čvrsto povezan usmeren graf u kojem svi čvorovi imaju isti izlazni stepen , ima sinhrozabilnu granu bojanja ako i samo ako je aperiodičan . Literatura Jarvis , J. P . ; Shier , D. R . " Graph-theoretic analysis of finite Markov chains " , in Shier , D. R . ; Wallenius , K. T . , Applied Mathematical Modeling : A Multidisciplinary Approach , CRC Press . Trahtman , Avraham N . " The road coloring problem " , Israel Journal of Mathematics Теорија графова