Random flows: network flows and electrical flows through random media

Summary

ABSTRACT

This is a review of certain aspects of flows through random media. We discuss discrete media only, rather than continuous media, and we represent such media as graphical networks. We are interested in two particular types of flow – network flows and electrical flows – and both of these involve the passage of indestructible, uncreatable matter. Rather than considering the case when the constraints on the flows are deterministic, we suppose that these constraints are random variables; thus we consider network flows with random capacities and electrical networks with random resistances, and we think of these either as being “typical networks” (in the sense of operations research) or as being models for randomly–impure physical bodies. In all cases we are concerned with the asymptotic behaviour of large networks in the limit as their sizes approach infinity, and almost all of our results deal with trees, complete graphs, or subsections of crystalline lattices (such as the square lattice).

INTRODUCTION

There are many situations in which the idea of a “flow” is important, such as

1. – fluid passing through a system of pipes,

2. – electrons moving along the wires of an electrical circuit,

3. – information or rumours spreading through a community,

4. – disease infecting the members of a population.

In all these examples are present the ideas of both space and time. Each requires a medium (generally a set of points with interconnections) and a permeating quantity (such as fluid or disease). In any particular example of one of these four situations, there is a set of rules which govern the consequent flow, and such sets of rules vary a great deal in their styles and degrees of complexity.