Walks, Trails, Paths, Circuits and Cycles

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Six words for moving through a graph

Graph theory has a small family of words for travelling along the edges of a graph: walk, trail and path for routes that may end anywhere, and closed walk, circuit and cycle for routes that come back to where they started. They differ in only three things: whether a vertex may be visited twice, whether an edge may be used twice, and whether the route ends at its starting vertex.

• A walk is a sequence of vertices v0, v1, ..., vk in which every two consecutive vertices are joined by an edge. Vertices and edges may repeat. The length of the walk is k, the number of steps taken, with repeated edges counted every time they are used.
• A trail is a walk that never uses the same edge twice. It may pass through a vertex more than once.
• A path is a walk that never visits the same vertex twice. An edge used twice would bring its two ends back, so a path never repeats an edge either.
• A closed walk is a walk whose last vertex is its first.
• A circuit is a closed trail: it ends where it started and uses no edge twice.
• A cycle is a closed walk of length at least 3 in which no vertex repeats, apart from the last vertex being the first.

These are the definitions used by most modern graph theory textbooks, but not by all of them, and section 4 shows where the main conventions differ. The running example is a strip of four triangles with 6 vertices and 9 edges:

edges = {AB, AC, BC, BD, CD, CE, DE, DF, EF}      6 vertices, 9 edges

top row:       B     D     F
bottom row:  A     C     E

deg:   A 2   B 3   C 4   D 4   E 3   F 2

Each route in the picture is the most specific of the six that it can be called:

• A, B, C, A, B, D is a walk of length 5. It uses the edge A-B twice, so it is not a trail.
• A, C, B, D, C, E is a trail of length 5. It visits C twice, so it is not a path, but each of its five edges is different.
• A, C, D, F is a path of length 3. Its four vertices are all different.
• A, B, C, D, B, A is a closed walk of length 5. It returns to A, but uses A-B twice.
• A, B, C, D, E, C, A is a circuit of length 6. It returns to A with six different edges, but passes through C twice.
• A, B, D, F, E, C, A is a cycle of length 6. It runs around the outside of the strip and repeats nothing.

A single vertex on its own, such as A, also counts: it is a walk of length 0 and a path of length 0, called a trivial walk. It matters mainly for edge cases in proofs and code, where "the path from a vertex to itself" should exist and have length 0.

2. How the six fit together

The definitions nest. Every path is a trail, because a route that never revisits a vertex cannot reuse an edge, and every trail is a walk. On the closed side, every cycle is a circuit and every circuit is a closed walk. None of these inclusions reverses, as the examples in section 1 show. Three questions are always enough to find the right name, and the order in which they are asked does not matter.

The counts in the example show how quickly the families grow apart. From A to F there are exactly 13 paths: 3 of length 3, 6 of length 4 and 4 of length 5. There are 23 trails: the 13 paths plus 10 trails that pass through some vertex twice, such as A, C, B, D, C, E, F. There are infinitely many walks, because a walk may run back and forth along any edge as often as it likes. Only when the length is fixed does the number of walks become finite, and section 6 counts them exactly.

Two details trip up beginners:

• Length counts edges, not vertices. The path A, C, D, F has four vertices and length 3. A cycle through k vertices has length k, because its last step returns to the start.
• One cycle has many spellings. The cycle A, B, D, F, E, C, A can be written starting at any of its 6 vertices and in either direction, which gives 12 sequences for one cycle. A path can likewise be read from either end. Code that counts cycles by listing sequences must divide by 2k, or it will count every cycle of length k that many times.

Why does a cycle need length at least 3? In a simple graph the shortest closed walks, such as A, B, A, go out along an edge and come straight back along the same one. That repeats an edge, so it is neither a circuit nor a cycle. In a multigraph the situation changes: two parallel edges between the same two vertices form a cycle of length 2, and a loop forms a cycle of length 1. This is also why the formal definition of a walk lists edges as well as vertices, v0, e1, v1, e2, ..., vk: when two parallel edges join the same vertices, the list of vertices alone does not say which edge was used. In a simple graph the vertices determine the edges, and listing the vertices is enough.

3. Checking a route in code

The definitions translate directly into a short function. It takes a simple graph and a sequence of vertices, checks that every step follows an edge, and then asks the three questions from section 2.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def classify(adj, seq):
    """Name the most specific kind of walk that the vertex sequence seq is."""
    steps = list(zip(seq, seq[1:]))
    if any(v not in adj[u] for u, v in steps):
        return 'not a walk'
    closed = len(seq) > 1 and seq[0] == seq[-1]
    edges = [frozenset(step) for step in steps]
    no_repeated_edge = len(set(edges)) == len(edges)
    inner = seq[:-1] if closed else seq          # a closed walk ends where it began
    no_repeated_vertex = len(set(inner)) == len(inner)
    if not closed:
        return 'path' if no_repeated_vertex else 'trail' if no_repeated_edge else 'walk'
    if no_repeated_vertex and len(edges) >= 3:
        return 'cycle'
    return 'circuit' if no_repeated_edge else 'closed walk'

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
for seq in ['ABCABD', 'ACBDCE', 'ACDF', 'ABCDBA', 'ABCDECA', 'ABDFECA', 'ABA', 'ABE']:
    print(seq, classify(strip, seq))
# ABCABD walk
# ACBDCE trail
# ACDF path
# ABCDBA closed walk
# ABCDECA circuit
# ABDFECA cycle
# ABA closed walk
# ABE not a walk

The function first rejects A, B, E, because there is no edge between B and E. For a closed route it compares vertices without the final one, since a closed walk always repeats its first vertex at the end. The test len(edges) >= 3 is what keeps A, B, A from being reported as a cycle: its two vertices are different, but its two steps use the same edge. The whole check takes time proportional to the length of the route.

4. Why textbooks disagree

If you have met these words before, you may have met them with different meanings. Graph theory grew up in several countries and fields at once, and the vocabulary was never fully standardised. The table compares the words that some widely used textbooks give to the same four ideas.

Since Harary's book of 1969, most graph theory texts agree on the core: a walk may repeat anything and a path repeats nothing. Ore's Theory of Graphs of 1962 shows the older usage, in which a path was a route without repeated edges, what is now called a trail. Rosen's Discrete Mathematics and Its Applications, a standard textbook for first courses in discrete mathematics, keeps a version of it: path means any walk, and a simple path is a route that does not repeat an edge. Rosen notes the conflict himself and lists walk, closed walk and trail as the other books' words, but a student who learns "path" from Rosen and then opens a graph theory text will find the same word meaning something stricter.

The words circuit and cycle are the least stable. West, and Chartrand and Zhang, use circuit for a closed trail, as this article does. Ore used circuit for what is now a cycle, and engineers often say "circuit" for any closed loop. Directed graphs add another layer: in Berge's classic books, first written in French, a route in an undirected graph is a chaîne (chain) and a closed one a cycle, while a route along arrows is a chemin (path) and a closed one a circuit.

The safest habit is to state the definition you are using the first time a word appears, or to replace the ambiguous word with the property: "a route that repeats no vertex" cannot be misread. When reading, look for the definition in the first chapter and expect it to differ from the last book you read.

The best-known casualty of the naming is the Eulerian path. It uses every edge of a graph exactly once, and it usually passes through vertices several times, so in the vocabulary of this article it is a trail, not a path. The name survives because the problem is older than the vocabulary, and "Eulerian trail" is now the more careful name for the same thing. The Hamiltonian path, which visits every vertex exactly once, really is a path. Section 8 returns to both.

5. Every walk contains a path

The most useful fact about walks is that repetition is never needed to get somewhere. If there is a walk from u to v, there is a path from u to v, and the path is no longer than the walk. The proof is a shortcut. If the walk visits some vertex x twice, delete everything between the two visits: the walk still runs from u to v, and it is shorter. Repeat until no vertex repeats. What is left is a path.

This small lemma has large consequences:

