# 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

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

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.

**Spanning Tree**has to fulfill two characteristics. It has to be- connected and
- free of circles.

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

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

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.

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

A classical problem of graph theory is the

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

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.

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