Graph

Ein Graph mit fünf Knoten $A,B,C,D,E$
und sieben Kanten ${\overline {AB}}$, ${\overline {AC}}$, ${\overline {BC}}$, ${\overline {BD}}$, ${\overline {BE}}$, ${\overline {CD}}$ und ${\overline {DE}}$.

Ein Graph ist eine Datenstruktur, die aus einer Menge an Knoten und einer Menge an Kanten besteht, wobei jede Kante zwei Knoten miteinander verbindet.

Graphen werden in der Informatik genutzt, um alle möglichen Sachverhalte zu modellieren, etwa die Verknüpfungen zwischen Neuronen in einem künstlichen Neuronalen Netz, die Spielfelder für einen Schachcomputer oder Orte und Straßen für die Routenplanung in Navigationssoftware.

Begriffe

Eine zusammenhängende Abfolge von Kanten bezeichnet man als Weg oder Pfad. Im obigen Beispielgraphen bilden z.B. ${\overline {AB}},{\overline {BC}},{\overline {CD}},{\overline {DE}}$ oder auch ${\overline {BE}},{\overline {BC}},{\overline {AC}}$ einen Weg.

Eine zusammenhängende Abfolge von Kanten, die dort endet, wo sie begonnen hat, bezeichnet man als Kreis. Im obigen Beispielgraphen bilden z.B. die Kanten ${\overline {AB}},{\overline {AD}},{\overline {DE}},{\overline {BE}}$ einen Kreis.

Arten von Graphen

(Un-)Gerichtete Graphen

Gerichtete Graphen zeichnen sich dadurch aus, dass die Kanten zwischen den Knoten eine Richtung haben. Mit gerichteten Graphen kann man z.B. künstliche neuronale Netze modellieren, die die Daten von der Eingabe- über die inneren Schichten zur Ausgabeschicht weiterleiten, oder Endliche Automaten, die reguläre Sprachen erkennen.

Das Gegenteil sind ungerichtete Graphen, deren Kanten keine Richtung aufweisen. Als ungerichteten Graphen kann man z.B. ein Schachbrett (außer aus der Perspektive eines Bauern) modellieren, da jeder Zug auch genau so in entgegengesetzter Richtung durchgeführt werden kann.

(Un-)Gewichtete Graphen

Man kann den Kanten eines Graphen ein Gewicht zuweisen. Damit kann man bspw. für die Berechnung von Streckenlängen für ein Navigationssystem die Streckenlänge, den zu erwartenden Stromverbrauch o.ä. modellieren.

Das Gegenteil sind ungewichtete Graphen, deren Kanten kein Gewicht haben. Auch das oben als Beispiel erwähnte Schachbrett kann man als ungewichteten Graphen modellieren.

(Un-)zusammenhängende Graphen

Graphen, in denen es von jedem Knoten zu jedem anderen Knoten mindestens einen Weg gibt, nennt man zusammenhängend.

Das Gegenteil sind unzusammenhängende Graphen, in denen es zwischen mindestens einem Knotenpaar keinen Weg gibt. Diese Graphen bestehen aus mehreren Teilgraphen, die nicht miteinander verbunden sind. Diese Teilgraphen werden Zusammenhangskomponenten genannt.

Beispiele

• 

  Gewichtet ✔️
  Gerichtet ✔️
  Zusammenhängend ✔️
  Kreis ✔️

• 

  Gewichtet ✔️
  Gerichtet ❌
  Zusammenhängend ✔️
  Kreis ✔️

• 

  Gewichtet ✔️
  Gerichtet ✔️
  Zusammenhängend ✔️
  Kreis ❌

• 

  Gewichtet ❌
  Gerichtet ✔️
  Zusammenhängend ❌
  Kreis ❌

• 

  Gewichtet ❌
  Gerichtet ❌
  Zusammenhängend ❌
  Kreis ✔️

• 

  Gewichtet ❌
  Gerichtet ❌
  Zusammenhängend ✔️
  Kreis ❌

Bäume als Sonderfall von Graphen

Zusammenhängende kreisfreie Graphen werden auch als Bäume bezeichnet, unzusammenhängende kreisfreie Graphen, die also aus mehreren Bäumen bestehen, als Wälder.