• Connectivity. "There is a walk between any two vertices" and "there is a path between any two vertices" mean the same thing, so a graph can be called connected using either word. The guide to connected components builds on this.
• Shortest routes are paths. A shortest walk between two vertices never repeats a vertex, since cutting out the repeat would make it shorter. This is why breadth-first search and Dijkstra's algorithm can search over walks without ever checking for repeated vertices, and still return paths. The guide to shortest path algorithms covers both.
• Negative weights break it. With negative edge weights, cutting out a loop can make a route longer, because the loop may have had negative total weight. If a negative cycle can be reached, walks can be made as cheap as you like by going round it again, and shortest walks stop existing. Shortest paths still exist, but finding one in general becomes NP-hard, since it would also find the longest paths of section 7. The guide to the Bellman-Ford algorithm shows how to detect such cycles.

Closed walks need more care. A closed walk does not always contain a cycle: A, B, A is closed but contains none. A closed walk of odd length always does, and the cycle it contains is odd as well. Split the closed walk at a repeated vertex into two shorter closed walks. Their lengths add up to the original odd length, so one of them is odd. Keep the odd one and repeat. The process stops at an odd closed walk with no repeated vertex, and since a simple graph has no closed walk of length 1, that walk is a cycle of length at least 3.

This argument is the key step in Kőnig's theorem: a graph is bipartite exactly when it has no cycle of odd length. A circuit splits the same way, into cycles that share no edge. The program below carries out all three operations: it cuts loops out of a walk, finds an odd cycle inside an odd closed walk, and splits a circuit into cycles.

def walk_to_path(walk):
    """Cut out every loop. The result is a path with the same two ends."""
    path, where = [], {}
    for v in walk:
        if v in where:                       # back at v: drop everything since the last visit
            for u in path[where[v] + 1:]:
                del where[u]
            del path[where[v] + 1:]
        else:
            where[v] = len(path)
            path.append(v)
    return ''.join(path)

def split_closed_walk(walk):
    """Split a closed walk at its first repeated vertex into two shorter closed walks."""
    seen = {}
    for i, v in enumerate(walk[:-1]):
        if v in seen:
            j = seen[v]
            return walk[j:i + 1], walk[:j] + walk[i:]
        seen[v] = i
    return None                              # nothing repeats: a cycle, or a step there and back

def odd_cycle(walk):
    """A closed walk of odd length always contains a cycle of odd length."""
    while True:
        parts = split_closed_walk(walk)
        if parts is None:
            return walk
        walk = next(p for p in parts if (len(p) - 1) % 2 == 1)

def circuit_to_cycles(walk):
    """Split a circuit into cycles that share no edge."""
    parts = split_closed_walk(walk)
    if parts is None:
        return [walk]
    return circuit_to_cycles(parts[0]) + circuit_to_cycles(parts[1])

print(walk_to_path('ACBDCEF'))               # walk of length 6
# ACEF
print(odd_cycle('ABCDCA'))                   # closed walk of length 5, edge C-D used twice
# ABCA
print(circuit_to_cycles('ABCDECA'))          # circuit of length 6 through C twice
# ['CDEC', 'ABCA']

The trail A, C, B, D, C, E, F visits C twice, so the loop C, B, D, C goes, leaving A, C, E, F. The closed walk A, B, C, D, C, A splits at C into C, D, C, of length 2, and A, B, C, A, of length 3, which is the odd cycle. The circuit A, B, C, D, E, C, A splits at C into the two triangles C, D, E, C and A, B, C, A.

The circuit split is a special case of a theorem published by Oswald Veblen in 1912: the edges of a graph can be divided into cycles that share no edge if and only if every vertex has even degree. A cycle uses two edges at each vertex it passes through, so the degrees must be even; the converse follows by repeatedly removing a cycle, which keeps every degree even.

6. Counting walks with matrix powers

Walks are hard to list but easy to count. Write the graph as its adjacency matrix A, with a 1 in row u, column v when u and v are adjacent and a 0 otherwise. The guide to graph representation explains the matrix itself. Then a classical fact holds: the entry in row u, column v of the power Ak is the number of walks of length k from u to v.

