4.2 Methods for Solving Flow Problems


  • In small flow networks, it may be possible to determine the maximum flow.
  • Remember that flow networks show the capacity of each edge. The maximum flow for an edge is often limited by the capacity of other edges. For example, if a pipe capable of carrying 100L/h is attached to one only capable of 50L/h, the maximum flow through the 100L/h pipe will be limited to 50L/h.


Picture 1
Read More »4.2 Methods for Solving Flow Problems

4.1 Introduction to Flow Problems

Flow Problems and Capacity

  • Many networks rely on the transport of fluids, people, objects or other quantities between different locations. Generally, the medium that is taken from one location to another (the pipe, road, etc.) is capable of transporting a certain number or amount per unit of time. This is known as the capacity.
  • Flow problems involves analysing movement through networks made up of a number of vertices connected via edges each with their own capacity.
  • In Further Maths, we will generally analyse flow problems involving digraphs.
Read More »4.1 Introduction to Flow Problems

1.3 Introduction to Network Matrices

Network Matrices

  • Matrices provide an alternative means to model networks. Using matrices also allows for more systemic methods for numerical analysis of networks.
  • A matrix is similar in form to a table, with a number of elements arranged into rows and columns. The vertices are listed along the rows and columns of the matrix. Each element is representative of the connection between the vertices that it’s corresponding row and column represent.
  • Each element indicates the number of edges which directly connect the vertex corresponding to the row to the vertex corresponding to the column.
  • If the graph is not a digraph, the matrix will be symmetric.

Note: network matrices are often known as adjacency matrices

Read More »1.3 Introduction to Network Matrices

1.1 Basics of Network Graphs

Network Graphs

  • A network graph shows the connections between multiple individuals or locations.
  • It consists of a number of dots, known as vertices (singular: vertex), each representing an individual or location, connected by lines, known as edges.
  • If two vertices are connected by an edge, this indicates the two individuals or locations the vertices represent are directly connected.
  • Examples of situations which can be modelled by network graphs include communication networks (showing which individuals can communicate with each other) and transportation networks (showing which towns are connected via roads, train tracks, etc).

Note: vertices are sometimes known as nodes.

Read More »1.1 Basics of Network Graphs