## 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 a_{ij} of the form: (1)
a_{ij}=1 if node i is an predecessor of node j (i.e., the arc starts
in i and terminated in j) and (2) a_{ij}=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**.

### Graphs

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.

Examples

- The
*node/arc incidence matrix***A**has element a_{ve}that can have three value: (1) a_{ve}=+1 if the link e start in node v. (2) a_{ve}=-1 if the link e ends in node v. (3) a_{ve}=0 otherwise. - Similarly, the
*arc/path incidence matrix***D**consists of elements d_{er}of the form: (1) d_{er}=1 if link e is part of route r or (2) d_{er}=0 otherwise. - The
*origin-destination/path incidence matrix***L**is composed of element l_{(od)r}with (1) l_{(od)r}=1 if path r lead from origin o to destination d and l_{(od)r}=0 otherwise.

Compare to adjacency matrix.

### Links

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.

### Nodes

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

**Sources**,**origins**, or**supply nodes**are nodes where the outflow exceeds the inflow.**Sinks**,**destinations**, or**demand nodes**are nodes where the inflow exceeds the outflow.**Transshipment (or transit) nodes**simply direct traffic throuh; their inflow always equals their outflow.

### Path

See route.

### 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.

- A
**star network**consists of a center node to which all other peripheral nodes are connected by one physical link. - In a
**tree network**each pair of nodes is connected by a unique route. - A
**mesh network**consists of nodes which are connected with at least two other nodes. In a fully connected mesh network there is a direct branch between any two nodes. - A
**bus network**has a common transmission line and all stations are connected to the single bus. - In
**ring networks**every node has a unique predecessor (or upstream node) as well as a unique successor (or downstream node). The transmission follows a predetermined direction.

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