The reason is the rule for multiplying matrices. A walk of length k from u to v is a walk of length k - 1 from u to some vertex w, followed by one step from w to v. So the number of such walks is the sum over all w of (walks of length k - 1 from u to w) times A[w][v], which is exactly the entry of Ak-1 times A. Induction on k does the rest.

The strip shows several consequences at once:

• The diagonal of A2 is the list of degrees. A closed walk of length 2 goes out along an edge and comes back, and there is one for each edge at the vertex: 2, 3, 4, 4, 3, 2 for A to F.
• A2[A][D] = 2, for the walks A, B, D and A, C, D.
• The first power with a nonzero entry gives the distance. A1 and A2 are 0 in row A, column F, and A3 is 3. So the distance from A to F is 3, and the three walks of that length are the three shortest paths A, B, D, F, A, C, D, F and A, C, E, F. By section 5, the shortest walks are always paths.
• Triangles come from the diagonal of A3. A closed walk of length 3 in a simple graph runs around a triangle. Each triangle is counted once from each of its 3 vertices in each of 2 directions, so the number of triangles is the sum of the diagonal divided by 6: here 24 / 6 = 4, the triangles ABC, BCD, CDE and DEF.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def matmul(X, Y):
    return [[sum(x * y for x, y in zip(row, col)) for col in zip(*Y)] for row in X]

def walk_counts(adj, order, k):
    """Entry [i][j] of the k-th power of the adjacency matrix counts walks of length k."""
    A = [[int(v in adj[u]) for v in order] for u in order]
    M = A
    for _ in range(k - 1):
        M = matmul(M, A)
    return M

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
order = 'ABCDEF'
for k in range(1, 7):
    M = walk_counts(strip, order, k)
    print(f'length {k}:  A to F {M[0][5]:3}   A back to A {M[0][0]:3}')
