Aperiodikus gráf
A matematika, azon belül a gráfelmélet területén egy irányított gráf akkor aperiodikus, ha nem létezik olyan k > 1 egész szám, ami a gráf minden körének hosszúságát osztja. Ezzel ekvivalens megfogalmazás szerint egy gráf akkor aperiodikus, ha körei hosszának legnagyobb közös osztója, amit a G gráf periódusának neveznek, éppen egy.
Gráfok, melyek nem lehetnek aperiodikusak
[szerkesztés]Egy irányított páros gráfban minden kör hosszúsága páros, ezért az irányított páros gráfok nem lehetnek aperiodikusak. Az irányított körmentes gráfokban üres igazság, hogy tetszőleges k minden kör hosszúságának osztója (hiszen nincs irányított kör, melynek osztója lehetne), ezért az irányított körmentes gráfokat nem tekintik aperiodikusnak. Az irányított körgráfokban pedig egyetlen kör található, ezért minden kör hosszúsága osztható n-nel, a kör hosszával.
Az aperiodikusság tesztelése
[szerkesztés]Tegyük fel, hogy G erősen összefüggő és k osztója G összes körhosszának. Tekintsük az eredményét egy G tetszőleges csúcsából kiinduló mélységi keresésnek, ami minden v csúcsot hozzárendel egy Vi halmazhoz, ahol i a mélységi keresési fa gyökerétől v-ig vezető út modulo k vett hosszúsága. (Jarvis & Shier 1996) megmutatták, hogy ez a Vi halmazokra particionálás rendelkezik azzal a tulajdonsággal, hogy a gráf minden éle egy Vi halmazból egy V(i + 1) mod k halmazba mutat. Megfordítva, ha ha egy erősen összefüggő G gráfnak az említett tulajdonságú particionálása létezik, k-nak osztania kell G minden körének hosszúságát.
Így tehát a G erősen összefüggő gráf periódusa a következő lépésekben megkereshető:
- Végezzünk mélységi keresést G-ben
- Minden G-beli e-re, ami egy a mélységi keresési fa i szintjén lévő csúcsot egy j szinten levővel köt össze, legyen ke = j - i - 1.
- Számítsuk ki a ke számhalmaz legnagyobb közös osztóját.
A gráf pontosan akkor aperiodikus, ha az így kiszámított periódus értéke egy.
Ha G nem erősen összefüggő, hasonló számítás végezhető G minden erősen összefüggő komponensében, eltekintve közben az erősen összefüggő komponensek között húzódó élektől.
Jarvis és Shier hasonló, de szélességi keresést alkalmazó algoritmust is leírnak; a mélységi keresés előnye, hogy a keresés során az erős összefüggőségi keresés is könnyen elvégezhető.
Alkalmazások
[szerkesztés]Egy erősen összefüggő gráfban ha a csúcsokon Markov-láncot definiálunk, melyben a v-ből w-be való átmenet pontosan akkor nem nulla, ha létezik v-ből w-be mutató él, akkor ez a lánc pontosan akkor aperiodikus, amikor a gráf aperiodikus. Egy olyan Markov-láncnak, melyben minden állapot visszatérő, erősen összefüggő állapotátmeneti gráfja van, mely pontosan akkor aperiodikus, ha a Markov-lánc aperiodikus. Így a gráfok aperiodikussága hasznos fogalom a Markov-láncok aperiodikusságának vizsgálatánál.
Az aperiodikusság az útszínezési probléma megoldásának fontos szükséges feltétele. A probléma (Trahtman 2009)-féle megoldása szerint egy olyan erősen összefüggő irányított gráf, melyben a csúcsok ki-foka megegyezik, pontosan akkor rendelkezik szinkronizálható élszínezéssel, ha aperiodikus.
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben az Aperiodic graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
[szerkesztés]- 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, <http://www.ces.clemson.edu/~shierd/Shier/markov.pdf>.
- Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics 172 (1): 51–60, DOI 10.1007/s11856-009-0062-5.