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 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 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. 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 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 -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
Jegyzetek . .
Kategória:Gráfcsaládok Kategória:Gráfalgoritmusok