Private Docent Dr. Hagen Bobzin

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.

Flows

link flows, route or path flows, multicommodity flows

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.

Max Flow/Min Cut Theorem

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.