Springe direkt zu Inhalt

Dana Kattham:

Starke und schwache Komponenten in gerichteten Graphen

Kurzbeschreibung

Stark zusammenhängende Komponenten (Strongly Connected Components, SCCs) sind ein zentrales Konzept in der Analyse gerichteter Graphen und spielen eine wichtige Rolle in zahlreichen Anwendungen der Informatik. Diese Arbeit behandelt zunächst formale Definitionen und grundlegende Begriffe der Graphentheorie und führt darauf aufbauend die Tiefensuche (Depth-First Search, DFS) als fundamentales Traversierungsverfahren ein. Auf dieser Grundlage werden starke Komponenten in gerichteten Graphen theoretisch eingeführt und ihre strukturellen Eigenschaften untersucht. Anschließend werden klassische Algorithmen zur Bestimmung von SCCs vorgestellt und analysiert, insbesondere DFS-basierte Verfahren. Ein weiterer Schwerpunkt liegt auf iterativen und speicheroptimierten Varianten dieser Algorithmen, die eine effiziente und skalierbare Berechnung stark zusammenhängender Komponenten auch in großen Graphen ermöglichen. Ergänzend wird die Breitensuche (Breadth-First Search, BFS) betrachtet und zur Bestimmung schwach zusammenhängender Komponenten in gerichteten Graphen herangezogen, indem diese als ungerichtete Graphen interpretiert werden. Abschließend werden die behandelten Verfahren hinsichtlich Laufzeit, Speicherbedarf und praktischer Implementierbarkeit verglichen und in einen anwendungsorientierten Kontext eingeordnet.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
06.02.2026