Definition und Begriffe

Ein Graph ist eine Menge von Knoten, welche durch Kanten verbunden sind. Daher kann er auch mit dem Tupel G(V, E), mit V={Knoten}, E={Kanten} definiert werden.

graph LR linkStyle default interpolate basis A((A)) --- B((B)) A --- C((C)) B --- D((D)) C --- E((E)) D --- E C --- B B --- E C --- D

Begriffe

  • Der Grad dG(u) des Knoten u im Graphen G ist die Anzahl der an diesen Knoten angebundenen Kanten.
  • Zwei Knoten sind adjazent, wenn diese durch eine Kante direkt verbunden sind
  • Wenn ein Knoten mit einer Kante verbunden sind, dann sind diese inzident
  • Eine Kantenfolge ist ein Ablauf von Knoten mit Kanten bei dem Kanten und Knoten auch mehrfach vorkommen dürfen
  • Ein Kantenzug ist eine Kantenfolge, bei der jede Kante nur einmal vorkommen darf
  • Ein Weg ist ein Kantenzug, bei dem jeder Knoten nur einmal passiert wird.
  • Ein Graph ist zusammenhängend, wenn zwischen jedem Knoten ein Weg existiert, also dass man von jedem Knoten (über Umwege) zu jeder anderem Knoten kommt

Spezialfälle

Typen von Graphen

Es kann gerichtete oder ungerichtete Graphen geben. Bei einem gerichteten Graphen, ist eine Verbindung zwischen zwei Knoten gerichtet, dass heißt es kann zwei Kanten zwischen zwei Knoten geben. Einen hin- und eine zurück. Ebenfalls kann man Kanten ein Gewicht zuweisen, was meistens als Arbeit oder Länge des Pfades gewertet wird. Dies ist dann ein gewichteter Graph.

graph LR linkStyle default interpolate basis subgraph Gewichteter I((A)) --- |2| J((B)) J --- |3| K((C)) I --- |5| K end subgraph Gerichteter E((A)) --> F((B)) E((A)) --> G((C)) G --> E F --> H((D)) H --> G end subgraph Ungerichteter A((A)) --- B((B)) A --- C((C)) B --- D((D)) C --- D end

Baum

Ein Baum ist eine Sonderform des Graphen, in der es keine Kreise gibt.

graph LR A((A)) --- B((B)) A --- C((C)) A --- D((D)) B --- E((E)) C --- F((F)) C --- G((G)) D --- H((H)) H --- I((I)) H --- J((J))

Binärbaum

Ein Binärbaum ist wiederum eine Sonderform des Baumes, in der jeder Knoten maximal zwei Kindesknoten, also maximal drei Nachbarknoten hat. Binärbäume sind als Datenstruktur recht beliebt, da diese zum Beispiel als Priority queue eingesetzt werden können, wie später im Dijkstra Algorithmus zu sehen ist.

graph TD A((A)) --- B((B)) A --- C((C)) B --- D((D)) B --- E((E)) C --- F((F)) C --- G((G)) D --- H((H))

Eulerkreis und Eulertour

Ein Eulerweg ist eine Kantenfolge, in der alle Kanten des Graphen abgelaufen werden. Dabei spielt es keine Rolle auf welchem Knoten man beginnt und auf welchem Knoten man endet. Ein Beispiel dafür wäre das Haus vom Nikolaus. Dies ist jedoch bei einem Eulerkreis wichtig, da in dieser der Startknoten auch der Endknoten sein muss.

Schon Leonard Euler hat in 1735 den Eulerweg mit dem Königsberger Brückenproblem entdeckt. Dabei ging es darum in der Stadt eine Rundweg zu finden, welcher über jede Brücke genau einmal führt. Dabei kann man die Brücken als Kanten und die Stadtteile als Knoten ansehen. So darf man in diesem Rundweg nur genau einmal jede Kante/Brücke passieren, jedoch die Knoten/Stadtteile mehrmals betreten.

graph LR linkStyle default interpolate basis A((A)) --- B((B)) A --- C((C)) C --- B C --- D((D)) C --- D B --- D A --- C
Aus dem Graphen ist es abzulesen, dass kein Eulerweg existiert, da für diese alle Knoten eine ungerade Anzahl an Nachbarknoten haben.

Daraus lernen wir die folgenden Kriterien für den Eulerkreis/tour:

  1. Für den Eulerweg darf es maximal 2 Knoten mit ungeradem Grad geben.
  2. Für den Eulerkreis müssen alle Knoten einen geraden Grad haben

Daraus lässt sich ableiten, dass jede Eulertour auch ein Eulerkreis ist.