Graphentheorie

Grundlegende Begriffe und Probleme

Die Graphentheorie definiert eine Vielzahl von grundlegenden Begriffen, deren Kenntnis zum Verständnis von wissenschaftlichen Abhandlungen unbedingt vonnöten ist. Diese sind in der Mehrheit sehr intuitiv bezeichnet, so dass man diese schnell erlernen kann und nur gelegentlich die genaue Definition nachschlagen muss. Vor der Lektüre weitergehender graphentheoretischer Artikel empfiehlt sich daher insbesondere das Lesen der folgenden Artikel:

• Typen von Graphen in der Graphentheorie
• Nachbarschaft und Grad in Graphen
• Wege, Pfade, Zyklen und Kreise in Graphen
• Wälder und Bäume in der Graphentheorie

Weitere grundlegende Begriffe findet man in:

• Repräsentation von Graphen im Computer
• Isomorphie von Graphen
• Operationen auf Graphen
• Teilgraphen und Minoren

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, 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 leicht algorithmisch bestimmbar, das heißt, die entsprechenden Algorithmen benötigen in Abhängigkeit von der Größe der Graphen nur wenig Zeit, um die Grapheneigenschaft zu berechnen. Andere Eigenschaften sind praktisch auch mit Computern unlösbar.

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

• Paarung (Graphentheorie)
• Zusammenhang von Graphen
• Flüsse und Schnitte in Netzwerken
• Färbung von Graphen
• Durchlaufbarkeit von Graphen
• Eulerkreisproblem
• Briefträgerproblem
• Hamiltonkreisproblem
• Problem des Handlungsreisenden
• Knotenüberdeckungen, Cliquen und stabile Mengen

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Graphentheorie aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung