Ein Graph besteht aus Knoten und Kanten. Die Kanten beschreiben eine binäre "Beziehung" zwischen den Knoten. Viele Probleme aus verschiedenen Gebieten in und außerhalb der Informatik lassen sich als Graphenprobleme modellieren.

Graphenalgorithmen dienen in der Praxis zum Lösen von diskreten Problemen, bei denen Objekte in gewissen Beziehungen zueinander stehen.
Dabei geht man wie folgt vor:

• Modelliere das Problem als Graph; etwa: Objekte sind Knoten; zwei Knoten sind mit einer Kante verbunden, wenn die entsprechenden Objekte in Beziehung stehen;
• Formuliere die Zielfunktion des Problems als Eigenschaften des Graphenmodells;
• Löse das Problem mithilfe eines (effizienten) Graphenalgorithmus.

Ein Beispiel ist die Strukturanalyse des Web: Welche Webseiten sind "relevant"? Wie findet man "aufstrebende" Webgemeinden? etc. Zu diesem Zweck modelliert man das Web durch den Webgraphen mit Webseiten als Knoten und Hyperlinks zwischen den Webseiten als (gerichtete) Kanten. Webgemeinden lassen sich dann mit speziellen Strukturen in dem Webgraphen wie Cliquen oder Bi-Cliquen identifizieren und entdecken. Relevante Webseiten können z.B. durch die Verbindungsstruktur des Webgraphen definiert werden. (Die Antwort einer Suchmaschine ist in der Regel eine nach Relevanz zur Anfrage sortierte Linkliste; Googles PageRank verwendet hierfür den Webgraphen.)

Ein anderes Beispiel ist die Frequenzplanung im Mobilfunk: Zur Vermeidung von Interferenz (Signalstörung) werden zu nah beieinander liegenden Sendern verschiedene Frequenzen zugewiesen. Der zugehörige Interferenzgraph hat die Sender als Knoten. Seine Kanten verbinden Sender, die wegen Interferenz nicht die gleiche Frequenz zugeteilt bekommen dürfen. Gesucht ist eine Zerlegung der Knoten des Interferenzgraphen in (möglichst wenige) disjunkte Teilmengen, so dass keine Kante zwei Knoten derselben Teilmenge verbindet. (In der Graphensprache spricht man hier von einem "Färbungsproblem"). Ist eine solche Zerlegung gefunden, bekommen alle Sender einer Teilmenge die gleiche Frequenz, während diejenigen aus verschiedenen Teilmengen verschiedene Frequenzen zugeteilt werden.

Das Modul führt in die Grundlagen effizienter Graphenalgorithmen ein, behandelt grundlegende Probleme und Methoden wie vollständiges Durchsuchen von Graphen, kürzeste Wege, minimale Spannbäume, Maximalflüsse in Netzwerken, Matching- und Färbungsprobleme sowie Baumstrukturen in Graphen und Dekompositionen.