17:
29:
357:, then this chain is aperiodic if and only if the graph is aperiodic. A Markov chain in which all states are recurrent has a strongly connected state transition graph, and the Markov chain is aperiodic if and only if this graph is aperiodic. Thus, aperiodicity of graphs is a useful concept in analyzing the aperiodicity of Markov chains.
325:
in place of depth-first search; the advantage of depth-first search is that the strong connectivity analysis can be incorporated into the same search.
115:
divides all cycles (because there are no directed cycles to divide) so no directed acyclic graph can be aperiodic. And in any directed
382:
Jarvis, J. P.; Shier, D. R. (1996), "Graph-theoretic analysis of finite Markov chains", in Shier, D. R.; Wallenius, K. T. (eds.),
402:
334:
311:
33:
449:
444:
72:
104:
361:
322:
100:
68:
411:
173:
148:
136:
421:
397:
218:
96:
20:
An aperiodic graph. The cycles in this graph have lengths 5 and 6; therefore, there is no
300:
49:
383:
438:
108:
338:
45:
318:, ignoring the edges that pass from one strongly connected component to another.
116:
41:
426:
75:
of the lengths of its cycles is one; this greatest common divisor for a graph
16:
369:
28:
368:), a strongly connected directed graph in which all vertices have the same
221:, if a partition with this property exists for a strongly connected graph
310:
is not strongly connected, we may perform a similar computation in each
64:
57:
360:
Aperiodicity is also an important necessary condition for solving the
372:
has a synchronizable edge coloring if and only if it is aperiodic.
119:, there is only one cycle, so every cycle's length is divisible by
103:. Therefore, no directed bipartite graph can be aperiodic. In any
416:
27:
15:
341:
on the vertices, in which the probability of transitioning from
179:) of the path in the depth-first search tree from the root to
196:
has the property that each edge in the graph goes from a set
385:
236:
Thus, we may find the period of a strongly connected graph
286:
Compute the greatest common divisor of the set of numbers
321:
Jarvis and Shier describe a very similar algorithm using
71:
of the graph. Equivalently, a graph is aperiodic if the
262:
of the depth-first search tree to a vertex on level
155:, starting at any vertex, and assigning each vertex
24: > 1 that divides all cycle lengths.
349:is nonzero if and only if there is an edge from
364:. According to the solution of this problem (
8:
184:
303:the period computed in this fashion is 1.
425:
415:
229:must divide the lengths of all cycles in
365:
147:. Consider the results of performing a
400:(2009), "The road coloring problem",
143:divides the lengths of all cycles in
7:
14:
258:that connects a vertex on level
244:Perform a depth-first search of
187:) that this partition into sets
91:Graphs that cannot be aperiodic
1:
403:Israel Journal of Mathematics
312:strongly connected component
123:, the length of that cycle.
466:
427:10.1007/s11856-009-0062-5
335:strongly connected graph
240:by the following steps:
127:Testing for aperiodicity
99:, all cycle lengths are
63: > 1 that
34:strongly connected graph
299:The graph is aperiodic
185:Jarvis & Shier 1996
73:greatest common divisor
105:directed acyclic graph
37:
25:
362:road coloring problem
172:is the length (taken
31:
19:
398:Trahtman, Avraham N.
323:breadth first search
67:the length of every
337:, if one defines a
183:. It can be shown (
149:depth-first search
137:strongly connected
38:
36:with period three.
26:
457:
450:Graph algorithms
430:
429:
419:
392:
390:
95:In any directed
465:
464:
460:
459:
458:
456:
455:
454:
435:
434:
396:
388:
381:
378:
331:
294:
274:
216:
203:to another set
201:
195:
167:
129:
97:bipartite graph
93:
56:if there is no
12:
11:
5:
463:
461:
453:
452:
447:
445:Graph families
437:
436:
433:
432:
394:
377:
374:
330:
327:
301:if and only if
297:
296:
290:
284:
270:
248:
207:
199:
191:
163:
128:
125:
92:
89:
79:is called the
52:is said to be
50:directed graph
13:
10:
9:
6:
4:
3:
2:
462:
451:
448:
446:
443:
442:
440:
428:
423:
418:
413:
409:
405:
404:
399:
395:
387:
386:
380:
379:
375:
373:
371:
367:
366:Trahtman 2009
363:
358:
356:
352:
348:
344:
340:
336:
328:
326:
324:
319:
317:
313:
309:
304:
302:
293:
289:
285:
282:
278:
273:
269:
265:
261:
257:
253:
249:
247:
243:
242:
241:
239:
234:
232:
228:
224:
220:
215:
211:
206:
202:
194:
190:
186:
182:
178:
175:
171:
166:
162:
158:
154:
150:
146:
142:
138:
134:
131:Suppose that
126:
124:
122:
118:
114:
110:
109:vacuous truth
106:
102:
98:
90:
88:
86:
82:
78:
74:
70:
66:
62:
59:
55:
51:
47:
43:
35:
30:
23:
18:
410:(1): 51–60,
407:
401:
384:
359:
354:
350:
346:
342:
339:Markov chain
332:
329:Applications
320:
315:
307:
305:
298:
291:
287:
280:
276:
271:
267:
263:
259:
255:
251:
245:
237:
235:
230:
226:
222:
213:
209:
204:
197:
192:
188:
180:
176:
169:
164:
160:
156:
152:
144:
140:
132:
130:
120:
112:
94:
84:
80:
76:
60:
53:
46:graph theory
42:mathematical
39:
21:
391:, CRC Press
117:cycle graph
111:that every
439:Categories
376:References
219:Conversely
107:, it is a
417:0709.0099
370:outdegree
250:For each
212:+ 1) mod
159:to a set
139:and that
54:aperiodic
44:area of
65:divides
58:integer
40:In the
266:, let
174:modulo
168:where
81:period
412:arXiv
389:(PDF)
333:In a
69:cycle
283:− 1.
101:even
48:, a
422:doi
408:172
353:to
345:to
314:of
306:If
254:in
151:of
135:is
83:of
441::
420:,
406:,
279:−
275:=
233:.
225:,
217:.
87:.
32:A
431:.
424::
414::
393:.
355:w
351:v
347:w
343:v
316:G
308:G
295:.
292:e
288:k
281:i
277:j
272:e
268:k
264:j
260:i
256:G
252:e
246:G
238:G
231:G
227:k
223:G
214:k
210:i
208:(
205:V
200:i
198:V
193:i
189:V
181:v
177:k
170:i
165:i
161:V
157:v
153:G
145:G
141:k
133:G
121:n
113:k
85:G
77:G
61:k
22:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
