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.

Egy aperiodikus gráf. A gráf köreinek hosszúsága 5, illetve 6, ezért nincs olyan k > 1 egész szám, ami mindegyik körhosszúság osztója lenne.

Egy erősen összefüggő gráf, melynek periódusa három.

Gráfok, melyek nem lehetnek aperiodikusak

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

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 V_i 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 V_i halmazokra particionálás rendelkezik azzal a tulajdonsággal, hogy a gráf minden éle egy V_i 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 k_e = j - i - 1.
• Számítsuk ki a k_e 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

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

• 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

• 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.