Graph Theory

Site still under construction ...
Please be aware that introductory books on graph theory or operations research give more precise definitions of the bits and pieces of graph theory, cf., e.g., Hiller, Lieberman (1995).

Adjacency Matrix

The adjacency matrix of a network with n nodes and no parallel arcs is an n×n matrix A having element aij of the form: (1) aij=1 if node i is an predecessor of node j (i.e., the arc starts in i and terminated in j) and (2) aij=0 otherwise.
Compare to incidence matrix.

Conservation of Flows

The flow conservation is one of the most important rules to be satisfied by a flow on a network. It requires that no flow unit entering the network or generated at a source of the network is lost within the network. It either leaves the network at some sink or is attracted by some destination node. Regarding transshipment nodes, which neither attract nor generate flow units, we require that the sum of units entering that node equals the sum of units leaving it. This is equivalent to Kirchhoff 's (Current) Law.


link flows, route or path flows, multicommodity flows


A graph consists of two sets, namely a set of nodes and a set of links that connect pairs of nodes. If all links are directed (with one node as origin or tail and the other node as destination or head), the graph is called a directed graph or digraph.

Incidence Matrices

Incidence matrices decribe how elements of a network (e.g., nodes and links) are related to each other.

Compare to adjacency matrix.


Links (lines, edges, branches) join pairs of nodes in a network so that flows of some type can take place. The term arcs usually denotes directed links. In most economic cases link are able to serve a maximum number of flow units per unit of time. This capacity of a link needs to be redefined when the quality of services changes with the density of traffic.

Max Flow/Min Cut Theorem


The junction points in a network are called nodes (or vertices). Pairs of point are connected by links along which flows of some type take place. Three classes of nodes are important


See route.


A route or path signifies a sequence of consecutive links. A closed path or cycle terminates at its initial node and elementary routes traverse no node and, therefore, no link twice.

Topology of Networks

Many features of networks depend on their topological structure. The following list includes the most important network topologies, where possible advantages or disadvantages are at hand without going into further details.

Of course, all of the above topologies can be combined in more or less hierarchical structures.