Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 19. Juni 2019 

Graphentheorie


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Graphentheorie ist ein Teilgebiet der Mathematik das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.

Dadurch dass einerseits viele algorithmische Probleme Graphen zurückgeführt werden können und andererseits die graphentheoretischer Probleme oft auf Algorithmen basiert ist Graphentheorie auch in der Informatik insbesondere der Komplexitätstheorie von großer Bedeutung.

Auf den ersten Blick scheint die eher eine abstrakte und realitätsferne Disziplin der zu sein. Tatsächlich lassen sich aber sehr Alltagsprobleme mit Hilfe von Graphen modellieren.

Einen Überblick über die in der Wikipedia graphentheoretischen Artikel liefert das Portal Graphentheorie .

Inhaltsverzeichnis

Betrachteter Gegenstand

In der Graphentheorie ist ein Graph eine Menge von Punkten (man nennt dann Knoten oder auch Ecken) die eventuell Linien (sog. Kanten bzw. Bögen) miteinander verbunden Die Form der Punkte und Linien spielt der Graphentheorie keine Rolle.

Man unterscheidet dabei zwischen:

  • endlichen Graphen bei denen die Menge der Knoten Kanten endlich ist und unendlichen Graphen auf die dies nicht zutrifft sowie
  • gerichteten Graphen bei denen die Kanten gerichtet sein (dargestellt durch Pfeile statt Linien) und ungerichteten Graphen .

Kompliziertere Graphentypen sind:

  • Multigraphen bei denen im Gegensatz zu einfachen Kanten zwischen den Knoten mehrfach vorkommen dürfen
  • Hypergraphen bei denen im Gegensatz zu einfachen Kanten mehr als nur zwei Knoten verbinden

Je nach Problemstellung können Knoten und auch mit Farben (formal mit natürlichen Zahlen) oder Gewichten (d.h. rationalen oder reellen Zahlen) versehen werden. Man spricht dann knoten- bzw. kantengefärbten oder -gewichteten Graphen.

Exakte Definitionen der verschiedenen Graphentypen findet im Artikel Typen von Graphen in der Graphentheorie .

Grundlegende Begriffe und Probleme

Die Graphentheorie definiert eine Vielzahl von Begriffen deren Kenntnis zum Verständnis von wissenschaftlichen unbedingt von Nöten ist. Glücklicherweise sind die in der Mehrheit sehr intuitiv bezeichnet so man diese schnell erlernen kann und nur die genaue Definition nachschlagen muss. Vor der weitergehender graphentheoretischer Artikel empfiehlt sich daher insbesondere Lesen der folgenden Artikel:

Weitere grundlegende Begriffe findet man in:


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

Die verschiedenen Eigenschaften können zueinander in stehen. Die Beziehungen zu untersuchen ist eine der Graphentheorie. Beispielsweise ist die Knotenzusammenhangszahl immer als die Kantenzusammenhangszahl welche wiederum immer kleiner der Minimalgrad des betrachteten Graphen ist. In Graphen ist die Färbungszahl immer kleiner als Diese Aussage ist auch als der 4-Farben-Satz bekannt.

Einige der aufgezählten Grapheneigenschaften sind relativ algorithmisch bestimmbar d.h. die entsprechenden Algorithmen benötigen Abhängigkeit der Größe der Graphen nur wenig um die Grapheneigenschaft zu berechnen. Andere Eigenschaften praktisch auch mit Computer unlösbar.

Die wichtigsten Probleme und Ergebnisse der werden in folgenden Artikeln dargestellt:

Geschichte

Die Anfänge der Graphentheorie gehen bis das Jahr 1736 zurück. Damals publizierte Leonhard Euler eine Lösung für das Königsberger Brückenproblem . Die Frage war ob es einen durch die Stadt Königsberg - heute Kaliningrad - gibt der jede der sieben über den Fluss Pregel genau einmal benutzt. Euler konnte für Problem eine notwendige Bedingung angeben und so Existenz eines solchen Rundganges verneinen. Eine hinreichende sowie einen effizienten Algorithmus der in einem einen solchen Rundgang finden kann wurde erst 1873 von Hierholzer angegeben.

Anwendungen

Wie oben erläutert können mit Hilfe Graphen viele Probleme modelliert werden. So läßt die Aufgabe eine kürzeste Route zwischen zwei zu finden dadurch lösen in dem man Straßennetz geeignet als kantengewichteten Graphen modelliert und in diesem mit Hilfe Algorithmus von Dijkstra effizient einen kürzesten Weg berechnet.

Bekannt ist auch das Problem die einer Landkarte mit möglichst wenig Farben so färben dass aneinander angrenzende Länder nicht die Farbe erhalten. Hier wird die Landkarte ebenfalls einen Graphen übersetzt und dann versucht mit Algorithmus dieses Problem zu lösen. Allerdings weiß heute dass dieses Problem auch mit Computern zu lösen ist und es wird vermutet keine effizienten Algorithmen existieren die dieses Problem lösen.

Stundenplanprobleme lassen sich über die Färbung von Graphen formulieren.

Weblinks

  • Graph Theory Resources eine Datenbank von Personen und Themen der graphentheoretischen Forschung



Bücher zum Thema Graphentheorie

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Graphentheorie.html">Graphentheorie </a>