The lecture will be held in English, unless there is no demand for it.

Graphen und Netzwerke modellieren in vielfältiger Art Beziehungen in der Informatik und außerhalb, zum Beispiel soziale Netze, Verkehrsnetze, und viele andere. Wir behandeln algorithmischen Fragen, die in diesem Zusammenhang auftreten:

• Analyse von Netzen, zum Beispiel: Gibt es besonders wichtige oder zentrale Knoten?  Wie verwundbar ist das Netzwerk gegenüber Störungen? Welche Eigenschaften unterscheiden zum Beispiel ein soziales Netzwerk von einem Straßennetz?
• Optimierungsprobleme auf Graphen, zum Beispiel kürzeste Wege, Durchsuchen von Graphen.
• Graphen als Hilfsmittel zur Visualisierung: Zeichnen von Graphen (Planarität, Vermeiden von Kreuzungen, gutes Layout)

Zielgruppe

Informatiker und interessierte Mathematiker im Masterstudium. MSc Data Science

Empfohlene Vorkennntnisse

"Höhere Algorithmik" oder eine andere Vorlesung ähnlichen Inhalts. Familiarity with elementary data structure such as search trees, linked lists, etc., and concepts such as asymptotic analysis of algorithms, polynomial time and NP-hardness.

Literature

I will not use a particular source but combine the material from several sources. One book that I am consulting is

• Graphentheoretische Konzepte und Algorithmen, S. O. Krumke und H. Noltemeier, Teubner, 2005.

Planned topics (see the syllabus for actual topics)

• Graph representations
• bipartite graphs
• planar graphs; plane graphs; dual graphs; straight-line drawing; maps; circle-packing representation
• spanning trees
• Euler tours
  • corollary about orientations
  • non-crossing Euler tours
  • Euler tours and trees
• Hamilton tours
• Graph coloring; independent sets; cliques
• Flows
• minimum-cost flows. shortest augmenting path algorithm
• Matchings, blossom algorithm.
• Planarity
• 2-connected components; blocks
• depth-first search; s-t-numbering
• arboricity; denseness; graph orientation
• tree-width
• planar graph separators
• measures about graphs, centrality, (Wiener index)

not treated:

• Further examples dynamic programming
  • number of matchings
  • coloring
  • traveling salesperson problem
• edge colorings of bipartite graphs
• edge coloring of regular bipartite graphs
• inclusion-exclusion techniques
• bipolar orientations
• convex bipartite matching
• Hamilton tours in cubic graphs
• prices in the transportation problem
• models for random graphs, preferential attachment