Benutzer:DixMartin/Graphalgorithmen

Die Algorithmische Graphentheorie^[1] ist ein Teilgebiet der Graphentheorie. Gegenstand der Algorithmischen Mathematik und speziell der algorithmischen Graphentheorie ist die Konstruktion und Analyse effzienter Algorithmen zur Lösung mathematischer Problemstellungen mit Hilfe des Computers. Sie ist damit im Bereich der Angewandten Mathematik anzusiedeln.^[2] Betrachtungsgegenstand der Graphentheorie sind Graphen (Mengen von Knoten und Kanten), deren Eigenschaften und ihre Beziehungen zueinander.

Graphen sind mathematische Modelle für netzartige Strukturen in Natur und Technik (wie soziale Strukturen, Straßennetze, Verwandtschaftsbeziehungen, Computernetze, elektrische Schaltungen, Versorgungsnetze oder chemische Moleküle). In der Graphentheorie untersucht man lediglich die abstrakte Netzstruktur an sich. Die Art, Lage und Beschaffenheit der Knoten und Kanten bleibt unberücksichtigt. Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung graphentheoretischer Probleme oft auf Algorithmen basiert, ist die Graphentheorie auch in der Informatik, insbesondere der Komplexitätstheorie, von großer Bedeutung. Insbesondere lassen sich viele Aufgaben der kombinatorischen Optimierung in der Sprache der Graphentheorie formulieren und umgekehrt graphentheoretische Probleme als lineare ganzzahlige Optimierungsprobleme modellieren.^[3] Randomisierte Graph-Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und oft effizienter als deterministische Algorithmen.^[4]

Einige Grapheneigenschaften sind relativ schnell algorithmisch bestimmbar, etwa wenn der Aufwand höchstens mit dem Quadrat der Größe der Graphen wächst. Andere Eigenschaften praktisch angewandter Graphen sind innerhalb der Lebensdauer heutiger Computer nicht exakt zu bestimmen. Allerdings kann in diesen Fällen der Einsatz von heuristischen Verfahren zu sinnvollen Näherungslösungen führen.

Graphenalgorithmen stehen in Matlab seit dem Rel. 2015b zur Verfügung:^[5] bfsearch, dfsearch, maxflow, conncomp, minspantree, toposort, isdag, transclosure, transreduction, shortestpath, shortestpathtree, distances.

Algorithmen

Im folgenden werden Algorithmen zu Problemen der Graphentheorie, also zur Bestimmung von Grapheneigenschaften aufgeführt.

Traversierung / Eumerierung / Durchlaufbarkeit von Graphen

Häufig muss ein Graph durchmustert werden. Populäre Graphentraversierungsmethoden sind die Tiefensuche und die Breitensuche. Beide Suchverfahren lassen sich auf den folgenden Algorithmus zurückführen, der alle von einem Startknoten erreichbaren Knoten durchsucht.^[6]

Kürzesteste Wege-Suche

Man unterscheidet verschiedene Varianten des Kürzeste-Wege-Problems:

Einzelpaar-kürzeste-Wege-Problem: Für ein Knotenpaar st ein kürzester Weg gesucht.
Einzelquelle-kürzeste-Wege-Problem: Für einen Knoten sind die kürzesten Wege zu allen erreichbaren Knoten gesucht.
Alle-Paare-kürzeste-Wege-Problem: Für jedes Knotenpaar ist ein kürzester v-w-Weg gesucht.^[7]

Algorithmen hierzu sind:

Eulerkreisproblem / Briefträgerproblem

Das Königsberger Brückenproblem ist das bekanneste Beispiel, dass nach der Existenz eines Eulerkreises fragt. Beim Briefträgerproblem wird nach einem kürzesten Zyklus gefragt, der alle Kanten mindestens einmal durchläuft.

Problem des Handlungsreisenden

Minimale Spannbaum-Suche

Matching-Algorithmen

Ein Matching-Problem liegt immer dann vor, wenn man irgendwelche Objekte in eindeutiger Weise irgendwelchen anderen Objekten zuordnen möchte, wobei nur bestimmte Zuordnungen erlaubt sind. ^[8]

