Vorliegende Sprache |
ger |
Hinweise auf parallele Ausgaben |
369673719 Druckausg.: ‡Krumke, Sven O.: Graphentheoretische Konzepte und Algorithmen |
ISBN |
978-3-8348-1849-2 |
Name |
Krumke, Sven O. |
Noltemeier, Hartmut |
ANZEIGE DER KETTE |
Noltemeier, Hartmut |
T I T E L |
Graphentheoretische Konzepte und Algorithmen |
Auflage |
3. Aufl. 2012 |
Verlagsort |
Wiesbaden |
Verlag |
Vieweg+Teubner Verlag |
Erscheinungsjahr |
2012 |
2012 |
Umfang |
Online-Ressource (X, 431 S. 412 Abb, digital) |
Reihe |
Leitfäden der Informatik |
Notiz / Fußnoten |
Description based upon print version of record |
Weiterer Inhalt |
Vorwort; Vorwort zur zweiten Auflage; Vorwort zur dritten Auflage; Inhaltsverzeichnis; 1 Einleitung; 1.1 Routenplanung; 1.2 Frequenzplanung im Mobilfunk; 1.3 Museumswärter; 1.4 Das Königsberger Brückenproblem; 1.5 Schiebepuzzle; 1.6 Konzept des Buchs; 1.7 Ergänzungsmaterial undWebseite zum Buch; 2 Grundbegriffe; 2.1 Gerichtete Graphen; 2.2 Teilgraphen und Obergraphen; 2.3 Ungerichtete Graphen, symmetrische Hülle und Orientierungen; 2.4 Linegraphen; 2.5 Graphentheoretische Algorithmen; 2.6 Komplexität und NP-Vollständigkeit; 2.7 Approximations-Algorithmen; 2.8 Übungsaufgaben. 5.5 Übungsaufgaben6 Bäume, Wälder und Matroide; 6.1 Bäume und Wälder; 6.2 Minimale spannende Bäume; 6.3 Der Algorithmus von Kruskal; 6.4 Matroide und Unabhängigkeitssysteme; 6.5 Der Algorithmus von Prim; 6.6 Der Algorithmus von Fredman und Tarjan; Der Algorithmus von Bor˚uvka; 6.8 Spannende Bäume mit Gradbeschränkung; 6.9 Die MST-Heuristik für das Traveling Salesman Problem; 6.10 Wurzelbäume in gerichteten Graphen; 6.11 Übungsaufgaben; 7 Suchstrategien; 7.1 Tiefensuche (DFS); 7.2 Anwendungen von DFS; 7.3 Tiefensuche für ungerichtete Graphen; 7.4 Breitensuche (BFS). 7.5 Lexikographische Breitensuche (LEX-BFS)7.6 Übungsaufgaben; 8 Kürzeste Wege; 8.1 Grundlegende Eigenschaften kürzester Wege; 8.2 Bäume kürzester Wege; 8.3 Ein Grundgerüst zur Berechnung kürzester Wege; 8.4 Der Algorithmus von Dijkstra; 8.5 Der Algorithmus von Bellman und Ford; 8.6 Kreise negativer Länge; 8.7 Die Bellmanschen Gleichungen und kreisfreie Graphen; 8.8 Kürzeste Wege für alle Paare (APSP); 8.9 LängsteWege; 8.10 Übungsaufgaben; 9 Flüsse und Strömungen; 9.1 Flüsse und Schnitte; 9.2 Residualnetze und flussvergrößerndeWege; 9.3 Das Max-Flow-Min-Cut-Theorem. 9.4 Der Algorithmus von Ford und Fulkerson9.5 Der Algorithmus von Edmonds und Karp; 9.6 Der Algorithmus von Dinic; 9.7 Push-Relabel-Algorithmen; 9.8 Untere Kapazitätsschranken, b-Flüsse undStrömungen; 9.9 Flussdekomposition; 9.10 Kombinatorische Anwendungen des Max-Flow-Min-Cut-Theorems; 9.11 Kostenminimale Flüsse; 9.12 Maximale Schnitte; 9.13 Übungsaufgaben; 10 Matchings; 10.1 Matchings und die Tutte-Berge-Formel; 10.2 Alternierende und augmentierendeWege; 10.3 Matchings maximaler Kardinalität in bipartiten Graphen; 10.4 Perfekte Matchings in regulären bipartiten Graphen. 10.5 Perfekte Matchings mit minimalem Gewicht in bipartiten Graphen. 3 Wege, Kreise und Zusammenhang3.1 Wege; 3.2 Kreisfreie Graphen; 3.3 Zusammenhang; 3.4 Bipartite Graphen; 3.5 Der Satz von Euler; 3.6 Hamiltonsche Wege und Kreise; 3.7 Übungsaufgaben; 4 Färbungen und Überdeckungen; 4.1 Cliquen und unabhängige Mengen; 4.2 Färbungen; 4.3 Perfekte Graphen; 4.4 Chordale Graphen; 4.5 Ein einfacher Färbungsalgorithmus; 4.6 Listenfärbungen und Kantenfärbungen; 4.7 Überdeckungen; 4.8 Das p-Center Problem; 4.9 Übungsaufgaben; 5 Transitive Hülle und Irreduzible Kerne; 5.1 Transitive Hülle; 5.2 Der Tripelalgorithmus; 5.3 Der reduzierte Graph; 5.4 Irreduzible Kerne |
Titelhinweis |
Druckausg.: ‡Krumke, Sven O.: Graphentheoretische Konzepte und Algorithmen |
ISBN |
ISBN 978-3-8348-2264-2 |
Klassifikation |
UY |
COM014000 |
*05-01 |
68-01 |
05C85 |
68R10 |
68W05 |
90C35 |
511.5 |
004 |
QA75.5-76.95 |
SK 890 |
Kurzbeschreibung |
Einleitung -- Graphentheoretische Grundbegriffe -- Wege, Kreise, Zusammenhang -- Färbungen und Überdeckungen -- Transitive Hülle und irreduzible Kerne -- Bäume, Wälder, Matroide -- Suchstrategien -- Kürzeste Wege -- Flüsse und Strömungen -- Matchings -- Netzwerkdesign und Routing -- Planare Graphen -- Graphtransformationen -- Baumweite. |
2. Kurzbeschreibung |
Diese Einführung in graphentheoretische Grundbegriffe und Basissätze enthält neben klassischen Resultaten auch neueste Ergebnisse und Themen wie z. B. dynamische Flüsse, die in Lehrbüchern bislang unberücksichtigt blieben. Die Präsentation mit zahlreichen Bildern erleichtert das Verständnis und erhöht für den Leser die Motivation. Zahlreiche Aufgaben mit Lösungen helfen bei der Vertiefung und Einübung des Erlernten. Der Online-Service bietet Ihnen begleitende Materialien wie z. B. JAVA- Applets zum Buch. Der Inhalt Einleitung - Graphentheoretische Grundbegriffe - Wege, Kreise, Zusammenhang - Färbungen und Überdeckungen - Transitive Hülle und irreduzible Kerne - Bäume, Wälder, Matroide - Suchstrategien - Kürzeste Wege - Flüsse und Strömungen - Matchings - Netzwerkdesign und Routing - Planare Graphen - Graphtransformationen - Baumweite Die Zielgruppe Studierende der Mathematik, Informatik und der Wirtschaftswissenschaften an Fachhochschulen und Universitäten Die Autoren Prof. Dr. Sven Oliver Krumke lehrt und forscht an der Technischen Universität Kaiserslautern. Prof. Dr. Hartmut Noltemeier ist Emeritus der Universität Würzburg. |
1. Schlagwortkette |
Graphentheorie |
Netzwerkfluss |
Optimierungsproblem |
Approximationsalgorithmus |
Komplexitätstheorie |
1. Schlagwortkette ANZEIGE DER KETTE |
Graphentheorie -- Netzwerkfluss -- Optimierungsproblem -- Approximationsalgorithmus -- Komplexitätstheorie |
2. Schlagwortkette |
Graphentheorie |
Netzwerkfluss |
Optimierungsproblem |
Approximationsalgorithmus |
Komplexitätstheorie |
ANZEIGE DER KETTE |
Graphentheorie -- Netzwerkfluss -- Optimierungsproblem -- Approximationsalgorithmus -- Komplexitätstheorie |
SWB-Titel-Idn |
367686910 |
Signatur |
Springer E-Book |
Bemerkungen |
Elektronischer Volltext - Campuslizenz |
Elektronische Adresse |
$uhttp://dx.doi.org/10.1007/978-3-8348-2264-2 |
Internetseite / Link |
Volltext |
Siehe auch |
Inhaltsverzeichnis |
Siehe auch |
Inhaltstext |
Siehe auch |
Volltext |
Siehe auch |
Cover |
Siehe auch |
Inhaltstext |