Aperiodičan graf

Aperiodični graf. Dužine ciklusa u ovom grafu iznose 5 i 6, prema tome ne postoji k>1 koji deli sve dužine ciklusa

Strogo povezan graf perioda tri.

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 k_e = j - i - 1.
• Izračunati najveći zajednički delilac seta brojeva k_e.

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.