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

Man unterscheidet dabei zwischen:

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

Kompliziertere Graphentypen sind:

• Multigraphen, bei denen in dem Gegensatz zu einfachen Graphen Kanten zwischen den Knoten mehrfach vorkommen dürfen und
• Hypergraphen, bei denen in dem Gegensatz zu einfachen Graphen Kanten mehr als ca. zwei Knoten verbinden können.

Je nach Problemstellung können Knoten und Kanten 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.

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

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

• 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 verschiedenes Merkmalen 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 behandelt werden, wie zu dem Beispiel Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite , Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, chromatische Zahl, Stabilitätszahl oder Cliquenzahl.

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

Einige der aufgezählten Graphen Merkmale sind relativ leicht algorithmisch bestimmbar, d. h. die entsprechenden Algorithmen benötigen in Abhängigkeit der Größe der Graphen ca. wenig Zeit, um die Graphen Merkmal zu berechnen. Anderes Merkmalen sind praktisch auch mit Computer unlösbar.

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

• Paarungen in Graphen
• Zusammenhang von Graphen
• Flüsse und Schnitte in Netzwerken
• Färbung von Graphen
• Durchlaufbarkeit von Graphen
  • Eulerkreis-Problem
  • Hamiltonkreis-Problem
  • Problem des Handlungsreisenden
• Cliquen und stabile Mengen

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

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

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

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

Im Bereich der Computergraphik ist die Visualisierung von Graphen eine Herausforderung. Besonders komplexe Netze werden erst durch ausgefeilte Autolayout-Algorithmen übersichtlich.

• Graph Theory Resources (http://www.cs.columbia.edu/~sanders/graphtheory/), eine Datenbank von Personen und Themen aus der graphentheoretischen Forschung
• GraphViz - Graph Drawing Tools (http://www.graphviz.org), ein Open Source-Tool welches es ermöglicht Graphen mittels einer einfach Sprache darzustellen. Daraus können dann u.a. VRML, SVG, PNG oder GIF-Dateien erstellt werden.