Aperiodičan graf
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Aperiodic-graph.svg/220px-Aperiodic-graph.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/Period-3-graph.svg/220px-Period-3-graph.svg.png)
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.