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
Kongresse
Themenseiten
Künstliche Intelligenz Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Veranstaltungskalender Awards MyNewsletter Firmensuche
Kunden Login
Über Einzelzugang informieren
Über Unternehmenszugang informieren
Referenzkunden
Zukunftswerkstatt Sales Excellence 2025 | 08. Mai 2025

KI als Booster im Vertrieb

Lernen Sie von Digital-Experten, wie der gezielte Einsatz von KI-Unterstützung Ihrem Unternehmen in vielen Bereichen hilft, im Vertrieb einen Schritt voraus zu sein. Jetzt wieder live vor Ort teilnehmen in Frankfurt am Main!
Erweiterte Suche
Anmelden
nach oben

2025 | Buch

Kapitel lesen Erstes Kapitel lesen

Graphentheorie

Eine elementare Einführung in Begriffe, Konzepte, Probleme und Algorithmen

verfasst von: Jan Fricke, Theo Overhagen

Verlag: Springer Berlin Heidelberg

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

Inhaltsverzeichnis
insite
SUCHEN

Über dieses Buch

Dieses kompakte Lehrbuch führt in die grundlegenden Problemstellungen, Begriffe und Konzepte der Graphentheorie ein und liefert einen entsprechenden Überblick: In den ersten beiden Kapiteln werden die grundlegenden Begriffe geklärt – alle anderen Kapitel behandeln darauf aufbauend und weitgehend unabhängig voneinander jeweils einen wichtigen Problemkreis. Die Resultate und Lösungsalgorithmen werden dabei jeweils durch viele Beispiele, Grafiken und Übungsaufgaben veranschaulicht. Das Buch legt außerdem großen Wert auf die Erläuterung der Zusammenhänge; bis auf wenige Ausnahmen werden alle Resultate bewiesen.

Zum Verständnis des Inhalts sind nur mathematische Grundkenntnisse nötig. Das Buch ist daher für Anfängervorlesungen in den ersten Semestern des Mathematikstudiums und insbesondere für Lehramtsstudierende gut geeignet. Es kann aber beispielsweise auch für Seminare, AGs oder Schülerprojekte verwendet werden.

Inhaltsverzeichnis

