Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2012 | Buch

Einleitung Kapitel lesen Erstes Kapitel lesen

Graphentheoretische Konzepte und Algorithmen

verfasst von: Sven Oliver Krumke, Hartmut Noltemeier

Verlag: Vieweg+Teubner Verlag

Buchreihe : Leitfäden der Informatik

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Das Buch enthält eine Einführung in graphentheoretische Grundbegriffe und Basissätze. Graphen werden als Modellierungswerkzeuge für verschiedene Anwendungen aus dem Bereich der Standortplanung, Logistik, Verkehrsplanung, des Scheduling und der Planung von Kommunikationsnetzen vorgestellt. Für die entstehenden graphentheoretischen Probleme werden effiziente Verfahren vorgestellt und rigoros analysiert. Für komplexitätstheoretisch "schwierige" Probleme enthält das Buch effiziente Näherungsverfahren, die schnell Lösungen mit beweisbarer Güte liefern.

Inhaltsverzeichnis

Frontmatter
1. Einleitung
Zusammenfassung
Graphentheoretische Konzepte und Algorithmen haben in vielen Bereichen des modernen Lebens Anwendungen. Wenn wir heute einen Routenplaner oder das Mobiltelefon benutzen, so stecken in der Mathematik im Hintergrund meist (auch) Graphen und effiziente Verfahren, die graphentheoretische Probleme lösen.
Sven Oliver Krumke, Hartmut Noltemeier
2. Grundbegriffe
Sven Oliver Krumke, Hartmut Noltemeier
3. Wege, Kreise und Zusammenhang
Zusammenfassung
In Kapitel 1 haben wir im Zusammenhang mit der Routenplanung und dem Königsberger Brückenproblem bereits von Wegen bzw. Kreisen in einem Graphen gesprochen. In diesem Kapitel werden wir diese Begriffe exakt fassen und wichtige Eigenschaften herleiten. Unter anderem kommen wir dabei auf das Königsberger Brückenproblem zurück und beweisen – wie angekündigt – den Satz von Euler (in verschiedenen Variationen), der ein notwendiges und hinreichendes Kriterium für die Existenz von Eulerschen Kreisen in Graphen liefert.
Sven Oliver Krumke, Hartmut Noltemeier
4. Färbungen und Überdeckungen
Zusammenfassung
In diesem Kapitel betrachten wir, sofern nicht explizit angegeben, ungerichtete einfache endliche Graphen G = (V, E) mit |V| = n und |E| = m.
Sven Oliver Krumke, Hartmut Noltemeier
5. Transitive Hülle und Irreduzible Kerne
Zusammenfassung
Das Problem 2-SAT besteht aus der Einschränkung des aussagenlogischen 2-SAT Erfüllbarkeitsproblems SAT (vgl. Abschnitt 2.6) auf diejenigen Instanzen, in denen jede Klausel genau zwei Literale enthält.
Sven Oliver Krumke, Hartmut Noltemeier
6. Bäume, Wälder und Matroide
Sven Oliver Krumke, Hartmut Noltemeier
7. Suchstrategien
Zusammenfassung
In diesem Abschnitt beschäftigen wir uns mit der sogenannten Tiefensuche DFS (depth first search), einem effizienten Verfahren, um strukturelle Informationen über einen Graphen, etwa über seine Zusammenhangskomponenten, zu gewinnen.
Sven Oliver Krumke, Hartmut Noltemeier
8. Kürzeste Wege
Zusammenfassung
In der Einleitung haben wir ein kürzeste-Wege-Problem aus dem Bereich der Routenplanung kennengelernt.
Sven Oliver Krumke, Hartmut Noltemeier
9. Flüsse und Strömungen
Zusammenfassung
Strömungen und Flüsse sind wichtige Werkzeuge zur Modellierung vieler Optimierungsprobleme. Informell besteht das „Maximalfluss-Problem“ darin, in einem Netz mit Kapazitäten auf den Pfeilen so viel Fluss wie möglich von einer ausgezeichneten Quelle s zu einer ausgezeichneten Quelle t zu schicken. Dabei dürfen die Kapazitäten nicht überschritten werden.
Sven Oliver Krumke, Hartmut Noltemeier
10. Matchings
Zusammenfassung
Wir haben Matchings bereits in Abschnitt 9.10 (Heiratssatz, Satz von Kőnig) kennengelernt.
Sven Oliver Krumke, Hartmut Noltemeier
11. Netzwerkdesign und Routing
Zusammenfassung
Im Vernetzungs-Problem aus Abschnitt 6.1 sollten alle Orte miteinander verbunden werden. Was passiert, wenn wir nur eine Teilmenge der Orte verbinden müssen?
Sven Oliver Krumke, Hartmut Noltemeier
12. Planare Graphen
Zusammenfassung
Graphen sind im Kern durch Inzidenzbeziehungen von zwei disjunkten Objektmengen (Eckenmenge und Pfeil- bzw. Kantenmenge) definiert. Die inhaltliche Interpretation dieser Objektmengen wird in vielfältigen Anwendungen problemspezifisch festgelegt.
Sven Oliver Krumke, Hartmut Noltemeier
13. Graphtransformationen
Zusammenfassung
Den Begriff des Isomorphismus zwischen zwei Graphen hatten wir bereits am Anfang eingeführt (Definition 2.4).
Sven Oliver Krumke, Hartmut Noltemeier
14. Baumweite
Zusammenfassung
In diesem Kapitel betrachten wir wieder, sofern nicht explizit angegeben, ungerichtete einfache endliche Graphen G = (V, E) mit |V| = n und |E| = m.
Sven Oliver Krumke, Hartmut Noltemeier
15. Anhang
Sven Oliver Krumke, Hartmut Noltemeier
Backmatter
Metadaten
Titel
Graphentheoretische Konzepte und Algorithmen
verfasst von
Sven Oliver Krumke
Hartmut Noltemeier
Copyright-Jahr
2012
Verlag
Vieweg+Teubner Verlag
Electronic ISBN
978-3-8348-2264-2
Print ISBN
978-3-8348-1849-2
DOI
https://doi.org/10.1007/978-3-8348-2264-2