Graphen und Algorithmen

Más información sobre el libro

Das Inhaltsverzeichnis umfasst verschiedene Themen im Bereich Graphen und algorithmische Graphenprobleme. Es beginnt mit einer Einführung in grundlegende Begriffe, Bäume und die Darstellung von Graphen im Computer, gefolgt von Konzepten wie Polynomialzeit und NP-Vollständigkeit. Es bietet auch Übungen und Lösungshinweise. Ein weiterer Abschnitt behandelt Euler- und Hamiltonkreise, einschließlich Kriterien für deren Existenz und Algorithmen zu deren Konstruktion. Das Durchsuchen von Graphen wird durch Tiefen- und Breitensuche sowie topologisches Sortieren vertieft, ergänzt durch Übungen und Lösungshinweise. Das Thema Minimalgerüste und der Greedy-Algorithmus wird behandelt, ebenso wie das Steinerbaumproblem. Kürzeste Wege in verschiedenen Graphenarten werden analysiert, einschließlich DAGS und gerichteter Graphen, mit Übungen und Lösungshinweisen. Das Maximalflussproblem wird durch Flüsse und Schnitte sowie Algorithmen wie Ford/Fulkerson und Dinitz erläutert. Unabhängige Knoten- und Kantenmengen sowie deren Zuordnungen, Überdeckungen und Färbungen werden ebenfalls behandelt. Ein Abschnitt zu Graphen und Hypergraphen mit Baumstruktur umfasst chordale Graphen und Hyperbäume. Schließlich wird der algorithmische Nutzen von Baumstrukturen und speziellen Graphenklassen thematisiert, gefolgt von ausgewählten Musterlösungen zu den Übungsaufgaben.