# Graph Algorithms

Graphs are a widely used model to describe structural relations. They are built of nodes, which are connected by edges (both directed or undirected). Some prominent examples for the application of graphs are:
• Routing
In this case nodes represent important places (junctions, cities), while edges correspond to roads connecting these places. A one-way road is represented by a directed edge.
• Communication networks (i.e. phone networks or internet)
Here, nodes are phones, modems, server, ISPs and more, edges are data lines connecting them.
• Gantt diagrams for sequence planning
Nodes correspond to phases of the projets, directed edges to dependencies between sections.
• Representation of hierarchical structures

Handling such models with means of algorithmic graph theory is an important area of mathematics and computer science. Some important algorithms of this area shall be presented and explained in the following, both by an interactive applet as well as by their pseudocode.

# Shortest Path Algorithms

One of the application of graphs in everyday life used most is the representation of infrastructure and communication networks. A map of the German highways, bus lines in a city or the flights offered by an airline; they all are depicted by a graph without us noticing it at all.

In this context it is obvious that the search of paths in the respective graphs is of great importance. Especially the "most benefical" path are very interesting. Thereby, "most benefical" can have diverse interpretations: Maybe it is the shortest of fastest way, eventually the cheapest or one that avoids the most speed checks.

Dijkstra's Algorithm Dijkstra's Algorithm computes the shortest path between two points whenever all adge weights are non-negative.

A* Algorithm The A* Algorithm works similarly to Dijkstra's Algorithm. However, it uses an additional heuristic for the distance between nodes and thus is normally faster.

Bellman-Ford Algorithm In contrast to the former two algorithms, the Bellman-Ford Algorithm also return shortest paths when negative edge weights are present.

Floyd-Warshall Algorithm The Floyd-Warshall Algorithm computes shortest paths between all pairs of points. It also works with negative edge weights.

# Spanning Tree Algorithms

The Minimal Spanning Tree Problem aims at connecting a set of nodes at minimal cost. Such problems are on hand if for example one wants to
• connect some server at minimal cost or
• supply some houses of a block with water by a pipeline network of minimal distance.

A Spanning Tree has to fulfill two characteristics. It has to be
• connected and
• free of circles.
One can then immediatly deduce that a spanning tree has to contain one edge less than the number of nodes. If he had less edges, he could not connect all nodes; if he had more, he had to contain a cycle.

If every edge has an associated weight – for example length or cost –, one can ask for a spanning tree of minimal total length or cost, i.e. for a Minimal Spanning Tree.

There are several algorithms that can compute minimal spanning trees, some of them discovered independently and even more than once. We restrict ourselves to two variants:

Prim's Algorithm Prim's Algorithm computes a minimal spanning tree on an undirected graph.

Kruskal's Algorithm Kruskal's Algorithm also computes a minimal spanning tree on an undirected graph. Furthermore, it returns a minimal spanning forest if the graph was unconnected.

# Matchings

The Matching Problem deals with the search of a relation of maximal size that connects two elements of different sets.

The Weighted Matching Problem is a special case that gives preferences to different relations in order to obtain the best allocation possible. It can be explained by the following example: The origin of the problem lies in the simple question of how to distribute presents among a certain number of children while obtaining optimal satisfaction.

Another typical problem is the so-called traditional "Marriage Problem", in which the subsets are occupied by women and men. The question arising is how to combine the couples in order to achieve a maximal satisfaction (low divorce rate).

This problem can be solved by the Hungarian Method (in the bipartite case) or the Blossom Algorithm (in the non-bipartite case, in the following presented for the unweighted problem).

Hopcroft-Karp Algorithm The Hopcroft-Karp Algorithm computes for two given sets with possible assignments a maximal relation.

Hungarian Method The Hungarian Method determines for two given sets with weighted assignments a maximal (with respect to the weihts) relation.

Blossom Algorithm The Blossom Algorithm computes a maximal matching in an arbitrary graph (in contrast to the Hopcroft-Karp algorithm which requires a bipartite graph).

# Flows

A very common problem in graphs and networks is the computation of flows. Be it the flow of goods, or information in a communication network, or flow in a pipeline network: the computation of flows in a network is a frequently modelled problem.

One often considers two variants:
• When requesting a maximal flow, the amount of goods to be transported on an edge is bounded by its capacity. One then wants to yield the maximal flow possible between source and sink, given the capacities on the edges.
• Alternatively, one might be interested in the cost-minimal flow of a given size. Besides edge capacities, the cost of transporting one unit of the good on an edge is given. In this case, the question is how to transport the required amount from source to sink while minimizing the transportation cost.

For both variants, there are many different algorithms. Two of them will be presented in the following.

Ford-Fulkerson Algorithm The Ford-Fulkerson Algorithm computes the maximal flow in a network.

Cycle-Cancelling Algorithm The Cycle-Cancelling Algorithm yields a maximal flow of minimal cost.

# Eulerian Paths and the Chinese Postman Problem

A classical problem of graph theory is the Eulerian Path Problem, which asks for paths or cycles that cover all arcs of a given graph.

The problem was first formulated by the following question:
The river Pregel divides the town Königsberg (Kaliningrad nowadays) in five parts, that are connected among themselves by seven bridges. Can one do a tour that passes each bridge exactly once?

This question can be interpreted and generalized as a graph theoretic problem (city parts as nodes, bridges as edges) and was thus solved by Leonhard Euler in 1736: Such a tour exists if and only if no or two nodes have odd degree.
If no nodes has odd degree, there is an Eulerian Cycle; if on the other hand two nodes have odd degree, only an Eulerian Path that starts and ends in different nodes is possible.

The aim of the related Chinese Postman Problem is to find a shortest path in a graph, such that this path uses each edge at least once and returns to the starting point.

The most prominent example for this problem is a postman that delivers mail in a part of his town. He has to visit each street once and he needs to return to the post office at the end, all while using as little time as possible. The problem's name originates exactly from the postman's problem and from the fact that it was first examined by a Chinese.
A similar example occurs for winter services: Each street has to be visited in order to remove snow, and each shift has to end at the depot where it started.

Hierholzer Algorithm The Hierholzer Algorithm computes an Eulerian Tour in a graph (if one exists).

Chinese Postman Problem The Chinese Postman Problem can be solved by combining the Matching Algorithms and the Hierholzer Algorithm presented above.

#### Research Unit M9

Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

#### Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

#### News

Jan 25th, 2019
Case Studies 2019: Preliminary Meeting on Wed, Feb 6th, at 16:00 in room MI 03.06.011.