A graph comprises of nodes and edges. The edges describe the binary “relation” between the nodes. Many problems from different fields inside and outside computer science can be modeled as graph problems.

Graph algorithms serve for solving discrete problems in the practice, where objects are interrelated with each other.
The following procedure is applied here:

• Model the problem as graph, for instance: objects are nodes; two nodes are connected with an edge if the objects are interrelated;
• Determine the objective function of the problem as feature of the graph model;
• Solve the problem with an (efficient) graph algorithm.

One example is the structure analysis of the web: Which websites are „relevant“? How can “rising” web communities be found? etc. For this purpose, the web is modeled by web graphs with websites as nodes and hyperlinks between the websites as (directed) edges. Web communities can be identified and detected with special structures in web graphs, such as cliques or bi-cliques. Relevant websites can be defined, e.g. via the interconnection structures of the web graph. (The answer of a search engine is usually a link list sorted by relevance related to the query; Googles PageRank uses web graphs for this.)

Another example is frequency planning in mobile communications: To avoid interferences (signal disturbances), different frequencies are allocated to transmitters located too close to each other. The related interference graph has the transmitters as nodes. Its edges connect transmitters that must not get the same frequency because of interferences. Demanded is a decomposition of the interference graph’s nodes into (as few as possible) disjunctive partial quantities so that no edge links two nodes belonging to the same partial quantity. (In graph language this is referred to as “coloring problem”). Where such decomposition was found, all transmitters of one partial quantity get the same frequency while those from different partial quantities are allocated to different frequencies.

The module introduces the basics of efficient graph algorithms, deals with basic problems and methods like complete screening of graphs, shortest paths, minimum spanning trees, maximum flows in networks, matching and coloring problems and tree structures in graphs and decompositions.