Maximaler Fluss

Maximaler-Fluss-Algorithmen beantworten die folgenden Fragen:

Ist es möglich, alle Bandbreiten vollständig auszuschöpfen?
Falls nein, was ist die maximal erreichbare Bandbreite?
Wie sollten die Daten geroutet werden? ^[9]

Ein Anwendungsbereich ist die Elektronik. Dort entspricht der maximale Fluss den Kirchhoffschen Regeln.

Sonstige

Algorithmus von Hopcroft und Tarjan zur Bestimmung der Planarität
Kernighan-Lin-Algorithmus zum Partitionieren
Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten
Algorithmus von Walker -zum Zeichnen von Bäumen

Einzelnachweise

↑ Läuchli: Algorithmische Graphentheorie (= Programm Praxis Ser). Springer Basel AG, Basel 1991, ISBN 978-3-7643-2663-0.
↑ Helmut Harbrecht, Michael Multerer: Algorithmische Mathematik: Graphen, Numerik und Probabilistik. 1. Aufl. 2022. Springer Berlin Heidelberg, Berlin, Heidelberg 2022, ISBN 978-3-642-41951-5, S. VII.
↑ Bernhard Korte, Jens Vygen: Combinatorial Optimization. In: Algorithms and Combinatorics. 2002, ISSN 0937-5511, doi:10.1007/978-3-662-21711-5 (uni-muenchen.de [PDF; abgerufen am 16. Januar 2024]).
↑ Volker Turau, Christoph Weyer: Algorithmische Graphentheorie: deterministische und randomisierte Algorithmen (= De Gruyter Studium). 5th edition Auflage. De Gruyter, Berlin ; Boston 2024, ISBN 978-3-11-135270-1, S. V.
↑ Wolfgang Schweizer: Matlab® Kompakt (= De Gruyter Studium). 7., aktualisierte und erweiterte Auflage. De Gruyter Oldenbourg, Berlin ; Boston 2022, ISBN 978-3-11-074170-4, S. 146.
↑ Helmut Harbrecht, Michael Multerer: Algorithmische Mathematik: Graphen, Numerik und Probabilistik. 1. Aufl. 2022. Springer Berlin Heidelberg, Berlin, Heidelberg 2022, ISBN 978-3-642-41951-5, S. 65.
↑ Helmut Harbrecht, Michael Multerer: Algorithmische Mathematik: Graphen, Numerik und Probabilistik. 1. Aufl. 2022. Springer Berlin Heidelberg, Berlin, Heidelberg 2022, ISBN 978-3-642-41951-5, S. 76.
↑ Helmut Harbrecht, Michael Multerer: Algorithmische Mathematik: Graphen, Numerik und Probabilistik. 1. Aufl. 2022. Springer Berlin Heidelberg, Berlin, Heidelberg 2022, ISBN 978-3-642-41951-5, S. 97.
↑ Helmut Harbrecht, Michael Multerer: Algorithmische Mathematik: Graphen, Numerik und Probabilistik. 1. Aufl. 2022. Springer Berlin Heidelberg, Berlin, Heidelberg 2022, ISBN 978-3-642-41951-5, S. 85.

ENDE

Betrachteter Gegenstand

→ Hauptartikel: Graph (Graphentheorie)

In der Graphentheorie bezeichnet ein Graph eine Menge von Knoten (auch Ecken oder Punkte genannt) zusammen mit einer Menge von Kanten. Eine Kante ist hierbei eine Menge von genau zwei Knoten. Eine Kante gibt an, ob zwei Knoten miteinander in Beziehung stehen, bzw. ob sie in der bildlichen Darstellung des Graphen verbunden sind. Zwei Knoten, die durch eine Kante verbunden sind, heißen benachbart oder adjazent. Wenn die Kanten statt durch Mengen durch geordnete Paare von Knoten angegeben sind, spricht man von gerichteten Graphen. In diesem Falle unterscheidet man zwischen der Kante (a,b) – als Kante von Knoten a zu Knoten b – und der Kante (b,a) – als Kante von Knoten b zu Knoten a. Knoten und Kanten können auch mit Farben (formal mit natürlichen Zahlen) oder Gewichten (d. h. rationalen oder reellen Zahlen) versehen werden. Man spricht dann von knoten- bzw. kantengefärbten oder -gewichteten Graphen.