Frontmatter
Kapitel 1. Grundbegriffe
Zusammenfassung
Graphen sind mathematische Strukturen bestehend aus Ecken und Kanten, bei denen die Kanten irgendwelche Beziehungen zwischen den Ecken repräsentieren. In diesem Kapitel sind die grundlegenden Definitionen mit Beispielen zu finden, um mit Graphen zu arbeiten. Insbesondere wird gezeigt, wie man Graphen durch Matrizen beschreiben kann. Graphen, die sich im Wesentlichen nur durch ihre Darstellung unterscheiden, werden als isomorph bezeichnet. Wichtige Klassen von Graphen werden vorgestellt: vollständige Graphen, Kreisgraphen, bipartite Graphen und viele andere mehr.
Jan Fricke, Theo Overhagen
Kapitel 2. Bäume
Zusammenfassung
Bäume sind kreislose zusammenhängende Graphen. In gewisser Weise können sie als Grundbausteine der Graphen aufgefasst werden. In diesem Kapitel werden die Grundlagen über den Zusammenhang in Graphen gelegt, sowie wichtige Eigenschaften von Bäumen gezeigt.
Jan Fricke, Theo Overhagen
Kapitel 3. Eulersche und Hamiltonsche Graphen
Zusammenfassung
Ein Graph ist ein Eulerscher Graph, wenn es einen geschlossenen Kantenzug gibt, der jede Kante genau einmal enthält. Er ist ein Hamiltonscher Graph, wenn es einen Kreis gibt, der jede Ecke genau einmal enthält. Es ist sehr einfach zu prüfen, ob ein Graph Eulersch ist, und in diesem Fall lässt sich eine Eulersche Tour sehr leicht konstruieren. Dagegen gibt es für Hamiltonsch zwar ein paar einfache Kriterien und Verfahren, aber kein effizientes Verfahren, das für jeden Graphen funktioniert.
Jan Fricke, Theo Overhagen
Kapitel 4. Kürzeste und längste Wege
Zusammenfassung
Ein wichtiges graphentheoretisches Problem ist die Bestimmung eines kürzesten, schnellsten oder sparsamsten Weges zwischen zwei Punkten. Dazu wird jeder Kante ein Wert zugeordnet, und man sucht einen Weg mit minimaler Summe dieser Werte. Der bekannteste Lösungsalgorithmus ist der Algorithmus von Dijkstra, der allerdings bei negativen Werten versagen kann. Der Floyd-Warshall-Algorithmus kann damit umgehen, ist aber deutlich aufwändiger. Das in gewisser Weise gegenteilige Probleme ist das Finden eines längsten Weges in einem azyklischen Graphen. Dieses Problem entsteht zum Beispiel in Ablaufplänen, wenn einzelne Schritte teilweise gleichzeitig zu und teilweise erst nach anderen Schritten ausgeführt werden können. Die Gesamtzeit des Projektes ergibt sich dann durch die maximale Zeit, die aufeinanderfolgende Schritte brauchen.
Jan Fricke, Theo Overhagen
Kapitel 5. Planare Graphen
Zusammenfassung
Ein ebener Graph ist ein Graph, dessen Ecken Punkte in der Ebene sind, und alle Kanten kreuzungsfreie Verbindungslinien in dieser Ebene zwischen den entsprechenden Punkten sind. Ebene Graphen können als Landkarte aufgefasst werden, die Eulersche Polyederformel liefert einen Zusammenhang zwischen den Anzahlen der Ecken, Kanten und Länder. Außerdem lässt sich einem ebenen Graphen ein dualer Graph zuordnen, beim dem die Rollen der Ecken und Länder vertauscht werden. Aus verschiedenen Gründen ist es interessant zu wissen, ob ein gegebener Graph als ebener Graph dargestellt werden kann. Solche Graphen heißen planar. Sie können durch den Satz von Kuratowski charakterisiert werden.
Jan Fricke, Theo Overhagen
Kapitel 6. Färbungen
Zusammenfassung
Auf Landkarten bekommen benachbarte Länder verschiedene Farben. Dafür könnte man jedem Land seine eigene Farbe geben, normalerweise möchte man aber so wenig Farben wie möglich verwenden. Allgemeiner kann man sich also die Frage stellen, wie viele Farben man mindestens benötigt, um die Ecken, Kanten oder Länder eines Graphen bzw. einer Landkarte so zu färben, dass benachbarte Ecken, Kanten bzw. Länder verschiedene Farben bekommen. Für diese Anzahlen gibt es einige Abschätzungen, für spezielle Fälle einfache Algorithmen zum Bestimmung einer optimalen Färbung. Die Ergebnisse können für die Lösung von Zuordnungsproblemen, Turnierplanungen u.ä. verwendet werden.
Jan Fricke, Theo Overhagen
Kapitel 7. Matchings
Zusammenfassung
Ein Matching in einem Graphen ist eine Teilmenge der Kanten, die keine Ecke mehrfach enthält. Typische Probleme, die zu Matchings führen, sind Zuordnungsprobleme: Teams sollen in einer Turnierrunde gepaart werden, Veranstaltungen sollen Räume zugeordnet werden. Meistens sucht man dabei möglichst große Matchings. Das kann in beliebigen Graphen recht aufwändig werden, es gibt aber gute Kriterien, die bei der Suche nach maximalen Matchings helfen. Für bipartite Graphen gibt es einen sehr effizienten Algorithmus (ungarische Methode) und ein sehr schönes Kriterium (Heiratssatz von Hall). Außerdem kann man Matchings als unabhängige Kantenmengen auffassen. Das geht analog für Ecken, und man kann jeweils umgekehrt auch Überdeckungen betrachten. Diese vier Typen von Mengen haben interessante Verbindungen, die im letzten Abschnitt des Kapitels erklärt werden.
Jan Fricke, Theo Overhagen
Kapitel 8. Netzwerke
Zusammenfassung
In Netzwerken wird ein Gut über Verbindungen zwischen verschiedenen Orten transportiert. Das kann zum Beispiel Wasser oder Strom in Leitungen sein, aber auch Verkehrsströme auf Straßen oder Schienen. Wir wenden uns zunächst dem Problem zu, für gegebene Kapazitäten der Verbindungen die maximale Kapazität zwischen zwei Punkten des Netzwerkes zu bestimmen. Das führt uns direkt zum Problem der Ausfallsicherheit: Wie viele Verbindungen bzw. Verteilerstellen dürfen maximal ausfallen, so dass immer noch alle Orte durch das Netzwerk verbunden sind?
Jan Fricke, Theo Overhagen
Kapitel 9. Labyrinthe
Zusammenfassung
Auch Labyrinthe können als Graphen modelliert werden. Allerdings hat man normalerweise keine Informationen über das komplette Labyrinth, man weiß oft noch nicht einmal, an welcher Kreuzung der Gang endet, den man gerade betritt. Labyrinth-Algorithmen müssen also mit den wenigen Informationen auskommen, die man zum entsprechenden Zeitpunkt direkt erkennen kann. Oftmals wird hier die Linke-Hand-Regel benutzt. Diese garantiert aber nur, dass man zum Anfangspunkt zurück findet, während man einen im Labyrinth versteckten Schatz oder einen Ausgang eventuell nicht erreicht. Am bekanntesten sind die Algorithmen von Tarry und Trémaux, die als älteste funktionierende Absuchalgorithmen gelten.
Jan Fricke, Theo Overhagen
Backmatter
Metadaten
Titel
Graphentheorie
verfasst von
Jan Fricke
Theo Overhagen
Copyright-Jahr
2025
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-70247-5
Print ISBN
978-3-662-70246-8
DOI
https://doi.org/10.1007/978-3-662-70247-5

Premium Partner

    Bildnachweise