Graphentheorie

Zur anschaulichen Darstellung von Beziehungen zwischen beliebigen Objekten werden oft graphische Hilfsmittel benutzt (z. B. Punkte, Strecken, Pfeile, Bezeichnungen, etc.). Beispiele hierzu sind Stadtpläne, Straßen- und Schienennetze, Wasserleitungspläne, Schaltpläne, Organisationspläne, Projektpläne u.v.m.. Das mathematische Modell für solche Situationen ist der Graph, das mathematische Teilgebiet heißt Graphentheorie. Im Gegensatz zu dem Begriff des Funktions­graphen aus der Analysis hat der Begriff Graph hier eine völlig andere Bedeutung. Es gibt zwischen diesen beiden Begriffen so gut wie keine Gemeinsamkeiten. In der Graphentheorie ist ein Graph eine Menge von Punkten (auch Knoten oder Ecken genannt, [engl.: vertices]), die durch Linien (auch Bögen oder Kanten genannt [engl.: edges]) miteinander verbunden sind. Die von mir bevorzugten Bezeichnungen sind: Knoten und Kanten. Die Form der Knoten und Kanten spielt in der Graphentheorie keine Rolle. 

Details
Hauptkategorie: Diskrete Mathematik
Kategorie: Graphentheorie

Wie bereits in der Einleitung erwähnt, ist das mathematische Modell für eine Situationen, in der mit graphischen Hilfsmitteln Beziehungen zwischen Objekten veranschaulicht werden, der Graph. Eine erste Einteilung von Graphen, eine Klassifizierung auf oberster Ebene, erfolgt anhand einiger wenige Kriterien, die einen direkten Bezug auf die Knoten und Kanten eines Graphen nehmen. Wir unterscheiden:

  • endliche und unendliche Graphen (Kriterium: Ist die Anzahl der Knoten endlich?)
  • Graphen mit und ohne Schlingen (Kriterium: Gibt es eine Kante, die einen Knoten mit sich selbst verbindet?)
  • gerichtete und ungerichtete Graphen (Kriterium: Haben die Kanten eine Orientierung?)
  • Graphen ohne Mehrfachkanten und Multigraphen (Kriterium: Gibt es mehr als eine Kante zwischen zwei Knoten?)
  • knotengefärbte bzw. knotengewichtete Graphen (Kriterium: Sind die Knoten gefärbt oder gewichtet?)
  • kantengefärbte bzw. kantengewichtete Graphen (Kriterium: Sind die Kanten gefärbt oder gewichtet?)
  • Hypergraphen (Kriterium: Werden mehr als zwei Knoten durch eine "Kante" [Hyperkante] verbunden?)

Ein endlicher, ungerichteter Graph ohne Mehrfachkanten und ohne Schlingen heißt einfacher Graph. Im Allgemeinen bestimmt der Kontext von welcher Art von Graphen man gerade spricht. Ist dieser Kontext nicht ersichtlich, so wird unter dem Begriff Graph ein einfacher Graph verstanden. 

Über die oben gemachte grobe Einteilung von Graphen hinaus, bestimmt die Art der 'Wege' innerhalb eines Graphen seine besonderen Eigenschaften. Diese Eigenschaften spiegeln sich in einem weiteren Adjektiv wider. Graphen können

  • zusammenhängend
  • zweiteilig (bipartit)
  • plättbar (planar)
  • eulersch
  • hamiltonsch
  • ...

sein. Die Vorgehensweise ist dieselbe wie in allen Bereichen der Mathematik. Die Einschränkung eines allgemeinen Objektes, hier des allgemeinen Graphen, durch "Hinzufügen eines Attributes", ermöglicht weitreichendere Untersuchungsmethoden und zeigt weitere Eigenschaften dieses Objektes.

Beispiel: Satz von Euler

Ein endlicher Multigraph hat einen geschlossenen Eulerzug genau dann, wenn er zusammenhängend ist und der Grad jedes Knotens  gerade ist.
Eulerzug
Ein Eulerzug  ist ein Kantenzug, der alle Kanten des Graphen enthält [also eine Kantenfolge, die alle Kanten des Graphen genau einmal enthält].
Kantenzug
Ein Kantenzug ist eine Kantenfolge, bei der alle Kanten verschieden sind.
Kantenfolge
Eine Kantenfolge ist eine Folge von 'benachbarten' Kanten. Sie ist geschlossen, wenn der Startknoten gleich dem Endknoten ist.
Grad eines Knoten
Der Grad eines Knotens v  ist die Anzahl der Kanten, die von ihm abgehen.

ACHTUNG: Bei Wikipedia (Stand 2013) wird der Begriff Kantenzug leider immer noch falsch verwendet!