Graph AlgorithmsGraphs 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:
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
|Dijkstra's Algorithm computes the shortest path between two points whenever all adge weights are non-negative.|
|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.|
|In contrast to the former two algorithms, the Bellman-Ford Algorithm also return shortest paths when negative edge weights are present.|
|The Floyd-Warshall Algorithm computes shortest paths between all pairs of points. It also works with negative edge weights.|
- connect some server at minimal cost or
- supply some houses of a block with water by a pipeline network of minimal distance.
- connected and
- free of circles.
|Prim's Algorithm computes a minimal spanning tree on an undirected graph.|
|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 Hopcroft-Karp Algorithm computes for two given sets with possible assignments a maximal relation.|
|The Hungarian Method determines for two given sets with weighted assignments a maximal (with respect to the weihts) relation.|
|The Blossom Algorithm computes a maximal matching in an arbitrary graph (in contrast to the Hopcroft-Karp algorithm which requires a bipartite graph).|
- 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.
|The Ford-Fulkerson Algorithm computes the maximal flow in a network.|
|The Cycle-Cancelling Algorithm yields a maximal flow of minimal cost.|
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.
|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.|