# length 1:  A to F   0   A back to A   0
# length 2:  A to F   0   A back to A   2
# length 3:  A to F   3   A back to A   2
# length 4:  A to F   6   A back to A  11
# length 5:  A to F  29   A back to A  24
# length 6:  A to F  78   A back to A  92
A3 = walk_counts(strip, order, 3)
print('triangles:', sum(A3[i][i] for i in range(len(order))) // 6)
# triangles: 4

The number of walks from A to F grows quickly with the length, from 3 to 78 in three steps, yet the computation stays cheap. Each multiplication of two n by n matrices takes about n3 operations, and repeated squaring reaches Ak in about log2 k multiplications, so even walks of length one million can be counted exactly in a few dozen matrix products. The sum of the diagonal of Ak is also the sum of the k-th powers of the matrix's eigenvalues, which is where walks meet spectral graph theory: the largest eigenvalue sets the growth rate of the number of long walks.

7. Walks are easy, paths are hard

The matrix trick has no counterpart for paths. The number of paths between two vertices is, in general, hard to compute: Leslie Valiant proved in 1979 that counting the paths between two given vertices is #P-complete, the counting analogue of NP-complete. No method much better than trying the routes one by one is known, and none is expected. The program below counts paths by exactly that kind of search, and counts trails the same way with edges in place of vertices.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def count_paths(adj, s, t, seen=None):
    """Number of paths from s to t: try every unvisited neighbour, then undo."""
    if s == t:
        return 1
    seen = seen or {s}
    total = 0
    for w in adj[s] - seen:
        seen.add(w)
        total += count_paths(adj, w, t, seen)
        seen.remove(w)
    return total

def count_trails(adj, s, t, used=None):
    """Number of trails from s to t. A trail may pass through t and come back to it later."""
    used = used or set()
    total = 1 if s == t else 0
    for w in adj[s]:
        e = frozenset((s, w))
        if e not in used:
            used.add(e)
            total += count_trails(adj, w, t, used)
            used.remove(e)
    return total

strip = graph(['AB', 'AC', 'BC', 'BD', 'CD', 'CE', 'DE', 'DF', 'EF'])
print(count_paths(strip, 'A', 'F'), count_trails(strip, 'A', 'F'))
# 13 23

def grid(n):
    """The n by n grid of streets: vertices (row, column), edges to the right and down."""
    return graph([((r, c), (r, c + 1)) for r in range(n) for c in range(n - 1)] +
                 [((r, c), (r + 1, c)) for r in range(n - 1) for c in range(n)])

for n in range(2, 6):
    print(n, count_paths(grid(n), (0, 0), (n - 1, n - 1)))
# 2 2
# 3 12
# 4 184
# 5 8512

On the strip the search confirms the counts from section 2: 13 paths and 23 trails from A to F. The grid shows how fast the numbers explode. Between opposite corners of a grid of streets with 2, 3, 4 and 5 vertices on a side there are 2, 12, 184 and 8,512 paths, and one more row and column gives 1,262,816. Physicists and chemists call paths in a lattice self-avoiding walks and use them as models of polymer chains, a molecule that cannot pass through itself.

The same gap separates the easy and hard questions about single routes:

• Shortest path: easy. Breadth-first search finds one in linear time when edges have no weights, and Dijkstra's algorithm when weights are nonnegative, thanks to the shortcut lemma of section 5.
• Longest path: hard. Deciding whether a graph has a path of at least a given length is NP-complete. A path through all n vertices has length n - 1, so the question includes the Hamiltonian path problem as a special case. In the strip the longest path from A to F has length 5 and passes through all six vertices; the zigzag A, B, C, D, E, F is one.
• Longest walk: meaningless. Walks may repeat edges, so any graph with an edge has walks of every length.

8. Trails, circuits and Euler

Trails belong to Euler. His 1736 solution of the Königsberg bridge problem asked for a walk that crosses every bridge exactly once: a trail through every edge of a multigraph. Such a trail is an Eulerian trail, and a closed one is an Eulerian circuit. Euler's condition, proved in full by Carl Hierholzer in a paper published in 1873, is about degrees. A connected graph has an Eulerian circuit exactly when every vertex has even degree, and an Eulerian trail that is not closed exactly when exactly two vertices have odd degree, in which case the trail must start at one of them and end at the other.

In the strip, B and E have degree 3 and every other vertex has even degree, so an Eulerian trail runs from B to E:

B, A, C, B, D, C, E, D, F, E        9 edges, each used once

It passes through B, C, D and E twice each, which is why "Eulerian path" is, strictly speaking, a misnomer. The guide to Eulerian paths and circuits covers Hierholzer's algorithm in detail. When a graph has more than two odd vertices, some edges must be walked twice, and the cheapest closed walk through every edge is the Chinese postman problem.

Veblen's theorem from section 5 is the other side of the same coin. An Eulerian circuit is a circuit through every edge, and splitting it at repeated vertices divides the edges into cycles that share no edge. Conversely, a connected graph whose edges divide into such cycles has all degrees even, and the cycles can be spliced together at shared vertices into one Eulerian circuit.

9. Cycles, girth and circumference

The strip has exactly 10 cycles: the four triangles, three cycles of length 4, two of length 5 and one of length 6.

length 3:  ABC, BCD, CDE, DEF
length 4:  ABDC, BDEC, CDFE
length 5:  ABDEC, BDFEC
length 6:  ABDFEC

Two numbers summarise the cycles of a graph. The girth is the length of a shortest cycle, here 3, and the circumference is the length of a longest cycle, here 6. A cycle through every vertex, like A, B, D, F, E, C, A, is a Hamiltonian cycle, so the strip is Hamiltonian. A graph with no cycle at all is a forest, and a connected one is a tree, in which there is exactly one path between any two vertices; the guide to trees develops that idea. The guide to cycles in graphs explains how to detect a cycle with depth-first search and how many independent cycles a graph has.

10. Directed walks and paths

In a directed graph every step must follow an arrow from its tail to its head. With that one change, all six definitions carry over: a directed walk, directed trail, directed path, closed directed walk, directed circuit and directed cycle. A few things behave differently:

• Cycles of length 2 exist. Two arrows u → v and v → u are different edges, so u, v, u is a directed cycle even in a graph without parallel edges.
• Reachability is one-way. A directed path from u to v says nothing about a path back. Vertices that can reach each other in both directions form a strongly connected component, and the guide to strongly connected components shows how to find them.
• No directed cycle means an order exists. A directed graph without directed cycles, a DAG, can always be listed so that every arrow points forward. That listing is a topological sort, and in a DAG even the longest path can be found in linear time.
• Ignoring the arrows gives a semi-walk or semi-path, which may step against an arrow. A directed graph is weakly connected when its vertices are joined by semi-paths.

The matrix trick of section 6 works unchanged for directed graphs: the entry in row u, column v of Ak counts the directed walks of length k from u to v.

11. Where each kind of route is used

Each of the six words names the right model for a different kind of real problem:

• Paths are routes for anything that should not loop: driving directions, packets across a network, a chain of introductions between two people. Every shortest-route problem is a path problem, by the shortcut lemma.
• Trails and circuits describe covering every street, pipe or wire once: snow ploughs, street sweepers and postal rounds. When some edges must be repeated, the problem becomes the Chinese postman problem of section 8.
• Walks appear wherever movement is random. A random walk moves to a random neighbour at each step. George Pólya proved in 1921 that a random walk on the grid of integer points returns to its start with certainty in one or two dimensions, but not in three. Google's original PageRank, described by Sergey Brin and Lawrence Page in 1998, ranks web pages by how often a random surfer following links visits them, and graph embedding methods such as DeepWalk learn from many short random walks.
• Cycles are usually the thing to find or forbid: a deadlock is a cycle of processes each waiting for the next, a circular import or a spreadsheet formula that refers to itself is a cycle of dependencies, and Kirchhoff's voltage law says that the voltages around every cycle of an electrical network add up to zero.
• Closed walks count structure: the diagonal of A3 counts triangles, which social network analysis uses to measure how often a person's friends know each other.

12. Common mistakes

13. Glossary

15. References

The definitions, theorems and attributions above come from these sources, listed in chronological order.

1. Euler, L. (1741). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8, 128 to 140. Presented in 1736.
2. Hierholzer, C. (1873). "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6, 30 to 32.
3. Veblen, O. (1912). "An Application of Modular Equations in Analysis Situs." Annals of Mathematics, second series, 14, 86 to 94.
4. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77, 453 to 465.
5. Pólya, G. (1921). "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz." Mathematische Annalen 84, 149 to 160.
6. Berge, C. (1958). Théorie des graphes et ses applications. Paris: Dunod.
7. Ore, O. (1962). Theory of Graphs. American Mathematical Society Colloquium Publications 38. Providence, RI: American Mathematical Society.
8. Harary, F. (1969). Graph Theory. Reading, MA: Addison-Wesley.
9. Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman.
10. Valiant, L. G. (1979). "The Complexity of Enumeration and Reliability Problems." SIAM Journal on Computing 8(3), 410 to 421.
11. Biggs, N. (1993). Algebraic Graph Theory, 2nd edition. Cambridge: Cambridge University Press.
12. Brin, S. and Page, L. (1998). "The Anatomy of a Large-Scale Hypertextual Web Search Engine." Computer Networks and ISDN Systems 30(1 to 7), 107 to 117.
13. West, D. B. (2001). Introduction to Graph Theory, 2nd edition. Upper Saddle River, NJ: Prentice Hall.
14. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
15. Chartrand, G. and Zhang, P. (2012). A First Course in Graph Theory. Mineola, NY: Dover.
16. Rosen, K. H. (2012). Discrete Mathematics and Its Applications, 7th edition. New York: McGraw-Hill.
17. Perozzi, B., Al-Rfou, R. and Skiena, S. (2014). "DeepWalk: Online Learning of Social Representations." Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 701 to 710.
18. Diestel, R. (2017). Graph Theory, 5th edition. Graduate Texts in Mathematics 173. Berlin: Springer.