Komplexere Graphentypen sind:

Multigraphen, bei denen die Kantenmenge eine Multimenge ist
Hypergraphen, bei denen eine Kante eine beliebig große Menge von Knoten darstellt (man spricht in diesem Falle auch von Hyperkanten)
Petri-Netze mit zwei Arten von Knoten

Ist die Menge der Knoten endlich, spricht man von endlichen Graphen, ansonsten von unendlichen Graphen.

Graphen als Datenstruktur

Graphen lassen sich insbesondere mit folgenden Datenstrukturen als Datenstruktur repräsentieren:

Grapheneigenschaften

Graphen können verschiedene Eigenschaften haben. So kann ein Graph

zusammenhängend (im allgemeinen k-zusammenhängend)
bipartit, (im allgemeinen k-partit)
planar,
eulersch oder hamiltonisch sein.

Es kann nach der Existenz spezieller Teilgraphen oder Minoren gefragt werden oder bestimmte Parameter untersucht werden, wie zum Beispiel Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite, Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, Bogenzusammenhangszahl, chromatische Zahl, Stabilitätszahl oder Cliquenzahl. Zwei Graphen können isomorph (strukturell gleich) oder automorph zueinander sein.

Wenn ein Knoten besonders ausgezeichnet ist, spricht man von einer Wurzel bzw. einm gewurzeltem Graphen.

Die verschiedenen Eigenschaften können zueinander in Beziehung stehen. Die Beziehungen zu untersuchen ist eine Aufgabe der Graphentheorie. Beispielsweise ist die Knotenzusammenhangszahl nie größer als die Kantenzusammenhangszahl, welche wiederum nie größer als der Minimalgrad des betrachteten Graphen ist. In ebenen Graphen ist die Färbungszahl immer kleiner als 5. Diese Aussage ist auch als der Vier-Farben-Satz bekannt.

Graphenklassen

Grundsätzlich werden Graphen in gerichtete und ungerichtete Graphen unterteilt.

azyklische Graphen: Weg, Pfad, Wald, Baum
zyklische Graphen: Zyklus, Kreis, Vollständige Graphen

Aufgrund des Vorhandenseins bestimmter Eigenschaften lassen sich weitere Graphenklassen unterscheiden wie

Bipartite Graphen
Planare Graphen

Grundlegende Begriffe und Probleme

Die Graphentheorie definiert eine Vielzahl von grundlegenden Begriffen sehr intuitiv einleuchtend:

Weitere grundlegende Begriffe sind:

Graphen können verschiedene Eigenschaften haben. So kann ein Graph zusammenhängend, bipartit, planar, eulersch oder hamiltonisch sein. Es kann nach der Existenz spezieller Teilgraphen gefragt werden oder bestimmte Parameter untersucht werden, wie zum Beispiel Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite, Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, Bogenzusammenhangszahl, chromatische Zahl, Stabilitätszahl oder Cliquenzahl.

Die verschiedenen Eigenschaften können zueinander in Beziehung stehen. Die Beziehungen zu untersuchen ist eine Aufgabe der Graphentheorie. Beispielsweise ist die Knotenzusammenhangszahl nie größer als die Kantenzusammenhangszahl, welche wiederum nie größer als der Minimalgrad des betrachteten Graphen ist. In ebenen Graphen ist die Färbungszahl immer kleiner als 5. Diese Aussage ist auch als der Vier-Farben-Satz bekannt.

Einige der aufgezählten Grapheneigenschaften sind relativ schnell algorithmisch bestimmbar, etwa wenn der Aufwand höchstens mit dem Quadrat der Größe der Graphen wächst. Andere Eigenschaften praktisch angewandter Graphen sind innerhalb der Lebensdauer heutiger Computer nicht exakt zu bestimmen. Allerdings kann in diesen Fällen der Einsatz von heuristischen Verfahren zu sinnvollen Näherungslösungen führen.