Graphs and Networks

Graphs

This is the web coverage of my lectures I give for a University of Cooperative Education (Berufsakademie Rhein-Main) in the field of graph theory. This is not a purely mathematical introduction, which would not be appropriate for a this „Cooperative Education“. Here we have a focus on application, which is for example finding paths in networks, finding shortest paths of the maximum flow in such a network.


Examples

Here you see quite a few simple examples of graphs. The first observation is that a graph can have directed or undireced edges. In directed graphs edges have an orientation, the connecting edge points from one vertex to another, one can compare this with a one-way road. In an undirected graphs edges have no direction and can be passes in both ways. These distinctions will be important when we search paths through a graph from a starting point (start vertex) to an end point (end vertex).

Complete graphs

A graph is called complete iff E = VxV, i.e. if it has all possible edges. Now given a graph with n vertices which is not a complete graph the complement graphis defined to have all vertices which are missing to make the given graph complete Other special graphs are circular graphs and *whell shaped graphs"



Literature

  1. V. Turau: „Algorithmische Graphentheorie“, Oldenbourg Verlag
  2. Krumke / Noltemeier „Graphentheoretische Konzepte und Algorithmen“, Teubner Verlag