Advertisement
Published in:
2016 | OriginalPaper | Chapter
9. Optimale Bäume und Wege
Authors : Jens Vygen, Stefan Hougardy
Published in: Algorithmische Mathematik
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Zusammenfassung
In der Kombinatorischen Optimierung sucht man in einer endlichen Menge von Objekten mit einer kombinatorischen Struktur ein optimales Element. Die Objekte (d. h., die zulässigen Lösungen) können meist als Teilmengen einer endlichen Grundmenge U repräsentiert werden. Oft ist U die Kantenmenge eines Graphen. Die Objekte können dann z. B. s-t-Wege (für gegebene Knoten s und t) oder aufspannende Bäume sein; diese beiden Fälle werden wir gleich betrachten. Hat man eine Gewichtsfunktion \(c\colon U\to{\mathbb{R}}\), so heißt eine zulässige Lösung \(X\subseteq U\) optimal, wenn ihr Gewicht (man sagt auch: ihre Kosten) \(c(X):=\sum_{u\in X}c(u)\) minimal ist.
Die in Kap. 6 vorgestellte Klasse
Graph (Programm 6.29) ist auch für gewichtete Graphen ausgelegt. Die Funktion add_edge hat ein optionales drittes Argument, mit dem das Kantengewicht angegeben werden kann.Sei G ein Graph mit Kantengewichten \(c\colon E(G)\to{\mathbb{R}}\). Für einen Teilgraphen H von G bezeichnen wir mit \(c(E(H))=\sum_{e\in E(H)}c(e)\) das Gewicht von H; manchmal spricht man auch von Kosten oder Länge.